LeetCode #122. Contains Duplicate II

Most efficent solution - o(n)

---

Time Complexity: O(n)

The for loop runs once for each element in nums, so that's O(n) where n = nums.length.

Inside the loop:

    * numSet.contains(nums[i]) → O(1) average case (HashSet lookup)
    * numSet.add(nums[i]) → O(1) average
    * numSet.remove(nums[i - k]) → O(1) average

No nested loops

Overall time: O(n)

Space Complexity O(k)

The space complexity is O(k) because the algorithm uses a sliding window of at most k elements stored in a HashSet. At any point, the size of the set never exceeds k, regardless of the total size of the input array n. So the memory usage scales with the window size k, not with the full input size n.

The set numSet holds at most k elements at a time due to this line:

if (numSet.size() > k) {
    numSet.remove(nums[i - k]);
}

So memory usage grows with k

Overall space: O(k)

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {

        Set<Integer> numSet = new HashSet<>();

        for (int i = 0; i < nums.length; i++) {
            if (numSet.contains(nums[i])){
                return true;
            }
            numSet.add(nums[i]);

            if (numSet.size() > k) {
                numSet.remove(nums[i - k]);
            }
        }
        return false;
    }    
}

---

Brute-force solution - o(n * k)

---

for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] == nums[j] && Math.abs(i - j) <= k)
return true;
}
}
return false;