Review the fundamentals: Arrays guide and time complexities.
Detect Duplicate Element — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Arrays and solve the Detect Duplicate Element problem optimally.
O(n)O(1)Problem Description
Given an integer array nums of length n, every value is in the range [1, n - 1]. Exactly one distinct value occurs more than once; it may occur two or more times. Return that repeated value without modifying nums and using only O(1) extra space.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Detect Duplicate Element"
WHY DOES IT MATTER?
Cycle detection can find repeated structure using only a few pointers.
OPTIMIZATION CHALLENGE
Find the duplicate without changing the array or allocating a set.
REAL-WORLD CONNECTION
Floyd detection applies to deterministic successor chains, such as a singly linked list; it is not a general graph-cycle detector.
Prove the cycle entry is the duplicate, then keep both pointer phases consistent.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
View index i as pointing to nums[i]. Values lie in [1, n - 1], so index 0 has no incoming edge. Its path must eventually repeat an index, forming a cycle. The cycle entry has an incoming edge from the preceding path and another from the cycle, so its value is duplicated. Exactly one distinct value repeats, making this entry the required answer. Floyd detection finds a meeting inside the cycle. Reset one pointer to 0 and advance both one link at a time to find the entry. Both phases are O(n) time and O(1) auxiliary space. Other disconnected cycles may exist; only the path from 0 matters.
Interview Questions on This Problem
Q1Can the duplicate appear more than twice?
Yes. Exactly one distinct value repeats, but it can occur any number of times allowed by the array length.
Q2Why start at index 0?
No value equals 0, so index 0 is outside a cycle and provides a path into the cycle whose entry is the repeated value.
Q3Does shifting every value make the algorithm work for an arbitrary range?
No. The valid-index range and duplicate assumptions are essential. Changing the range requires a separately justified algorithm.
Examples
Input
[1, 2, 3, 2, 4, 5]
Output
2
Explanation: The value 2 occurs at indices 1 and 3. Following index-to-value links from index 0 gives 0 -> 1 -> 2 -> 3 -> 2, so the cycle entry is 2.
Input
[3, 1, 3, 4, 2]
Output
3
Explanation: The repeated value is 3. The index-to-value path from 0 is 0 -> 3 -> 4 -> 2 -> 3.
Input
[2, 2, 2, 2, 2]
Output
2
Explanation: Exactly one distinct value, 2, repeats; it is allowed to occur more than twice.
Constraints
- 2 <= nums.length <= 10^5
- 1 <= nums[i] < nums.length
- Exactly one distinct value appears more than once; all other present values appear once.
- Do not modify the input array. Use O(1) extra space.
Optimal Approach & Strategy
Treat each index i as pointing to nums[i]. Because values are valid nonzero indices and only one distinct value repeats, the path starting at index 0 enters a cycle at the repeated value. First use Floyd's cycle detection: advance slow by one link and fast by two until they meet. Reset slow to 0, then advance both by one link until they meet again. That meeting index is the duplicate. Both phases take O(n) time, use O(1) extra space, and leave nums unchanged.
Brute Force Approach
Compare every pair of indices and return the value of the first equal pair. This takes O(n^2) time and O(1) extra space without modifying the array. Sorting would modify the input, and a hash set would use O(n) extra space, so neither meets all constraints.
Step-by-Step Dry Run
For nums = [1, 2, 3, 2, 4, 5]: Start slow = 0, fast = 0. Phase 1: (slow, fast) becomes (1, 2), then (2, 2); the pointers meet. Reset slow = 0, leaving fast = 2. Phase 2: (slow, fast) becomes (1, 3), then (2, 2). Return 2, the cycle entry and repeated value.
Code Solutions
function solution(nums) {
let slow = 0;
let fast = 0;
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow !== fast);
slow = 0;
while (slow !== fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
// Input driver: length/dimensions, values, then K when applicable.
if (require.main === module) {
const input = require("fs").readFileSync(0, "utf8").trim();
if (input) {
const tokens = input.split(/\s+/).map(Number); let pos = 0;
const n = tokens[pos++];
const nums = tokens.slice(pos, pos + n); pos += n;
console.log(solution(nums));
}
}#include <iostream>
#include <vector>
class Solution {
public:
int solution(std::vector<int>& nums) {
int slow = 0, fast = 0;
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
slow = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
};
// Input driver: length/dimensions, values, then K when applicable.
int main() {
int n; if (!(std::cin >> n)) return 0;
std::vector<int> nums(n);
for (int& value : nums) std::cin >> value;
std::cout << Solution().solution(nums) << "\n";
}
class Solution {
public int solution(int[] nums) {
int slow = 0, fast = 0;
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
slow = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
}
// Input driver: length/dimensions, values, then K when applicable.
public class Main {
public static void main(String[] args) {
java.util.Scanner in = new java.util.Scanner(System.in);
if (!in.hasNextInt()) return;
int n = in.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) nums[i] = in.nextInt();
System.out.println(new Solution().solution(nums));
}
}
def solution(nums):
slow = fast = 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
slow = 0
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
# Input driver: length/dimensions, values, then K when applicable.
if __name__ == "__main__":
import sys
tokens = iter(map(int, sys.stdin.buffer.read().split()))
n = next(tokens)
nums = [next(tokens) for _ in range(n)]
print(solution(nums))
function solution(nums) {
let slow = 0;
let fast = 0;
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow !== fast);
slow = 0;
while (slow !== fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
// Input driver: length/dimensions, values, then K when applicable.
if (require.main === module) {
const input = require("fs").readFileSync(0, "utf8").trim();
if (input) {
const tokens = input.split(/\s+/).map(Number); let pos = 0;
const n = tokens[pos++];
const nums = tokens.slice(pos, pos + n); pos += n;
console.log(solution(nums));
}
}
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.