Contains Duplicate II

62.1k
0

Given an integer array nums containing N elements and a non-negative integer k, return true when two distinct indices i and j satisfy both conditions:

  • nums[i] == nums[j]

  • |i - j| <= k

Return false when no valid pair exists.

Example 1

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

Output: true

Explanation: Value 1 occurs at indices 0 and 3. The index distance is |0 - 3| = 3, which does not exceed k.

Example 2

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

Output: false

Explanation: Every repeated value occurs at indices separated by 3 positions. Since 3 > k, no valid pair exists.

Brute Force Approach

Only index pairs separated by at most K positions can satisfy the required distance condition. For an element at index i, positions after i + K cannot form a valid pair with index i.

Comparing every element with the next K eligible elements covers every valid forward pair. A matching pair confirms a nearby duplicate immediately. Completion of all eligible comparisons without equality confirms the absence of a valid pair.

Algorithm

  • Return false when N < 2 or K = 0, since two distinct indices cannot satisfy the required condition.

  • Traverse every index i from 0 to N - 1.

  • Traverse index j from i + 1 to min(N - 1, i + K), limiting comparisons to valid index distances.

  • Compare nums[i] with nums[j].

  • Return true immediately when equal values appear within a distance of at most K.

  • Return false after every eligible pair remains different.

Dry Run

cd2

cd2

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Checks every eligible pair within distance k. */
bool containsNearbyDuplicate(vector<int>& nums, int k) {
int n = nums.size();
// Handle cases without any valid distinct pair.
if (n < 2 || k <= 0) {
return false;
}
// Select the first index of every pair.
for (int i = 0; i < n; i++) {
// Compare only indices within distance k.
for (int j = i + 1;
j < n && j - i <= k;
j++) {
// Stop after finding a nearby duplicate.
if (nums[i] == nums[j]) {
return true;
}
}
}
// No valid duplicate pair exists.
return false;
}
};
// Driver code to execute the solution.
int main() {
vector<int> nums = {1, 2, 3, 1};
int k = 3;
Solution solution;
bool answer =
solution.containsNearbyDuplicate(nums, k);
cout << boolalpha << answer << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N × min(N, K)), where N represents the number of array elements and K represents the maximum allowed index distance. Every index is compared with at most the next K elements. The complexity becomes O(N²) when K is at least N.

Space Complexity: O(1), because only loop indices and the array size are stored.

Better Approach

The Brute Force Approach performs several repeated comparisons for every index. For the current value at index i, only the closest previous occurrence can produce the smallest possible index distance.

A Hash Map named latestIndex stores every processed value with the most recent index containing that value. The name latestIndex describes the stored information directly: every key represents an array value, while the corresponding mapped value represents the latest processed position of that value.

Comparing index i with the latest previous occurrence gives the minimum distance among all earlier equal values. Any older occurrence can only produce an equal or larger distance. After an unsuccessful distance check, replacing the stored position with index i prepares the closest possible occurrence for future comparisons.

Algorithm

  • Return false when N < 2 or K = 0, since two distinct indices cannot satisfy the required distance condition.

  • Initialize an empty Hash Map latestIndex. Store every processed array value as a key and the most recent index containing that value as the mapped value. The latest position provides the minimum possible distance from any future equal value.

  • Traverse every index i from 0 to N - 1.

  • Search for nums[i] inside latestIndex.

  • Retrieve the stored previous index when nums[i] already exists.

  • Calculate the distance between both occurrences using i - previousIndex.

  • Return true when the calculated distance does not exceed K.

  • Store or update latestIndex[nums[i]] = i after an unsuccessful check. The current index becomes the closest previous occurrence for every future appearance of the same value.

  • Return false after the complete traversal finds no valid pair.

Dry Run

cd2

cd2

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Stores the latest index of every value. */
bool containsNearbyDuplicate(vector<int>& nums, int k) {
int n = nums.size();
// Handle cases without any valid distinct pair.
if (n < 2 || k <= 0) {
return false;
}
// Map each value to the latest processed index.
unordered_map<int, int> latestIndex;
// Process every array index once.
for (int i = 0; i < n; i++) {
auto entry = latestIndex.find(nums[i]);
// Check the distance from the latest occurrence.
if (
entry != latestIndex.end() &&
i - entry->second <= k
) {
return true;
}
// Store the current index as the latest occurrence.
latestIndex[nums[i]] = i;
}
// No valid duplicate pair exists.
return false;
}
};
// Driver code to execute the solution.
int main() {
vector<int> nums = {1, 2, 3, 1};
int k = 3;
Solution solution;
bool answer =
solution.containsNearbyDuplicate(nums, k);
cout << boolalpha << answer << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N) on average, where N represents the number of elements in nums. Every element requires one average O(1) Hash Map lookup and one average O(1) update.

