Sliding Window - Contains Duplicate II

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.

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

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

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

Constraints:

1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
0 <= k <= 10⁵

Solution 1 - Using sliding window technique, and a HashSet find if there is a duplicate element within window size of K

In this approach, we are going to apply sliding window technique, using two pointers left and right, find if there is any duplicate element found within the window size of k ( i.e. right - left).

Implementation steps:

First, we will create three variables left, right that we will use to adjust the window, and a HashSet, dups to check the duplicate of an element. Initialize left=0 and right=0, that is the beginning window size.
Next, run a while loop until right pointer reaches end of array, and check:
- If the difference between right and left pointers are greater than K: This means that we are going out of window size k, so remove left pointer element from dups to keep the window size within k, and also increment left pointer.
- If the right pointer element is found in HashSet: return true, since a duplicate found within the window size of k.
- Finally, add right pointer element to the dups and then increment right pointer.
If there is no duplicate found, at the end return false.

import java.util.HashSet; public class ContainsDuplicatesII { static boolean containsNearbyDuplicate(int[] nums, int k) { int left = 0; int right = 0; HashSet<Integer> dups = new HashSet<>(); while(right < nums.length) { if(right-left > k) { dups.remove(nums[left]); left++; } if(dups.contains(nums[right])) { return true; } dups.add(nums[right]); right++; } return false; // if nothing found } public static void main(String[] args) { System.out.println(containsNearbyDuplicate(new int[]{1, 2, 3, 1}, 3)); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of nums array.
Space complexity: O(k) for the HashSet that is used check duplicates, and at any given time it contains atmost k elements.

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: