algoadvance

Leetcode 219. Contains Duplicate II

Problem Statement

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

Clarifying Questions

1. Q: What should be returned if the array is empty or contains only one element?
   • A: Return false, as there can’t be any duplicate indices in such cases.
2. Q: Can the values in nums be negative?
   • A: Yes, the values in nums can be negative.
3. Q: Can k be zero or negative?
   • A: k is expected to be non-negative as per the problem constraints.
4. Q: How large can the array nums be?
   • A: The length of the array (n) can be up to 10^5.
5. Q: What are the possible values for k?
   • A: k can range from 0 to n-1, where n is the length of the array.

Strategy

We will use a HashMap to keep track of the indices of the elements as we iterate through the array. For each element, we will check if it has appeared before and if the difference between the current index and the last seen index is less than or equal to k. If such a pair is found, we return true. If we finish iterating through the array without finding such a pair, we return false.

Code

import java.util.HashMap;

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        // Test cases
        System.out.println(sol.containsNearbyDuplicate(new int[]{1, 2, 3, 1}, 3)); // true
        System.out.println(sol.containsNearbyDuplicate(new int[]{1, 0, 1, 1}, 1)); // true
        System.out.println(sol.containsNearbyDuplicate(new int[]{1, 2, 3, 1, 2, 3}, 2)); // false
    }
}

Time Complexity

• Time Complexity: O(n), where n is the length of the array. We iterate through the array once, and each operation (check and update the map) is O(1).
• Space Complexity: O(n), in the worst case, all elements may be unique and stored in the map.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?