Contains Duplicate II - Practice Coding Problems

Contains Duplicate II - Problem

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.

In other words, find if there are duplicate values within a window of size k.

Input & Output

Example 1 — Basic Case

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

› Output: true

💡 Note: There are two 1's at indices 0 and 3. The distance |3-0| = 3 which equals k=3, so return true.

Example 2 — Distance Too Large

$ Input: nums = [1,0,1,1], k = 1

› Output: true

💡 Note: There are two 1's at indices 2 and 3. The distance |3-2| = 1 which equals k=1, so return true.

Example 3 — No Duplicates Within k

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

› Output: false

💡 Note: No duplicate values exist within distance k=2. The closest duplicates are at distance 3.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Array with potential duplicates and distance k

Process

Check if any duplicates exist within distance k

Output

Return true if found, false otherwise

Key Takeaway

🎯 Key Insight: Use a sliding window to efficiently track recent elements and detect duplicates within the allowed distance

Asked in

a Amazon 12 Apple 8 M Microsoft 6 G Google 4

The key insight is to use a sliding window approach with a hash set to efficiently track duplicates within distance k. The optimal solution maintains a window of the most recent k elements, checking for duplicates as we slide the window. Time: O(n), Space: O(min(n,k))

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window with Hash Set	O(n)	O(min(n,k))	Maintain a window of k elements using a hash set
Brute Force - Check All Pairs	O(n×k)	O(1)	For each element, check all elements within distance k
Hash Map with Last Index	O(n)	O(n)	Store the most recent index of each element

Sliding Window with Hash Set — Algorithm Steps

Use a hash set to store elements in current window
Slide window by adding new elements and removing old ones
Return true if element already exists when adding

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with empty window set

Slide

Add new elements, remove old ones

Check

Detect duplicate when adding

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define HASH_SIZE 10007

typedef struct HashNode {
    int key;
    struct HashNode* next;
} HashNode;

bool hashContains(HashNode* table[], int key) {
    int hash = abs(key) % HASH_SIZE;
    HashNode* node = table[hash];
    while (node) {
        if (node->key == key) return true;
        node = node->next;
    }
    return false;
}

void hashInsert(HashNode* table[], int key) {
    int hash = abs(key) % HASH_SIZE;
    HashNode* node = (HashNode*)malloc(sizeof(HashNode));
    node->key = key;
    node->next = table[hash];
    table[hash] = node;
}

void hashRemove(HashNode* table[], int key) {
    int hash = abs(key) % HASH_SIZE;
    HashNode** node = &table[hash];
    while (*node) {
        if ((*node)->key == key) {
            HashNode* temp = *node;
            *node = (*node)->next;
            free(temp);
            return;
        }
        node = &(*node)->next;
    }
}

bool solution(int* nums, int numsSize, int k) {
    HashNode* window[HASH_SIZE] = {NULL};
    int windowSize = 0;
    
    for (int i = 0; i < numsSize; i++) {
        if (hashContains(window, nums[i])) {
            return true;
        }
        
        hashInsert(window, nums[i]);
        windowSize++;
        
        if (windowSize > k) {
            hashRemove(window, nums[i - k]);
            windowSize--;
        }
    }
    
    return false;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    bool result = solution(nums, numsSize, k);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array with O(1) hash set operations

✓ Linear Growth

Space Complexity

O(min(n,k))

Hash set stores at most k elements in the sliding window

⚡ Linearithmic Space

145.0K Views

Medium Frequency

~15 min Avg. Time

4.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window with Hash Set — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler