Kth distance

Given an unsorted array arr and anumber k which is smaller than size of the array. Find if the array contains duplicates within k distance.

Examples:

Input: arr[] = [1, 2, 3, 4, 1, 2, 3, 4] and k = 3
Output: false
Explanation: All duplicates are more than k distance away.

Input: arr[] = [1, 2, 3, 1, 4, 5] and k = 3
Output: true
Explanation: 1 is repeated at distance 3.

Constraints:
1 ≤ arr.size() ≤ 10⁶
1 ≤ k < arr.size()
1 ≤ arr[i] ≤ 10⁵

Approach 01:

#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
public:
    bool checkDuplicatesWithinK(const vector<int>& array, int distance) {
        int arrayLength = array.size();
        if (unordered_set<int>(array.begin(), array.end()).size() == arrayLength) {
            return false;
        }
        for (int i = 0; i <= arrayLength - distance - 1; ++i) {
            unordered_set<int> subArraySet(array.begin() + i, array.begin() + i + distance + 1);
            if (subArraySet.size() != distance + 1) {
                return true;
            }
        }
        return false;
    }
};

class Solution:
    def checkDuplicatesWithinK(self, array, distance):
        arrayLength = len(array)
        if len(set(array)) == arrayLength:
            return False
        for i in range(arrayLength - distance):
            subArray = array[i:i + distance + 1]
            if len(set(subArray)) != len(subArray):
                return True
        return False

Time Complexity

• Initial Duplicate Check:

  Creating a unordered_set with all elements from array takes \( O(N) \) time, where \( N \) is the length of array. Checking if all elements are unique in array by comparing the size of the set with arrayLength is an \( O(1) \) operation.

• Sliding Window Check:

  The outer loop iterates from 0 to \( N – \text{distance} – 1 \), making approximately \( O(N – \text{distance}) \) iterations.

  For each iteration, creating a unordered_set of size \( \text{distance} + 1 \) takes \( O(\text{distance}) \) time.

  This results in an overall time complexity of \( O(N \cdot \text{distance}) \) for this part.

• Overall Time Complexity:

  Combining both parts, the time complexity is \( O(N + N \cdot \text{distance}) \), which simplifies to \( O(N \cdot \text{distance}) \).

Space Complexity

• Initial Duplicate Check:

  The initial unordered_set for checking uniqueness in the entire array has a space complexity of \( O(N) \).

• Sliding Window Check:

  For each iteration, the unordered_set for storing a subset of elements has a space complexity of \( O(\text{distance}) \).

• Overall Space Complexity:

  The space complexity is \( O(N) \), as the largest set created is for the initial duplicate check, which takes up to \( O(N) \) space.