Some Space Optimisations

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

MY FIRST APPROACH: A very valid solution

class Solution:
    def containsNearbyDuplicate(self, nums: list[int], k: int) -> bool:
        ref = {}
        for i in range(len(nums)):
            if nums[i] not in ref:
            ref[nums[i]] = i
        else:
            if abs(i - ref[nums[i]]) <= k:
            return True
        else:
            ref[nums[i]] = i
        return False

Enter fullscreen mode Exit fullscreen mode

This should work. And I was pretty happy with it.

Then I noticed the given constraints. One of which was the proposed sample size for the list/array

1 <= nums.length <= 10^^5

Enter fullscreen mode Exit fullscreen mode

10^^5 ????

The list/array has the potential to hold 100k items. My first approach of storing a copy of each value could easily grow O(n) times, worst case. If there are no duplicates, or if the duplicate is at the very end of the list, I could blindly end up storing each copy into the dictionary until we reach n – 1.

But that shouldn’t be necessary at all, since I only need to find duplicates within a fixed window size, k.

APPROACH 2:

class Solution:
    def containsNearbyDuplicate2(self, nums: list[int], k: int) -> bool:
        ref = set()
        for i in range(len(nums)):
            if len(ref) > k:
                ref.remove(k - i)

            if nums[i] in ref:
                return True
            else:
                ref.add(nums[i])
        return False

Enter fullscreen mode Exit fullscreen mode

This is better I suppose, space-wise. Now I can ensure the set only stores a fixed number of values. Such that len(ref) <= k at any given point in time.