Log inSign up
mediumLeetCodeNot Started

Find the Duplicate Number

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return *this repeated number*.

You must solve the problem without modifying the array nums and uses only constant extra space O(1).

---

### Constraints: - 1 <= n <= 10^5 - nums.length == n + 1 - 1 <= nums[i] <= n - All integers in nums appear only once except for precisely one integer which appears two or more times.

---

### Follow-up Questions: - How can we prove that at least one duplicate number must exist in nums? (Pigeonhole Principle) - Can you solve the problem in linear runtime O(n) and constant auxiliary space O(1)?

Example 1 · Example 1 (Repeated Value in Mid-Array):

Input: nums = [1, 3, 4, 2, 2]
Output: 2
Explanation: The integer 2 appears twice in the array at index 3 and index 4. The single repeated number is 2.

Example 2 · Example 2 (Repeated Boundary Value):

Input: nums = [3, 1, 3, 4, 2]
Output: 3
Explanation: The integer 3 appears at index 0 and index 2. The duplicate number is 3.

Example 3 · Example 3 (Multiple Repeated Occurrences):

Input: nums = [3, 3, 3, 3, 3]
Output: 3
Explanation: The integer 3 is the only value in nums, appearing multiple times. Output is 3.

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Array Indexing
  • Basic Time & Space Complexity Analysis

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Map array index-value relationships to directed functional graphs.
  • Master Floyd's Cycle Detection (Tortoise and Hare) algorithm on implicit pointers.
  • Derive the mathematical proof for why Phase 2 pointer convergence yields the cycle entrance.
  • Implement clean, standalone solutions across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Values are constrained to the range [1, N] matching the array indices.
  • Array modification is strictly prohibited (no sorting, no sign-negation marker).
  • Memory is strictly constrained to O(1) auxiliary space.
  • Finding cycle entrance in state space / functional graphs.

Algorithmic Decision Tree:

  • If array modification allowed: Negative index tagging achieves O(N) time and O(1) space.
  • If space allowed O(N): Hash Set lookup achieves O(N) time.
  • If strictly read-only array and O(1) space: Floyd's Cycle Detection (Tortoise and Hare) is mandatory.

Connected Patterns:

Linked List Cycle II: Finding the cycle entry node.First Missing Positive: Value-to-index mapping.Circular Array Loop: Cycle validation in directed arrays.

1. Hash Set / Sorting

Intuition

Use a Hash Set to track seen numbers, or sort the array and look for adjacent duplicates.

Algorithm

  1. 1. Initialize a hash set seen.
  2. 2. Iterate through each num in nums.
  3. 3. If num is already in seen, return num.
  4. 4. Otherwise, insert num into seen.
  5. 5. Uses O(N) space or modifies the array in O(N log N) time.

Brute Force Nested Pairwise Comparison Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 3, 4, 2, 2]
Current operationSTEP 1 OF 6
Inspect i=0: Value 1 has no duplicate
Visual state
Values and pointers at this exact step
table
S
1
3
4
2
2
0
↑ i=0 (val 1)
1
2
3
4
i0
Val1
Duplicate FoundNO
Variables at this step
i
0
Val
1
Duplicate Found
NO
Check / comparison
Compare nums[0] (1) with all j in {1..4}. None equal 1.
Decision / next transition
Advance i to index 1.
Why this step matters

Inspect i=0: Value 1 has no duplicate. Advance i.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 int findDuplicate(vector<int>& nums) {
17 unordered_set<int> seen;
18 for (int num : nums) {
19 if (seen.count(num)) return num;
20 seen.insert(num);
21 }
22 return -1;
23 }
24};
25
26int main() {
27 Solution sol;
28 vector<int> nums = {1, 3, 4, 2, 2};
29 cout << "Duplicate Number: " << sol.findDuplicate(nums) << endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(N) — A single linear pass with O(1) set lookups takes O(N) time.
  • Space complexity: O(N) — Hash Set stores up to N distinct elements, requiring O(N) space.

Why Brute Force Doesn't Scale:

Since nums[i] is between 1 and n, 0 is never in the range. This ensures index 0 is always outside the cycle and serves as a valid list head. When slow moves by 1 step (slow = nums[slow]) and fast moves by 2 steps (fast = nums[nums[fast]]), they must meet inside the loop after at most N steps. The mathematical distance from the start to the cycle entrance equals the distance from the intersection point to the cycle entrance.

For N = 100,000: Binary Search performs ~1,700,000 checks. Floyd's cycle detection finishes in ~150,000 operations.

2. Binary Search on Value Range [1, n]

Intuition

Apply binary search on the range of possible answers [1, n] by counting how many elements are <= mid.

Algorithm

  1. 1. Initialize low = 1, high = n (where n = nums.length - 1).
  2. 2. While low < high: - mid = low + (high - low) / 2. - Count how many numbers in nums are <= mid. - If count > mid, search left: high = mid. - Else search right: low = mid + 1.
  3. 3. Return low.

Hash Set Visited Frequency Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 3, 4, 2, 2]
Current operationSTEP 1 OF 6
Inspect 1: 1 is not in set
Visual state
Values and pointers at this exact step
table
Input array
S
1
3
4
2
2
0
↑ i=0 (val 1)
1
2
3
4
Hash map state
Execution state
seen{ 1 }
seen = { 1 }. Advance to index 1.
Variables at this step
seen
{ 1 }
Check / comparison
Is 1 in seen set? NO. Insert 1: seen = { 1 }.
Decision / next transition
seen = { 1 }. Advance to index 1.
Why this step matters

