EasyArraysAI interview only
Contains Duplicate II
Asked atamazongooglemetamicrosoftadobe
01 · Problem
You are given an integer array nums and a non-negative integer k. Determine whether there are two different indices i and j such that nums[i] == nums[j] and the distance between them, |i - j|, is at most k.
Return true if such a pair exists, otherwise return false. When k is 0 no valid pair can exist, so the answer is false.
02 · Examples
Example 01
Input
nums = [1,2,3,1], k = 3
Output
true
The two 1s sit at indices 0 and 3, which are exactly 3 apart, and 3 <= k.
Example 02
Input
nums = [1,0,1,1], k = 1
Output
true
The 1s at indices 2 and 3 are only 1 apart.
Example 03
Input
nums = [1,2,3,1,2,3], k = 2
Output
false
Every repeated value is exactly 3 positions away from its twin, which is more than k = 2.
03 · Constraints
- 011 <= nums.length <= 105
- 02-109 <= nums[i] <= 109
- 030 <= k <= 105
04 · Optimal complexity
- Time
- O(n)
- Space
- O(min(n, k))
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.