Contains Duplicate

The problem

You are given an array nums of whole numbers. Call its length n. Return true if some value appears in it at least twice. Return false if every value appears only once.

Example 1

Input: nums = [3, 8, 1, 6, 2, 8]

Output: true

The value 8 appears twice, at index 1 and at index 5.

nums

308112632485

Example 2

Input: nums = [5, 2, 9, 4]

Output: false

All four values are different.

Example 3

Input: nums = [7]

Output: false

A single number has nothing to repeat with.

Constraints

• 1 ≤ n ≤ 100,000
• −1,000,000,000 ≤ nums[i] ≤ 1,000,000,000

Clarifying questions

Do we need to say which value repeats?

No. Only true or false. So we can stop at the first repeat we find.

Can the numbers be negative?

Yes. That rules out using the value as an index into a plain array. A hash set handles any value.

Is the array sorted?

No. If it were, equal values would already sit next to each other.

May we change the array?

Usually yes. That matters for the sorting approach, which sorts the array in place.

Spot the pattern

The question is “have I seen this value before?”, asked once for every number. Scanning back over the earlier numbers to answer it is slow. A hash set remembers what we have seen and answers that question in one step. That is the hashing pattern: spend memory so you never search twice.

Solutions

Brute forceO(n²)Sort firstO(n log n)Hash setO(n)

Show all

Brute force O(n²)

The idea

Compare each number with every number to its right. If any pair is equal, return true. If no pair is equal, return false. We never need to look left, because that pair was already checked from the other side.

This is correct, but slow. With n numbers there are about n × n / 2 pairs.

Walkthrough

nums

308112632485

1. for i in range(len(nums)):
2. for j in range(i + 1, len(nums)):
3. if nums[i] == nums[j]:
4. return True
5. return False

Compare every number with every number to its right. Stop at the first pair that matches.

← BackStep →Play1 / 10

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Brute force: compare every pair of numbers.
    // About n * n / 2 pairs, so O(n^2) time and O(1) extra memory.
    public boolean containsDuplicate(int[] nums) {
        int numsLength = nums.length;
        for (int i = 0; i < numsLength; i++) {
            // Only look to the right: the pairs to the left were checked
            // when the left number was i.
            for (int j = i + 1; j < numsLength; j++) {
                if (nums[i] == nums[j]) return true;
            }
        }
        return false;
    }
}

Big O

Time O(n²)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit line compares one pair. It sits inside two loops, so it runs again and again. Each run is one comparison, which does not grow with n, so each run counts as 1 step.

   1. for i in range(len(nums)):
   2. for j in range(i + 1, len(nums)):
   3. if nums[i] == nums[j]:
   4. return True
   5. return False

2. 2 Count the runs on Example 1

   Example 1 found the two 8s after 9 comparisons: 5 for i = 0 and 4 for i = 1.

   But Big O counts the worst case, and the worst case is an array with no repeat at all. Then no pair ends the search early, and every one of the 5 + 4 + 3 + 2 + 1 = 15 pairs gets compared.

   i	0	1	2	3	4	5
   compared	5	4	0	0	0	0
   worst case	5	4	3	2	1	0

   worst case, no match

   5 + 4 + 3 + 2 + 1 = 15

3. 3 Write the count for any n

   With n numbers and no repeat, number 0 is compared with n − 1 others, number 1 with n − 2, and so on down to 1:

   (n − 1) + (n − 2) + … + 1 = n × (n − 1) / 2 = ½n² − ½n

   Check it with Example 1: 6 × 5 / 2 = 15.

4. 4 Keep only the part that grows fastest

   • Drop the −½n. Next to ½n² it soon stops mattering. At n = 100, ½n² is 5,000 and ½n is 50.
   • Drop the ½. Halving every count does not change how fast the count grows. When n doubles, the work still grows 4 times.

   What is left is n².

   So the time is O(n²).

5. S Space: count the extra memory the same way

   The code creates only i and j. That is 2 variables for 6 numbers or for 100,000 numbers, so the space is O(1).

   ij

Sort first O(n log n)

The idea

Two equal numbers can sit far apart, like the two 8s in Example 1. Sorting fixes that. After a sort, equal numbers always land right next to each other.

So sort the array, then walk it once and compare each number with the one just before it. If any two neighbors are equal, there is a repeat. If no neighbors match, there is none, because a copy of a number could only be its neighbor.

Walkthrough

nums

308112632485

1. nums.sort()
2. for i in range(1, len(nums)):
3. if nums[i] == nums[i - 1]:
4. return True
5. return False

The input as given. Equal numbers can sit far apart, like the two 8s at index 1 and 5.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Sort first: equal numbers end up side by side, so one pass over
    // neighbors finds them. The sort costs O(n log n) and dominates.
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++) {
            // After sorting, a copy of nums[i] can only sit right before it.
            if (nums[i] == nums[i - 1]) return true;
        }
        return false;
    }
}

Big O

Time O(n log n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Two lines do the work. The sort on line 1 is one line, but it is not one step: a good sort needs about n × log₂ n steps to put n numbers in order. The neighbor check on line 3 sits inside one loop and costs 1 step per run.

   1. nums.sort()
   2. for i in range(1, len(nums)):
   3. if nums[i] == nums[i - 1]:
   4. return True
   5. return False

2. 2 Count the runs on Example 1

   Example 1 has 6 numbers. The sort takes about 6 × log₂ 6 ≈ 6 × 2.6 ≈ 16 steps. The scan then compares neighbors at most 5 times, once for each i from 1 to 5.

   part	sort	scan
   steps on Example 1	about 6 × log₂ 6 ≈ 16	5 neighbor checks

3. 3 Write the count for any n

   For n numbers, the sort costs about n log n and the scan costs at most n − 1:

   n log n + (n − 1)

   Check it with Example 1: about 16 + 5 = 21 steps.

4. 4 Keep only the part that grows fastest

   • Drop the n − 1. log n keeps growing with n, so n log n always ends up bigger than n. The sort is the biggest part, and the scan only adds a smaller part next to it.

   What is left is n log n.

   So the time is O(n log n).

5. S Space: count the extra memory the same way

   The scan creates only i, so the code itself needs O(1) extra memory. One honest note: the sort inside your language may use some memory of its own. Java and C# sort plain numbers in place with about log n extra. Python’s sort can use up to n / 2 extra slots.

   i

Hash set O(n)

The idea

Walk the array once. Keep a hash set of the numbers seen so far. A hash set is a collection that can tell you “is this value inside?” in one step on average, however many values it holds.

For each number, ask the set first. If the number is already there, we have found a repeat. If not, add it, so a later copy can find it.

Why it never misses a repeat: when the second copy of any value arrives, the first copy is already in the set, so the check on that step must say yes.

Walkthrough

nums

308112632485

seen

empty

1. seen = set()
2. for number in nums:
3. if number in seen:
4. return True
5. seen.add(number)
6. return False

Start with an empty set. A set answers "have I seen this number?" in one step.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Hash set: remember every number seen so far.
    // One pass with O(1) lookups, so O(n) time and O(n) memory.
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int number : nums) {
            // A set lookup is one step on average, so this check is cheap.
            if (seen.contains(number)) return true;
            seen.add(number);
        }
        return false;
    }
}

Big O

Time O(n)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Each run of the loop does one set lookup and at most one set add. Both take one step on average, so each run counts as 1 step. There is one loop, and nothing inside it loops again.

   1. seen = set()
   2. for number in nums:
   3. if number in seen:
   4. return True
   5. seen.add(number)
   6. return False

2. 2 Count the runs on Example 1

   Example 1 has 6 numbers. The loop runs once per number, and the 6th run finds the second 8.

   6 runs. With no repeat, the loop would also run 6 times and then return false.

   run	1	2	3	4	5	6
   number	3	8	1	6	2	8
   in seen?	no	no	no	no	no	yes
   then	add	add	add	add	add	return

3. 3 Write the count for any n

   The loop visits each number at most once, so in the worst case it runs:

   n times

   Check it with Example 1: 6 numbers, 6 runs.

4. 4 Keep only the part that grows fastest

   There is nothing to drop. The count is already n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The set is the extra memory. With no repeat, every number goes into it, so it ends up holding n values. The space is O(n). This is the trade: the set costs memory and saves the second loop.

   seen (up to n numbers)number

Common mistake

Adding before checking

If you add number to the set and then ask whether number is in it, the answer is always yes. Every array then looks like it has a repeat. Check first, then add.

Tested at the limits

2,000 random arrays of 1 to 8 numbers from a tiny range, so a repeat shows up about half the time. The brute force, the sort first and the hash set gave the same answer every time.

Largest inputs	Result
100,000 numbers (the most allowed), all different, so every number is read and stored. Hash set.	0.01 s, and about 6 MB of extra memory: the set holds all 100,000 numbers, which is the O(n) space.
100,000 numbers, all different. Sort first.	0.02 s, and about 0.4 MB of extra memory: it sorts in place, and the sort borrows a little room of its own.
2,000 numbers. Brute force, about 2 million pairs.	0.05 s. At 100,000 numbers it would check 5 billion pairs, which is why the hash set matters.