Problem Statement
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.
Examples
Example 1:
Input: nums= [1, 2, 3, 4]
Output: false
Explanation: There are no duplicates in the given array.
Example 2:
Input: nums= [1, 2, 3, 1]
Output: true
Explanation: '1' is repeating.
Example 3:
Input: nums= [3, 2, 6, -1, 2, 1]
Output: true
Explanation: '2' is repeating.
Constraints:
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
Solution
The question asks one thing. Does any value appear twice?
So the real work is a lookup. For every value you read, you need to know whether you have seen it before. The three approaches below differ only in how fast that lookup is.
Read them in order, but know where they end up. Approach 1 is slow, and it is here to show why the other two exist. Approach 2 is the one to give in an interview. Approach 3 is what you use when memory is tight.
Approach 1: Brute Force
Compare every value against every value that comes after it. If two of them match, return true. If the loops finish with no match, every value is different, so return false.
This is correct and it needs no extra memory. It is also slow. The first value is compared against N - 1 others, the second against N - 2, and so on down. That is about N squared / 2 comparisons.
Here is the nested loop running on [3, 2, 6, -1, 2, 1]. Move through the steps one at a time:
Step 1. The array is [3, 2, 6, -1, 2, 1]. The brute force approach fixes one position i and compares it against every position to its right, then moves i along. The moment two values match, the answer is true and the scan can stop.
1 of 4
Code
Here is the code for this algorithm:
Complexity Analysis
Time Complexity
- Outer loop: The outer loop runs
Ntimes, whereNis the length of the input array. This gives the outer loop a time complexity of O(N). - Inner loop (nested): For each iteration of the outer loop, the inner loop runs
N - i - 1times, which decreases asiincreases. In the worst case, the inner loop will run approximately N times for the first element, N - 1 times for the second element, and so on. This results in a total time complexity for the inner loop of O(N^2).
Overall time complexity: O(N^2).
Space Complexity
- The algorithm only uses a few variables (
i,j, and boolean result), all of which require constant space. - No additional data structures are used that depend on the input size.
Overall space complexity: O(1).
Approach 2: Using Hash Set
A set is a collection that holds each value at most once, and can tell you whether it holds a value without looking through everything. That second part is what matters here.
To check whether a list holds the value 6, you have to compare 6 against every entry. There is no shortcut. A set works differently. It runs the value through a hash function, which turns the value into a slot number, and then reads that one slot. On average that is a single step, no matter how many values the set holds.
So the plan is short. Walk the array once. Before adding a value, ask the set whether it is already there. If it is, you have found a repeat and can return true straight away.
This approach works as follows:
- Create an empty set to hold the values you have already seen.
- Walk through the input array
nums, one value at a time. - For each value
x, ask the set whether it already holdsx.- If it does, return
true. That value has appeared twice. - If it does not, add
xto the set and move on.
- If it does, return
- If the walk finishes with no match, every value was different, so return
false.
Why add x to the set at all? The question never asks for a set, so this step can look like extra work. The set is your memory of what you have already read. Without it, the check on the next value would have nothing to compare against, and you would be back to scanning the array.
Here is the algorithm Walkthrough:
3 is not in the set yet, so it is added
1 of 6
Code
Here is the code for this algorithm:
Complexity Analysis
Time Complexity
- Loop through the array: The algorithm iterates over the array
numsonce. This gives a time complexity of O(N), whereNis the number of elements in the array. - HashSet operations: For each element, the algorithm performs a
HashSet.add()operation. On average, adding or checking elements in aHashSethas a time complexity of O(1) due to its underlying hash table structure.
Overall time complexity: O(N) on average, where N is the number of elements in the array. In the worst case, when every element lands in the same hash bucket, it is O(N^2). That worst case needs an input with no duplicates at all, so the early return never fires and every lookup walks a bucket holding everything read so far. Real inputs do not behave this way, which is why the average is the number that gets quoted.
Space Complexity
- HashSet storage: The algorithm uses a
HashSetto store unique elements. In the worst case, when all elements are unique, theHashSetwill containNelements. - This results in a space complexity of O(N), where
Nis the number of unique elements in the array.
Overall space complexity: O(N).
A shorter variant, and what it costs. Many people reach for a one-liner here: build a set from the whole array and compare its size with the array length.
return len(set(nums)) != len(nums)
It is correct, and it is the same O(N) time and O(N) space. What it gives up is the early return. The loop
above stops the moment it sees a repeat, so on [1, 1, ...] with a million elements it reads two of them.
The one-liner always builds the whole set first, so it reads all million. Same complexity, different work
on the inputs that repeat early.
Both are fine answers in an interview. Say the one-liner, then mention that the explicit loop can exit early, and you have shown you know the difference rather than just the shorter syntax.
Approach 3: Sorting
Sorting puts equal values next to each other. That is the property this approach uses.
So sort the array first, then walk it once and compare each value with the value right after it. If two neighbours match, return true. If the walk finishes with no match, return false.
This approach needs no set. What it costs instead is the sort, which is slower than one pass, and it changes the order of the input array.
Code
Here is the code for this algorithm:
Complexity Analysis
Time Complexity
- The algorithm first sorts the array using
Arrays.sort(), which has a time complexity of O(N \log N), whereNis the number of elements in the array. - After sorting, the algorithm performs a single pass through the array to compare adjacent elements. This step takes O(N) time.
- Therefore, the overall time complexity is dominated by the sorting operation, making it O(N \log N).
Space Complexity
- The space complexity of the sorting algorithm depends on the implementation of
Arrays.sort(). In the case of primitive types likeint[], it uses a variant of the quicksort algorithm, which has a space complexity of O(\log N) due to the recursion stack for in-place sorting. - The algorithm itself only uses a constant amount of extra space for the index variable and the loop, which does not depend on the size of the input.
Thus, the overall complexity is:
- Time Complexity: O(N \log N)
- Space Complexity: O(\log N)
Which approach to give in an interview
Approach 2, the hash set, is the one to give. It runs in O(N) time in a single pass, and it is the shortest to write correctly under pressure. Use approach 3, sorting, only when memory is tight. It trades O(N) time for O(N \log N) and drops the extra memory to whatever the sort itself needs, which is O(\log N) for a typical library sort rather than O(1). If the requirement is strictly constant extra space, name an in-place sort such as heapsort, because most library sorts are not in place: Python's Timsort can allocate O(N). Approach 1 is here to show why the other two exist, not as an answer to offer.