Problem Statement in English

You’re given an array nums, and an integer k. Your task is to return true, if there are duplicates in any subarray of nums, where i represents its leftmost index, and j its rightmost index, such that $\text{abs}(i-j) = k$.

Approach

First off, you can do this by sheer brute force. Use a nested loop, and check every possibility. That’s straightforward, and we’re not going to be getting into that. We’re going to try and improve the time complexity from $O(n^2)$ to $O(n)$.

The technique we’re going to use is called the Sliding Window approach. It utilises 2 pointers that we’re going to have to manage cleverly in order to maintain a window size that we desire.

Now I say clever, but really, all you have to do is remove the leftmost element of the window whenever we exceed the desired window size, and move the left pointer forward by $1$.

This is as generic as I can make the Sliding Window to be, as you can use the contents of the window for a wide variety of purposes. Check out this problem for another use case for this algorithm, which makes for a nice follow up.

I’ll let my code explain the approach to this problem.

Solution in Python


class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        # if `k` is 0
        # there cannot be be any duplicates
        # because the question specifies that `i` and `j`
        # must be *distinct*
        if k == 0:
            # return false
            return False

        # initialise the set
        # which we will use to detect duplicates
        # in constant time
        s = set()

        # left pointer
        leftPtr = 0

        for rightPtr in range(len(nums)):
            # if condition specified in question is not met
            # we've exceeded the permitted window size
            if rightPtr - leftPtr > k:
                # remove the value pointer to by the left pointer
                s.discard(nums[leftPtr])
                # move left pointer ahead
                # to satisfy window size requirement
                leftPtr += 1
            # check if new value pointer to
            # by the right pointer
            # already exists in `nums`
            if nums[rightPtr] in s:
                # if it does,
                # return true
                return True
            # otherwise add the new value to the set
            s.add(nums[rightPtr])

        # if we've reached here, then no duplicates exist within
        # the provided window size in `arr`
        # return false
        return False

Complexity

  • Time: $O(n)$
    Since we iterate over $n$ elements at most.

  • Space: $O(1)$
    Since we only store a couple integer variables.

And we are done.