330. Contains Duplicate II
Easy
Last Seen Index
Hashing
Problem
Given an integer array nums and an integer k, return true if there are two distinct indices i and j such that nums[i] equals nums[j] and the absolute difference between i and j is at most k.
Examples
Example 1
Input: [1,2,3,1], 3
Output: true
Example 2
Input: [1,0,1,1], 1
Output: true
Example 3
Input: [1,2,3,1,2,3], 2
Output: false
Constraints
� 1 <= nums.length <= 100000
� -1000000000 <= nums[i] <= 1000000000
� 0 <= k <= 100000
Hints
?? Remember the most recent index of each value.
?? When a value appears again, compare the current index with its previous index.
?? A bounded sliding-window set is another solution.
Expected Complexity
Time: O(n)
Space: O(min(n, k)) or O(n)
Follow-up
Can you solve it with a hash set containing at most k + 1 elements?
Practice Notes
Attempts: 0
Time spent: 0min
Hints used: 0
JavaScript
00:00
Loading...
Case 1
Case 2
Case 3
Input
[1,2,3,1], 3Expected
true