Contains Duplicate 2

Problem Statement:

You are given an integer array nums and an integer k. Your task is to determine if there are two distinct indicesi and j in the array such that:

• nums[i] == nums[j], and
• |i - j| <= k.

If such indices exist, return true. Otherwise, return false.

Leet Code:

https://leetcode.com/problems/contains-duplicate-ii/description/

Constraints:

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
0 <= k <= 10^5

1. 1 ≤ nums.length ≤ 10^5
   1. The input array can have up to 100,000 elements, so:
      1. ❌ Brute-force (O(n^2)) will time out.
      2. We need an efficient approach, ideally O(n) or O(n log n).
2. -10^9 ≤ nums[i] ≤ 10^9
   1. Elements can be very large or very negative, so:
      1. You can't use array indexing based on the value (like arr[nums[i]]).
      2. Use a data structure like set or map (or unordered_set/unordered_map) that supports large integers.
3. 0 ≤ k ≤ 10^5
   1. k controls the maximum allowed index distance for a duplicate.
      1. If k = 0: no duplicates can ever satisfy abs(i - j) <= k unless i == j — which is disallowed.
      2. If k >= nums.length: you're effectively looking for any duplicate, same as Contains Duplicate I.

Examples

Example 1:

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

Explanation:
nums[0] == nums[3] and
|0 - 3| <= 3, which is less than or equal to k.

Example 2:

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

Explanation:
nums[2] == nums[3] and
|2 - 3| = 1, which is less than or equal to k.

Example 3:

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

Explanation: No pair of indices satisfied the condition
where the difference between their indices is less than
or equal to k for equal values.

Different Approaches

1️⃣ Brute Force Approach (TLE for large input)

Intuition:

Check all pairs with distance ≤ k.

Dry Run:

Initialization:

       +-----+-----+-----+-----+
nums = |  1  |  2  |  3  |  1  |
       +-----+-----+-----+-----+
          0     1     2     3
k = 3

For i = 0

i = 0, j = i + 1 = 1
         +-----+-----+-----+-----+
  nums = |  1  |  2  |  3  |  1  |
         +-----+-----+-----+-----+
            0     1     2     3
            ^     ^
            |     |
            i     j
  k = 3

     Do j <= i + k
        1 <= 0 + 3
        True
        Does nums[i] == nums[j]
                   1 == 2
                   False

i = 0, j = 2
         +-----+-----+-----+-----+
  nums = |  1  |  2  |  3  |  1  |
         +-----+-----+-----+-----+
            0     1     2     3
            ^           ^
            |           |
            i           j
  k = 3

     Do j <= i + k
        2 <= 0 + 3
        2 <= 3
        True
        Does nums[i] == nums[j]
                   1 == 3
                   False

i = 0, j = 2
         +-----+-----+-----+-----+
  nums = |  1  |  2  |  3  |  1  |
         +-----+-----+-----+-----+
            0     1     2     3
            ^                 ^
            |                 |
            i                 j
  k = 3

      Do j <= i + k
        3 <= 0 + 3
        3 <= 3
        True
        Does nums[i] == nums[j]
                   1 == 1
                   True
 
 Return true
 If it was False keep doing the same,
 for different values of i till last
 index of the array.

Code:

bool containsNearbyDuplicate(std::vector<int>& nums, int k) {
    // Outer loop goes through each element
    for (int i = 0; i < nums.size(); ++i) {
        // Inner loop checks the next `k` elements or till the end of the array
        for (int j = i + 1; j <= i + k && j < nums.size(); ++j) {
            if (nums[i] == nums[j]) {
                return true;  // Return true if duplicate is found
            }
        }
    }
    return false;  // No such pair found
}

Complexity Analysis:

• Time Complexity:O( n * k), where n is the size of the array and k is the given window size.
  • In the worst case, for each element, you are only checking the next k elements.
• Space Complexity:O(1)
  • Since no extra space is used apart from variables.

