219. Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Example 1:

Input: [1,2,3,1], k = 3
Output: true

Example 2:

Input: [1,0,1,1], k = 1
Output: true

Example 3:

Input: [1,2,1], k = 0
Output: false


Solution:

In this array if we can find index i and j such that nums[i] == nums[j] and j - i <= k, return true. If we cannot find such i and j, return false.

We can iterate through the array and maintain a HashMap to store the value we've already met, and it's index.

For any index i, if there exists the same value in the map, we check their distance. If the distance is <= k, return true. If not, we update this value in the map with a new index i.

When finish iterating the array, we do not find such pair, and return false.

The time complexity is O(n) and the space complexity is also O(n).


Code:

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                if (i - map.get(nums[i]) <= k) {
                    return true;
                }
            }
            map.put(nums[i], i);
        }
        return false;
    }
}