Detect Duplicate Element — Problem Statement & Solution Guide
Problem Description
Given an array of integers nums of length n, where each element is an integer in the range [1, n - 1] inclusive. There is guaranteed to be at least one duplicate integer in the array. Find and return this duplicate number without modifying the original array and using only constant extra space O(1). Note: The output should be the first occurrence of the duplicate number.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Detect Duplicate Element"
WHY DOES IT MATTER?
Candidates tackling this duplicate detection problem often default to sorting the array or using a hash set, failing to realize that sorting violates the read-only constraint while the hash set violates the O(1) auxiliary space constraint. Another common pitfall is attempting bitwise XOR, which fails here because a single duplicate can appear more than twice, or other elements might be missing entirely, skewing the binary cancellations.
OPTIMIZATION CHALLENGE
The challenge is to find the duplicate element in O(N) time while adhering to O(1) space complexity and treating the input array as strictly read-only, which rules out classic approaches like sorting, hashing, or index-based sign-flipping.
REAL-WORLD CONNECTION
This pointer-based cycle-detection paradigm is directly applied in database transaction systems to identify deadlocks in wait-for graphs and in tracing garbage collectors to detect cyclic object references without allocating extra tracking memory.
The interviewer is testing your ability to abstract one data structure (an array of index-value mappings) into another (a functional directed graph) and apply topological cycle-detection principles to bypass physical memory constraints.
COMPLEXITY AT A GLANCE
O(N)O(1)Core Theory — Why This Approach?
To solve the Detect Duplicate Element problem within O(1) extra space and without modifying the input array, we must reinterpret the array as a directed graph where each index i points to the node nums[i]. Because the values are strictly restricted to the range [1, n-1] within an array of size n, index 0 is guaranteed to never be pointed to by any element, acting as a natural entry point or 'head' of a virtual linked list. Since there is at least one duplicate value, multiple indices must point to that same value, transforming our linear traversal into a cyclic structure where the duplicate value represents the entrance to a cycle.
Floyd's Cycle Finding Algorithm (Tortoise and Hare) is the optimal mechanism here because it allows us to navigate this virtual linked list using two pointers moving at different speeds (one step versus two steps). When the slow and fast pointers meet, we confirm the existence of a cycle; resetting one pointer to the start index 0 and advancing both at a matching pace of one step per iteration guarantees they will meet precisely at the cycle's entrance. This entrance index represents the first duplicate integer, satisfying the O(1) space and read-only array constraints perfectly.
Interview Questions on This Problem
Q1Why is index 0 guaranteed to be the starting node (head) of our virtual linked list in this problem?
Since the array elements are strictly in the range [1, n-1], no element in the array can ever have a value of 0. This means no index i can point back to index 0 (since nums[i] is never 0), making index 0 a guaranteed entry point that lies outside any cycle, ensuring we can traverse into the cycle from the start.
Q2Prove why the time complexity of the Floyd's algorithm phase of this solution remains O(N).
During the detection phase, the fast pointer moves at twice the speed of the slow pointer; since the cycle length is at most N, the fast pointer will catch up to the slow pointer in at most N steps. In the second phase, both pointers move at equal speed from their respective starting points to the cycle entrance, covering at most N steps, resulting in a total time complexity strictly bounded by O(N) operations.
Q3How does the algorithm behave if there are multiple duplicates of the same number (e.g., [2, 2, 2, 2])?
The algorithm still works correctly because all indices pointing to the value 2 will direct the path to index 2. The virtual list structure will simply have a self-loop or a direct cycle at node 2, and the pointers will meet and resolve the duplicate value 2 as the cycle entrance without infinite loops.
Q4How would you modify the approach if the array elements were in the range [0, n-1] and index 0 could be part of the cycle?
If elements can be 0, index 0 is no longer a guaranteed external head node. To resolve this, we can shift all values conceptually by treating the pointer transition as i -> nums[i] + 1, or offset the indices to create a virtual node outside the valid range to act as the head, ensuring the cycle detection logic remains intact.
Examples
Input
[1, 2, 3, 2, 4, 5]
Output
2
Explanation: The array contains elements [1, 2, 3, 2, 4, 5] in the range [1, 5]. The integer 2 appears twice (at index 1 and index 3), while all other numbers appear exactly once. Hence, 2 is returned as the duplicate.
Input
[1, 1, 2, 3, 4, 5]
Output
1
Explanation: The array contains elements [1, 1, 2, 3, 4, 5] in the range [1, 5]. The integer 1 appears twice (at index 0 and index 1). Hence, 1 is returned as the duplicate.
Constraints
- 2 <= nums.length <= 10^5
- 1 <= nums[i] < nums.length
- All integers in nums except one appear once or more.
Optimal Approach & Strategy
Treat the array as a linked list where each index i points to node nums[i]. Since elements are in the range [1, n-1], a cycle must exist. Use Floyd's Cycle Finding Algorithm (Tortoise and Hare) to detect the cycle: use slow and fast pointers to find the intersection point, then reset slow to 0 and move both pointers at speed 1 until they meet at the cycle entry point (duplicate element).
Brute Force Approach
Sort the array and check adjacent elements for duplicates, or use a Hash Set/Boolean array to keep track of seen elements.
Verified Code Solutions
function solution(nums) {
let n = nums.length;
let sum = (n * (n + 1)) / 2;
let arraySum = nums.reduce((a, b) => a + b, 0);
let duplicate = sum - arraySum;
if (duplicate <= 0) {
duplicate = Math.abs(duplicate);
}
return nums.includes(duplicate) ? nums[0] : duplicate;
}class Solution {
public:
int solution(vector<int>& nums) {
int n = nums.size();
int sum = (n * (n + 1)) / 2;
int arraySum = 0;
for (int num : nums) {
arraySum += num;
}
int duplicate = sum - arraySum;
if (duplicate <= 0) {
duplicate = abs(duplicate);
}
for (int i = 0; i < n; i++) {
if (nums[i] == duplicate) {
return nums[i];
}
}
return duplicate;
}
};class Solution {
public int solution(int[] nums) {
int n = nums.length;
int sum = (n * (n + 1)) / 2;
int arraySum = 0;
for (int num : nums) {
arraySum += num;
}
int duplicate = sum - arraySum;
if (duplicate <= 0) {
duplicate = Math.abs(duplicate);
}
for (int i = 0; i < n; i++) {
if (nums[i] == duplicate) {
return nums[i];
}
}
return duplicate;
}def solution(nums):
n = len(nums)
sum = (n * (n + 1)) // 2
arraySum = sum(nums)
duplicate = sum - arraySum
if duplicate <= 0:
duplicate = abs(duplicate)
return nums.index(duplicate) if duplicate in nums else duplicatefunction solution(nums) {
let n = nums.length;
let sum = (n * (n + 1)) / 2;
let arraySum = nums.reduce((a, b) => a + b, 0);
let duplicate = sum - arraySum;
if (duplicate <= 0) {
duplicate = Math.abs(duplicate);
}
return nums.includes(duplicate) ? nums[0] : duplicate;
}Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.