Contains Duplicate - Practice Coding Problems

Contains Duplicate - Problem

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

This is a fundamental problem that tests your understanding of data structures and algorithms for detecting duplicates efficiently.

Input & Output

Example 1 — Contains Duplicate

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

› Output: true

💡 Note: The value 1 appears at both index 0 and index 3, so there is a duplicate.

Example 2 — All Distinct

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

› Output: false

💡 Note: All elements are distinct, no duplicates found.

Example 3 — Multiple Duplicates

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

› Output: true

💡 Note: Several values appear multiple times (1, 2, 3, and 4), so there are duplicates.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Array of integers [1,2,3,1]

Process

Check for duplicate values using hash set

Output

Return true if duplicate found, false otherwise

Key Takeaway

🎯 Key Insight: Use a hash set to detect duplicates in O(n) time with constant lookup

Asked in

G Google 25 A Amazon 30 M Microsoft 20 🍎 Apple 15

The key insight is using a hash set to track seen elements in a single pass. The optimal approach is the hash set method with O(n) time and O(n) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Hash Set - Optimal Solution	O(n)	O(n)	Use a hash set to track seen elements in a single pass
Sort First Approach	O(n log n)	O(1)	Sort the array first, then check adjacent elements for duplicates
Brute Force - Compare All Pairs	O(n²)	O(1)	Compare every element with every other element to find duplicates

Hash Set - Optimal Solution — Algorithm Steps

Create an empty hash set
Iterate through each element in the array
Check if current element exists in the set
If yes, return true (duplicate found)
If no, add element to set and continue
If loop completes, return false (no duplicates)

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with empty hash set

Process

Check each element: if seen before, return true

Found

Duplicate detected when element already in set

Code -

solution.c — C

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

#define HASH_SIZE 10007

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

int hash(int value) {
    return abs(value) % HASH_SIZE;
}

bool contains(HashNode* table[], int value) {
    int index = hash(value);
    HashNode* node = table[index];
    while (node != NULL) {
        if (node->value == value) {
            return true;
        }
        node = node->next;
    }
    return false;
}

void insert(HashNode* table[], int value) {
    int index = hash(value);
    HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
    newNode->value = value;
    newNode->next = table[index];
    table[index] = newNode;
}

bool solution(int* nums, int numsSize) {
    HashNode* table[HASH_SIZE] = {NULL};
    for (int i = 0; i < numsSize; i++) {
        if (contains(table, nums[i])) {
            return true;
        }
        insert(table, nums[i]);
    }
    return false;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int nums[1000];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    bool result = solution(nums, size);
    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(n)

Hash set can store up to n elements in worst case

⚡ Linearithmic Space

125.0K Views

High Frequency

~15 min Avg. Time

3.5K 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

Hash Set - Optimal Solution — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler