82. Find the Duplicate Number (Cyclic Sort Approach)
🔗 LeetCode Problem: 287. Find the Duplicate Number
📊 Difficulty: Easy (with Cyclic Sort)
🏷️ Topics: Array, Two Pointers, Binary Search, Bit Manipulation
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.
Example 1:
Input: nums = [1,3,4,2,2]
Output: 2
Example 2:
Input: nums = [3,1,3,4,2]
Output: 3
Constraints:
- 1 <= n <= 10^5
- nums.length == n + 1
- 1 <= nums[i] <= n
- All the integers in nums appear only once except for precisely one integer which appears two or more times.
🌟 Note: Two Different Patterns!
This is the SAME problem as #75, but with a DIFFERENT approach!
Problem #75: Floyd's Cycle Detection (Fast & Slow Pointers)
- Array as linked list
- O(n) time, O(1) space
- DOESN'T modify array ✓
Problem #82: Cyclic Sort (THIS ONE!)
- Place numbers at correct indices
- O(n) time, O(1) space
- DOES modify array ✗ (violates constraint!)
Why learn both?
- Different pattern practice
- Interview might restrict approach
- Understanding multiple solutions
⚠️ CRITICAL: Constraint Violation!
Problem says: "without modifying the array"
Cyclic Sort MUST modify the array to work!
So technically, this approach VIOLATES the constraint!
However:
✓ Great for understanding Cyclic Sort pattern
✓ Works if modification is allowed
✓ Good to know the limitation
For interview: Use Floyd's approach (#75) if modification not allowed!
🎨 Visual Understanding
The Cyclic Sort Idea
Example: nums = [1, 3, 4, 2, 2]
Cyclic Sort Goal:
Place each number i at index i-1
Perfect placement:
Index: 0 1 2 3 4
Value: 1 2 3 4 ?
But we have:
Index: 0 1 2 3 4
Value: 1 3 4 2 2
After trying to sort:
When we try to place second "2" at index 1
But index 1 already has 2!
→ 2 is the duplicate! ✓
The Process
Initial: [1, 3, 4, 2, 2]
Step 1: i=0, nums[0]=1
1 should be at index 0 ✓
Already correct!
Step 2: i=1, nums[1]=3
3 should be at index 2
Swap with index 2
[1, 4, 3, 2, 2]
Step 3: i=1, nums[1]=4
4 should be at index 3
Swap with index 3
[1, 2, 3, 4, 2]
Step 4: i=1, nums[1]=2
2 should be at index 1 ✓
Already correct!
Step 5: i=2, nums[2]=3
3 should be at index 2 ✓
Already correct!
Step 6: i=3, nums[3]=4
4 should be at index 3 ✓
Already correct!
Step 7: i=4, nums[4]=2
2 should be at index 1
But nums[1] is already 2!
→ Found duplicate! Return 2 ✓
🎯 Approach: Cyclic Sort (Modified Array)
Implementation
/**
* Cyclic Sort - MODIFIES ARRAY (violates constraint!)
* Time: O(n), Space: O(1)
*/
public int findDuplicate(int[] nums) {
int i = 0;
while (i < nums.length) {
int correctIndex = nums[i] - 1;
// If current number is not at its correct position
if (nums[i] != nums[correctIndex]) {
swap(nums, i, correctIndex);
} else {
// If nums[i] == nums[correctIndex]
// Either it's at correct position OR it's a duplicate
// Check if it's at correct position
if (i == correctIndex) {
// At correct position, move to next
i++;
} else {
// Not at correct position but equals target
// This means duplicate!
return nums[i];
}
}
}
return -1; // Should never reach
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
⏰ Time: O(n) - Each number swaps at most once
💾 Space: O(1) - In-place
❌ Constraint: Modifies array (violates problem requirement!)
Alternative: Find Without Full Sort
/**
* Cyclic Sort - Find duplicate without completing sort
* Time: O(n), Space: O(1)
* Still modifies array!
*/
public int findDuplicate(int[] nums) {
int i = 0;
while (i < nums.length) {
// If number is at wrong position
if (nums[i] != i + 1) {
int correctIndex = nums[i] - 1;
// If target position already has this number
if (nums[i] == nums[correctIndex]) {
// Found duplicate!
return nums[i];
}
// Swap to correct position
swap(nums, i, correctIndex);
} else {
i++;
}
}
return -1;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
🔍 Detailed Dry Run
Example: nums = [1, 3, 4, 2, 2]
Goal: Find duplicate (2)
Initial: [1, 3, 4, 2, 2]
Index: 0 1 2 3 4
i = 0:
nums[0] = 1
Expected at index 0? 1 != 0+1? No, 1 == 1 ✓
At correct position! i++
Array: [1, 3, 4, 2, 2]
i = 1
i = 1:
nums[1] = 3
Expected at index 1? 3 != 1+1? Yes, 3 != 2
Wrong position!
correctIndex = 3 - 1 = 2
nums[2] = 4
Is nums[1] == nums[2]? 3 == 4? No
Not duplicate, swap!
Swap nums[1] with nums[2]
Array: [1, 4, 3, 2, 2]
i = 1 (stays same)
i = 1:
nums[1] = 4
Expected at index 1? 4 != 2? Yes
Wrong position!
correctIndex = 4 - 1 = 3
nums[3] = 2
Is nums[1] == nums[3]? 4 == 2? No
Not duplicate, swap!
Swap nums[1] with nums[3]
Array: [1, 2, 3, 4, 2]
i = 1
i = 1:
nums[1] = 2
Expected at index 1? 2 == 2? Yes ✓
At correct position! i++
Array: [1, 2, 3, 4, 2]
i = 2
i = 2:
nums[2] = 3
Expected at index 2? 3 == 3? Yes ✓
At correct position! i++
Array: [1, 2, 3, 4, 2]
i = 3
i = 3:
nums[3] = 4
Expected at index 3? 4 == 4? Yes ✓
At correct position! i++
Array: [1, 2, 3, 4, 2]
i = 4
i = 4:
nums[4] = 2
Expected at index 4? 2 != 5? Yes
Wrong position!
correctIndex = 2 - 1 = 1
nums[1] = 2
Is nums[4] == nums[1]? 2 == 2? YES!
DUPLICATE FOUND!
Return 2 ✓
Result: 2
🎯 Comparison: Cyclic Sort vs Floyd's
Approach Time Space Modifies Constraint
═══════════════════════════════════════════════════════════════
Floyd's (#75) O(n) O(1) No ✓ Satisfies
Cyclic Sort (#82) O(n) O(1) Yes ✗ Violates
When to Use Which:
═══════════════════════════════════════════════════════════════
Use Floyd's (#75) when:
✓ Cannot modify array (problem constraint!)
✓ Want elegant mathematical solution
✓ Interview setting (safer choice)
Use Cyclic Sort (#82) when:
✓ Modification is allowed
✓ Practicing cyclic sort pattern
✓ Want straightforward approach
✓ Educational purposes
Verdict for This Problem:
═══════════════════════════════════════════════════════════════
Floyd's approach is REQUIRED since problem says
"without modifying the array"
Cyclic Sort is GOOD TO KNOW but violates constraint!
🎯 Why Cyclic Sort Works
The Logic:
═══════════════════════════════════════════════════════════════
Range is [1, n], array has n+1 elements
Each number should go to its "home" index
Mapping: Number i → Index i-1
During sorting:
When we try to place duplicate at its home
Home already occupied by same number
→ Found duplicate!
Example:
[1, 3, 4, 2, 2]
Try to place both 2's at index 1:
First 2 goes to index 1 ✓
Second 2 tries to go to index 1
But index 1 already has 2!
→ Duplicate detected! ✓
Time: O(n)
Each number swaps at most once
When duplicate found, return immediately
Space: O(1)
In-place modification
⚠️ Common Mistakes
Mistake 1: Forgetting constraint check
// Using cyclic sort without checking if modification allowed!
// Problem explicitly says "without modifying"
// This approach VIOLATES the constraint!
Always read constraints carefully!
Mistake 2: Wrong duplicate detection
// ❌ WRONG - Only checks equality
if (nums[i] == nums[correctIndex]) {
return nums[i];
}
// What if nums[i] is at correct position?
// nums[2] = 3, correctIndex = 2
// nums[2] == nums[2]? Always true!
// ✓ CORRECT - Check if NOT at correct position
if (nums[i] != i + 1 && nums[i] == nums[correctIndex]) {
return nums[i];
}
Mistake 3: Infinite loop
// ❌ WRONG - Infinite loop on duplicate
while (i < nums.length) {
if (nums[i] != nums[correctIndex]) {
swap(nums, i, correctIndex);
}
// Missing i++ for when they're equal!
}
// ✓ CORRECT
if (nums[i] != nums[correctIndex]) {
swap(nums, i, correctIndex);
} else if (i == correctIndex) {
i++;
} else {
return nums[i]; // Duplicate!
}
🎯 Pattern Recognition
Problem Type: Find Single Duplicate in [1, n]
Core Pattern: Cyclic Sort (WITH MODIFICATION)
When to Apply:
✓ Values in range [1, n]
✓ One duplicate exists
✓ ONLY if modification allowed!
Recognition Keywords:
- "Find duplicate"
- "Range [1, n]"
- "n+1 elements"
- Check: "without modifying"?
Similar Problems:
- Find All Duplicates (LC 442) - Multiple duplicates
- Set Mismatch (LC 645) - One dup, one missing
- Missing Number (LC 268) - One missing
Key Components:
┌────────────────────────────────────────────┐
│ ⚠️ CONSTRAINT VIOLATION WARNING │
│ │
│ Problem says: "without modifying" │
│ Cyclic Sort: MUST modify │
│ │
│ Use Floyd's (#75) for this problem! │
│ Use Cyclic Sort only if allowed! │
└────────────────────────────────────────────┘
🧠 Interview Strategy
CRITICAL: This approach violates the constraint!
If Asked This Problem in Interview:
═══════════════════════════════════════════════════════════════
Step 1: Read constraint carefully
"Oh, I see it says 'without modifying the array'"
Step 2: Mention both approaches
"I know two O(1) space approaches:
- Floyd's cycle detection (doesn't modify)
- Cyclic sort (modifies array)"
Step 3: Choose correct one
"Since the problem requires no modification,
I'll use Floyd's cycle detection approach."
Step 4: Implement Floyd's (#75)
[Implement the Fast & Slow pointer solution]
Bonus Points:
"If modification were allowed, cyclic sort would
be more straightforward - place each number at
its correct index and detect when we find a
duplicate trying to occupy same position."
This shows:
✓ You read constraints carefully
✓ You know multiple approaches
✓ You can choose the right one
✓ You understand trade-offs
📝 Quick Revision Notes
🎯 Core Concept:
Find Duplicate (Cyclic Sort): Place number i at index i-1. When placing, if target already has same number → duplicate found! But ⚠️ VIOLATES "no modification" constraint! Use Floyd's (#75) for actual problem. This approach only for practice or if modification allowed.
⚡ Quick Implementation:
class Solution {
public int findDuplicate(int[] a) {
// // Approach 1 - using linked list cycle concept
// // Floyd algorithm - fast and slow pointers.
// // Step 1 - determine cycle
// int slow = a[0];
// int fast = a[0];
// do {
// slow = a[slow];
// fast = a[a[fast]];
// } while(slow != fast);
// // Step 2 - find the cycle entrance
// slow = a[0];
// while (slow != fast) {
// slow = a[slow];
// fast = a[fast];
// }
// return slow;
// Approach 2 - using cyclic sort
// do a paper work dry-run
int len = a.length;
int i = 0;
while (i < len) {
if(a[i] != i + 1) {
if(a[i] == a[a[i] - 1]) {
return a[i];
}
swap(a, i, a[i] - 1);
} else {
i++;
}
}
return -1;
}
private void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void main(String[] args) {
Solution t = new Solution();
System.out.println(t.findDuplicate(new int[] {1,3,4,2,2}) == 2);
System.out.println(t.findDuplicate(new int[] {3,1,3,4,2}) == 3);
System.out.println(t.findDuplicate(new int[] {3,3,3,3,3}) == 3);
System.out.println(t.findDuplicate(new int[] {1, 1}) == 1);
System.out.println(t.findDuplicate(new int[] {1, 2, 1}) == 1);
System.out.println(t.findDuplicate(new int[] {1, 2, 2}) == 2);
System.out.println(t.findDuplicate(new int[] {1, 2, 3, 4, 5, 1}) == 1);
System.out.println(t.findDuplicate(new int[] {1, 2, 3, 4, 5, 5}) == 5);
System.out.println(t.findDuplicate(new int[] {1, 2, 3, 4, 5, 2}) == 2);
System.out.println(t.findDuplicate(new int[] {2, 1, 2}) == 2);
}
}
🔑 Key Insights:
- Pattern: Cyclic Sort
- Detection: nums[i] == nums[correctIdx] (not at i)
- Constraint: ⚠️ MODIFIES array (violates!)
- Use Floyd's: For actual problem (#75)
- Use This: Only if modification OK
- Time: O(n), Space: O(1)
⚠️ CRITICAL WARNING:
This approach VIOLATES the problem constraint!
Problem says: "without modifying the array"
Cyclic Sort: MUST modify to work
For interviews: Use Floyd's approach (#75)!
This is ONLY for:
✓ Understanding cyclic sort pattern
✓ When modification is allowed
✓ Educational purposes
💡 The Key Difference:
Problem #75 (Floyd's):
Array as linked list
No modification ✓
More complex logic
Problem #82 (Cyclic Sort):
Place at correct indices
Requires modification ✗
Simpler logic
Always check constraints!
🧪 Edge Cases
Case 1: Duplicate at start
Input: nums = [2,1,2]
Output: 2
Case 2: Duplicate at end
Input: nums = [1,3,4,2,2]
Output: 2
Case 3: All duplicates
Input: nums = [2,2,2,2,2]
Output: 2
All handled, but array IS modified! ⚠️
Related Patterns
- Problem #75: Find Duplicate (Floyd's) - REQUIRED approach!
- Find All Duplicates (LC 442) - Multiple duplicates
- Set Mismatch (LC 645) - Cyclic sort perfect here
Happy practicing! 🎯
Note: This problem demonstrates an important lesson: ALWAYS read constraints carefully! While cyclic sort is a valid O(1) space approach, it violates the "no modification" requirement. In interviews, showing you understand when NOT to use a pattern is just as important as knowing the pattern itself! For this specific problem, use Floyd's approach (#75) which doesn't modify the array. 💪✨