2️⃣ Hashing (Stores indices)

Intuition:

We can use a hash map (or unordered map) to keep track of the most recent index of each number in the array. As we iterate through the array:

• For each element nums[i], we check if it already exists in the map.
• If it exists, we calculate the absolute difference between its current index i and the previously stored index.
  • If the difference is less than or equal to k, return true.
  • If not, update the index in the map.
• If the number doesn't exist in the map, add it with the current index.

If we finish processing the array and no such pair is found, return false.

Approach:

1. Initialize an empty hash map (unordered map) to store the last seen index of each element.
2. Iterate through the array:
   • If the element already exists in the map:
     • Check if the difference between the current index and the previously stored index is less than or equal to k.
     • If yes, return true.
   • Update the map with the current index for that element.
3. If no valid pair is found, return false.

Dry Run:

Initialization:

       +-----+-----+-----+-----+
nums = |  1  |  2  |  3  |  1  |
       +-----+-----+-----+-----+
          0     1     2     3
k = 3

lastSeenIndex map =   key  value
                    +-----+-----+
                    |     |     |
                    +-----+-----+

First Iteration:

       +-----+-----+-----+-----+
nums = |  1  |  2  |  3  |  1  |
       +-----+-----+-----+-----+
          0     1     2     3
          ^
          |
          i
k = 3

lastSeenIndex map =   key  value
                    +-----+-----+
                    |     |     |
                    +-----+-----+

    Check if nums[i] exists in the map
    nums[0] = 1 does not exist in the map
    false
      add it in the with nums[i] as the key and index
      as value.

Second Iteration:

       +-----+-----+-----+-----+
nums = |  1  |  2  |  3  |  1  |
       +-----+-----+-----+-----+
          0     1     2     3
                ^
                |
                i
k = 3

lastSeenIndex map =   key  value
                    +-----+-----+
                    |  1  |  0  |
                    +-----+-----+

    Check if nums[i] exists in the map
    nums[1] = 2 does not exist in the map
    false
      add it in the with nums[i] as the key and index
      as value.

Third Iteration:

       +-----+-----+-----+-----+
nums = |  1  |  2  |  3  |  1  |
       +-----+-----+-----+-----+
          0     1     2     3
                      ^
                      |
                      i
k = 3

lastSeenIndex map =   key  value
                    +-----+-----+
                    |  1  |  0  |
                    +-----+-----+
                    |  2  |  1  |
                    +-----+-----+

    Check if nums[i] exists in the map
    nums[2] = 3, does not exist in the map
    false
      add it in the with nums[i] as the key and index
      as value.

Fourth Iteration:

       +-----+-----+-----+-----+
nums = |  1  |  2  |  3  |  1  |
       +-----+-----+-----+-----+
          0     1     2     3
                            ^
                            |
                            i
k = 3

lastSeenIndex map =   key  value
                    +-----+-----+
                    |  1  |  0  |
                    +-----+-----+
                    |  2  |  1  |
                    +-----+-----+
                    |  3  |  2  |
                    +-----+-----+

    Check if nums[i] exists in the map
    nums[3] = 1, does exist in the map
    true
      Check the index difference, if it less than or
      equal to k
      i - lastSeenIndex[1] <= k
      3 - 0 <= 3
      3 <= 3
      true 
      Return true

Code:

#include <unordered_map>
#include <vector>
#include <cmath>

bool containsNearbyDuplicate(std::vector<int>& nums, int k) {
    // Create a hash map to store the last seen index of each element
    std::unordered_map<int, int> lastSeenIndex;

    // Iterate through the array
    for (int i = 0; i < nums.size(); ++i) {
        // Check if nums[i] exists in the map
        if (lastSeenIndex.find(nums[i]) != lastSeenIndex.end()) {
            // If it exists, check the index difference
            if (i - lastSeenIndex[nums[i]] <= k) {
                return true; // Found a pair with |i - j| <= k
            }
        }
        // Update the last seen index for nums[i]
        lastSeenIndex[nums[i]] = i;
    }

    // If no such pair is found, return false
    return false;
}