Inspect 1: 1 is not in set. Add to set.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 int findDuplicate(vector<int>& nums) {
17 int low = 1, high = nums.size() - 1;
18 while (low < high) {
19 int mid = low + (high - low) / 2;
20 int count = 0;
21 for (int num : nums) {
22 if (num <= mid) count++;
23 }
24 if (count > mid) high = mid;
25 else low = mid + 1;
26 }
27 return low;
28 }
29};
30
31int main() {
32 Solution sol;
33 vector<int> nums = {1, 3, 4, 2, 2};
34 cout << "Duplicate Number: " << sol.findDuplicate(nums) << endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(N log N) — Binary search takes log N iterations. In each iteration, we do a linear scan of N elements to count. Total time = O(N log N).
  • Space complexity: O(1) — Only uses integer loop variables (low, high, mid, count). Space is O(1).

3. Floyd's Cycle Detection (Tortoise & Hare)

Intuition

Treat the array as a linked list where value nums[i] is a pointer to the next index, and find the entry point of the cycle.

Algorithm

  1. 1. Phase 1 (Detect Intersection): Initialize slow = nums[0], fast = nums[0]. Advance slow = nums[slow] and fast = nums[nums[fast]] until slow == fast.
  2. 2. Phase 2 (Find Entrance): Reset slow = nums[0]. Keep fast at the intersection. Advance both slow = nums[slow] and fast = nums[fast] by 1 step simultaneously.
  3. 3. When slow == fast, their meeting point is the duplicate number.
  4. 4. Return slow. Operates in O(N) time and O(1) space.

Floyd's Tortoise and Hare Cycle Detection Trace

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
InputINPUT nums = [1, 3, 4, 2, 2]
Current operationSTEP 1 OF 7
Hop 1: Slow takes 1 hop to nums[0] = 1
Visual state
Values and pointers at this exact step
pointers
S
1
3
4
2
2
0
↑ Start
1
2
3
4
Variables at this step
slow
nums[0] = 1
fast
nums[1] = 3
Phase
Cycle Detection
Check / comparison
Phase 1: Initialize slow = nums[0] = 1, fast = nums[nums[0]] = nums[1] = 3.
Decision / next transition
slow = 1, fast = 3.
Why this step matters

Hop 1: Slow takes 1 hop to nums[0] = 1. Fast takes 2 hops to nums[nums[0]] = nums[1] = 3.

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 int findDuplicate(vector<int>& nums) {
17 int slow = nums[0];
18 int fast = nums[0];
19
20 // Phase 1: Find intersection point
21 do {
22 slow = nums[slow];
23 fast = nums[nums[fast]];
24 } while (slow != fast);
25
26 // Phase 2: Find entrance of cycle
27 slow = nums[0];
28 while (slow != fast) {
29 slow = nums[slow];
30 fast = nums[fast];
31 }
32
33 return slow;
34 }
35};
36
37int main() {
38 Solution sol;
39 vector<int> nums = {1, 3, 4, 2, 2};
40 cout << "Duplicate Number: " << sol.findDuplicate(nums) << endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(N) — Phase 1 finds cycle intersection in O(N) steps. Phase 2 finds cycle entrance in O(N) steps. Total time is O(N).
  • Space complexity: O(1) — Only two pointer variables (slow, fast) are used. Auxiliary space is strictly O(1).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.1. Hash Set Lookup (Brute Force)O(N)O(N)Insert elements into a Hash Set until a duplicate key is encountered.Uses O(N) auxiliary heap memory for hash table.
2.2. Binary Search on Value Range (Better)O(N log N)O(1) auxiliaryCount elements <= mid in range [1, n]. If count > mid, duplicate lies in [low, mid].Requires log(N) full array scans.
3.3. Floyd's Cycle Detection (Optimal)OptimalO(N)O(1) auxiliaryTreat array as linked list i -> nums[i]. Find cycle entrance with slow/fast pointers.Optimal runtime and memory bounds.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Modifying array with sign negation (e.g. nums[x] = -nums[x]): While O(1) space, this violates the problem's strict read-only constraint.

Pitfall 2:

Initializing fast = nums[nums[0]] before the while condition: Can cause early termination if slow == fast initially.

Pitfall 3:

Using binary search incorrectly without value-based counting.

Crucial Edge Cases to Validate:

  • Smallest input [1, 1]: Handled immediately with cycle on element 1.
  • Duplicate appearing 3 or more times: Floyd's algorithm reliably identifies the cycle entrance regardless of duplicate multiplicity.
  • Array with elements sorted vs unsorted: Works identically as traversal is governed by value pointers.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clearly explain why index 0 is guaranteed to be outside the cycle (no value in nums can be 0).
  2. Explain the 2 phases: Phase 1 detects presence of cycle, Phase 2 finds cycle entrance.
  3. Mention Pigeonhole Principle to establish that a duplicate is guaranteed mathematically.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for undefined?

2.Why is the brute force approach suboptimal for large inputs in undefined?

3.Which data structure or technique enables the optimal solution for undefined?

Back to DSA Sheet