Given an integer array nums containing N elements, return true when at least one value occurs more than once. Return false when every value occurs exactly once.
Example 1
Input: nums = [1, 2, 3, 1]
Output: true
Explanation: Value 1 occurs at indices 0 and 3, so a duplicate exists.
Example 2
Input: nums = [1, 2, 3, 4]
Output: false
Explanation: Every value occurs exactly once, so no duplicate exists.
Brute Force Approach
Duplicate detection starts with a simple condition: two different indices must contain the same value. Without sorted order or extra memory, no previous information can eliminate a later comparison.
Pairwise comparison covers every unique pair of indices. A matching pair ends the search immediately. Completion of all pair checks without equality confirms that every value is distinct.
Algorithm
Return
falsewhenN < 2, since a duplicate requires at least two array positions.Traverse index
ifrom0toN - 2.For every index
i, traverse indexjfromi + 1toN - 1. Starting fromi + 1avoids self-comparison and repeated pair checks.Compare
nums[i]withnums[j].Return
trueimmediately when equal values appear at two different indices.Return
falseafter every possible pair remains different.
Dry Run
contains duplicate
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Checks duplicate values through pairwise comparison. */ bool containsDuplicate(vector<int>& nums) { int n = nums.size(); // A duplicate requires at least two elements. if (n < 2) { return false; } // Compare every unique pair of indices. for (int i = 0; i < n - 1; i++) { // Start after i to avoid // repeated pair comparisons. for (int j = i + 1; j < n; j++) { // Equal values at different // indices confirm a duplicate. if (nums[i] == nums[j]) { return true; } } } // No matching pair exists. return false; }};// Driver code to execute the solution.int main() { vector<int> nums = {1, 2, 3, 1}; Solution solution; bool answer = solution.containsDuplicate(nums); cout << boolalpha << answer << endl; return 0;}Complexity Analysis
Time Complexity: O(N²), where N represents the number of elements in nums. At most N × (N - 1) / 2 pairs are compared.
Space Complexity: O(1), because only the array size and two loop indices are stored.
Better Approach
Pairwise comparison spends quadratic time checking values located at different positions. Sorting places equal values in consecutive positions, converting a global duplicate search into a sequence of adjacent comparisons.
Sorting a copy preserves the original array. After ascending order is formed, every repeated value belongs to an adjacent equal pair. A single left-to-right traversal can therefore detect a duplicate.
Algorithm
Return
falsewhenN < 2, since fewer than two elements cannot form a duplicate pair.Create
sortedNumsas a separate working copy ofnums. Sorting is required to place equal values next to each other, while the separate copy prevents the original input array from being reordered.Sort
sortedNumsin ascending order, placing equal values next to each other.Traverse index
ifrom1toN - 1.Compare
sortedNums[i]withsortedNums[i - 1].Return
trueimmediately when two adjacent values are equal.Return
falseafter the complete traversal finds no equal adjacent pair.
Dry Run
l
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Checks duplicate values after sorting a separate array copy. */ bool containsDuplicate(vector<int>& nums) { int n = nums.size(); // A duplicate requires at least two elements. if (n < 2) { return false; } // Create a working copy because sorting is // required without reordering the input array. vector<int> sortedNums = nums; // Place equal values in adjacent positions. sort( sortedNums.begin(), sortedNums.end() ); // Compare every adjacent pair. for (int i = 1; i < n; i++) { // Equal adjacent values confirm // the presence of a duplicate. if ( sortedNums[i] == sortedNums[i - 1] ) { return true; } } // No equal adjacent pair exists. return false; }};// Driver code to execute the solution.int main() { vector<int> nums = {1, 2, 3, 1}; Solution solution; bool answer = solution.containsDuplicate(nums); cout << boolalpha << answer << endl; return 0;}Complexity Analysis
Time Complexity: O(N log N), where N represents the number of elements in nums. Sorting requires O(N log N) time, followed by an O(N) adjacent-element traversal.
Space Complexity: O(N), because a copy containing all N elements is created to preserve the original array.
Optimal Approach
Sorting removes repeated pair comparisons but still arranges the complete array, even though duplicate detection does not require sorted output. Only earlier occurrence information matters during traversal.
An initially empty Hash Set can record processed values. A successful membership lookup proves the presence of a duplicate. An unsuccessful lookup is followed by insertion. Average constant-time lookup and insertion reduce duplicate detection to a single traversal.
Algorithm
Return
falsewhenN < 2, since fewer than two values cannot contain a duplicate.Initialize an empty Hash Set
seento act as a lookup history of values processed so far. An existing value insideseenconfirms that the current value has already appeared at an earlier index.Traverse every value
numinnums.Search for
numinsideseen.Return
trueimmediately whennumalready exists inseen, because an earlier occurrence has already been processed.Insert
numintoseenwhen no earlier occurrence exists.Return
falseafter the complete traversal finishes without a repeated value.
Dry Run
contain duplicate
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Checks duplicate values using a lookup history of processed values. */ bool containsDuplicate(vector<int>& nums) { int n = nums.size(); // A duplicate requires at least two elements. if (n < 2) { return false; } // Keep processed values as lookup history // for detecting an earlier occurrence. unordered_set<int> seen; // Process every array value once. for (int num : nums) { // An existing entry proves that num // appeared at an earlier index. if ( seen.find(num) != seen.end() ) { return true; } // Record num for later duplicate checks. seen.insert(num); } // Every value appears exactly once. return false; }};// Driver code to execute the solution.int main() { vector<int> nums = {1, 2, 3, 1}; Solution solution; bool answer = solution.containsDuplicate(nums); cout << boolalpha << answer << endl; return 0;}Complexity Analysis
Time Complexity: O(N) on average, where N represents the number of elements in nums. Every value is processed once, and each Hash Set lookup and insertion takes O(1) average time.
Space Complexity: O(N), because the Hash Set can store all N values when every array element is distinct.
FAQs about Contains Duplicate
1. Can sorting preserve the original array?
Yes. Sorting a separate copy preserves nums. Copy creation requires O(N) extra space.
2. Can O(N) time and O(1) extra space be achieved?
For unrestricted integer values under standard comparison and hashing assumptions, both guarantees are generally unavailable together. A bounded value range can allow a bitset or frequency array, with extra space based on the range size.
3. Why is an immediate return valid after one matching pair?
The required output only represents duplicate existence. One equal pair already proves a true result, so remaining values cannot change the answer.
4. Can an empty array or a single-element array contain a duplicate?
No. A duplicate requires at least two positions containing the same value. Arrays containing fewer than two elements always return false.
5. Does a Hash Set guarantee constant-time operations?
No strict universal guarantee exists. Average lookup and insertion require O(1) time, while severe hash collisions can reduce performance. Standard interview analysis uses average-case O(1) Hash Set operations.
Be the first to add a comment.