Complexity Analysis:

• Time Complexity:O(n), where n is the number of elements in the nums.
  • Each insertion and lookup in the unordered map takes O(1) on average.
• Space Complexity:O(n)
  • We store at most n key-value pairs in the hash map.

3️⃣ Sliding Window with Set (Efficient and Simple)

Instead of using a hash map, we can use a sliding window approach with a set to track the numbers in the current window of size k. The sliding window ensures that we only consider indices within the range i and i-k.

• Instead of storing all the elements encountered so far, we store the k elements to create the window.

Intuition:

• As we iterate through the array, we maintain a set that contains at most k elements (the current sliding window).
• For each element, if it already exists in the set, it means we have found a duplicate within the window, and we return true.
• If the size of the set exceeds k, we remove the oldest element (i.e., the one at index i - k) to maintain the window size.
• If no duplicate is found by the end of the loop, we return false.

Dry Run:

Initialization:

       +-----+-----+-----+-----+
nums = |  1  |  2  |  3  |  1  |
       +-----+-----+-----+-----+
          0     1     2     3
k = 3

set => +-----+
       |     |
       +-----+

First Iteration:

       +-----+-----+-----+-----+
nums = |  1  |  2  |  3  |  1  |
       +-----+-----+-----+-----+
          0     1     2     3
          ^
          |
          i
k = 3

set => +-----+
       |     |
       +-----+

    Does nums[i] exist in set
    Does nums[0] = 1, exist in set
      false
      Insert nums[0] = 1, in the set
      Check if the set's size = 1 is greater than k = 3
        false

Second Iteration:

       +-----+-----+-----+-----+
nums = |  1  |  2  |  3  |  1  |
       +-----+-----+-----+-----+
          0     1     2     3
                ^
                |
                i
k = 3

set => +-----+
       |  1  |
       +-----+

    Does nums[i] exist in set
    Does nums[1] = 2 exist in set
      false
      Insert nums[1] = 2, in the set
      Check if the set's size = 2 is greater than k = 3
        false

Third Iteration:

       +-----+-----+-----+-----+
nums = |  1  |  2  |  3  |  1  |
       +-----+-----+-----+-----+
          0     1     2     3
                      ^
                      |
                      i
k = 3

set => +-----+
       |  1  |
       +-----+
       |  2  |
       +-----+

    Does nums[i] exist in set
    Does nums[2] = 3 exist in set
      false
      Insert nums[1] = 3, in the set
      Check if the set's size = 3 is greater than k = 3
        false

Fourth Iteration:

       +-----+-----+-----+-----+
nums = |  1  |  2  |  3  |  1  |
       +-----+-----+-----+-----+
          0     1     2     3
                            ^
                            |
                            i
k = 3

set => +-----+
       |  1  |
       +-----+
       |  2  |
       +-----+
       |  3  |
       +-----+

    Does nums[i] exist in set
    Does nums[3] = 1 exist in set
      true
      Since we maintain the window in set, such that
      if size of the set increases than the k we
      erase the first element from the set to maintain
      window width equal to k.
      Return true.

Code:

#include <unordered_set>
#include <vector>

bool containsNearbyDuplicate(std::vector<int>& nums, int k) {
    std::unordered_set<int> window;

    for (int i = 0; i < nums.size(); ++i) {
    	// If already in the window -> duplicate found
        if (window.find(nums[i]) != window.end()) {
            return true;
        }

		// Add current element to the window
        window.insert(nums[i]);

        // Ensure the window contains at most `k` elements
        // Remove the element that is now out of the window range
        if (window.size() > k) {
            window.erase(nums[i - k]);
        }
    }

    return false;
}

Complexity Analysis:

• Time Complexity:O(n), where n is the size of the input array.
• Space Complexity:O(k)
  • since the set stores at most k elements at any given time.