Space Complexity: O(N), because the Hash Map can store one latest index for every distinct array value.

Optimal Approach

The Better Approach reduces the average running time to linear, but the Hash Map can retain values whose stored indices already lie outside the allowed distance. Such entries cannot form a valid pair with the current or any later index.

A Hash Set named window stores values belonging only to the active range of previous K indices. The name window represents the sliding section of the array currently eligible for comparison. Before processing index i, the set contains values from indices max(0, i - K) through i - 1.

A successful membership lookup therefore confirms two facts at once: an equal value has appeared earlier, and the corresponding occurrence lies within the allowed distance. Exact indices become unnecessary because the active window already enforces the distance condition.

Algorithm

  • Return false when N < 2 or K = 0, since no two distinct indices can have a distance of zero.

  • Initialize an empty Hash Set window to represent values stored within the previous K valid positions. Membership inside window acts as both duplicate detection and distance validation.

  • Traverse every index i from 0 to N - 1.

  • Search for nums[i] inside window.

  • Return true when nums[i] already exists, because the matching occurrence belongs to one of the previous K indices.

  • Insert nums[i] into window after an unsuccessful membership check, making the current value available for upcoming indices.

  • Remove nums[i - K] when i >= K. Perform the removal after checking the current index because index i - K remains a valid candidate for index i, but falls outside the allowed range for index i + 1.

  • Return false after the complete traversal finds no nearby duplicate.

Dry Run

k

k

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Maintains values from the previous k indices. */
bool containsNearbyDuplicate(vector<int>& nums, int k) {
int n = nums.size();
// Handle cases without any valid distinct pair.
if (n < 2 || k <= 0) {
return false;
}
// Store values inside the active index window.
unordered_set<int> window;
// Process every array value once.
for (int i = 0; i < n; i++) {
// Detect a matching value inside the valid window.
if (window.find(nums[i]) != window.end()) {
return true;
}
// Add the current value to the active window.
window.insert(nums[i]);
// Remove the oldest value before the next step.
if (i >= k) {
window.erase(nums[i - k]);
}
}
// No valid duplicate pair exists.
return false;
}
};
// Driver code to execute the solution.
int main() {
vector<int> nums = {1, 2, 3, 1};
int k = 3;
Solution solution;
bool answer =
solution.containsNearbyDuplicate(nums, k);
cout << boolalpha << answer << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N) on average, where N represents the number of elements in nums. Every value is inserted, searched, and removed at most once through average O(1) Hash Set operations.

Space Complexity: O(min(N, K)), where K represents the maximum allowed index distance. The Hash Set retains only values belonging to the active window of at most K previous positions.

FAQs about Contains Duplicate II

1. Why is only the most recent index stored in the Hash Map?

The most recent occurrence produces the smallest distance from every future occurrence. When the latest index lies farther than K positions away, every older index also lies farther than K positions away.

2. Why does the Optimal Approach use a Hash Set instead of a Hash Map?

The active sliding window already guarantees the required index distance. Only value membership remains necessary, so storing exact indices becomes unnecessary.

3. What happens when K is 0?

Two distinct indices always have a distance of at least 1. Therefore, no valid pair can exist when K = 0.

4. Why is the oldest value removed after checking the current value?

A value exactly K positions behind the current index still forms a valid pair. Removal before the current comparison would incorrectly discard a valid candidate.

5. Can a plain Hash Set work without maintaining a sliding window?

No. A Hash Set containing every previously processed value can detect duplicates but cannot confirm the required index distance. Removing values outside the last K positions adds the missing distance guarantee.

6. Does hash-based lookup always take O(1) time?
Hash Set and Hash Map operations take O(1) average time. Severe hash collisions can produce slower worst-case behaviour, although standard interview analysis uses average-case hashing complexity.

HashingArrays

Read Similar Blogs

HashingData Structures

Count Distinct Elements

Given an integer array arr[] , return the count of all distinct elements in the array. Input: arr = [10, 20, 20, 10, 30, 10] Output: 3 Explanation: The different values are 10 , 20 , and 30 . 10 an...

87.7k
Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1 2 3 , then sec...

72.4k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cell...

79.8k
Comments0