Crack the Backend

Problem Statement

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

We need to detect if there is a duplicate. A set is the natural structure: as we scan, if we see a number that is already in the set, we have a duplicate. Otherwise add the number to the set. O(n) time, O(n) space. Alternatively, sort and check adjacent pairs (O(n log n) time, O(1) extra space if in-place sort).

Key Observations

Set: Set<Integer> set. For each x in nums: if set.contains(x) (or if !set.add(x) — add returns false if the element was already present), return true. Otherwise set.add(x). After the loop, return false.
Sort: Sort nums; for i = 0..n-2, if nums[i] == nums[i+1] return true. Return false.

Approach

High-level: Set<Integer> set = new HashSet<>(). For each x in nums: if !set.add(x) return true (already seen). Return false.

Steps:

Set<Integer> set = new HashSet<>(). For each int x : nums: if !set.add(x) return true.
return false.

Implementation

Java

public boolean containsDuplicate(int[] nums) {
    Set<Integer> set = new HashSet<>();

    for (int x : nums) {
        if (set.contains(x)) {
            return true;
        }

        set.add(x);
    }

    return false;
}

Test Cases

Example 1

Input

nums = [1,2,3,1]

Expected

true

Explanation

1 appears twice.

Complexity Analysis

Time: O(n).
Space: O(n).

Follow-ups

Contains duplicate II: two same values within distance k (sliding window + set).