The O(n) Club: Find the Duplicate Number (or, That Time Your Array Became a Linked List)

The O(n) Club: Find the Duplicate Number (or, That Time Your Array Became a Linked List)

⚡ TL;DR

Got an array with a single duplicate lurking somewhere, but the catch: you can’t mutate the array, and you have to use O(1) space? Sure, toss out your dreams of HashSets and in-place sorting. Just turn your array into a makeshift linked list and use Floyd’s Tortoise & Hare like you’re chasing bugs through production. Java version for impatient devs below:

// Cycle detection to the rescue!
int slow = nums[0];
int fast = nums[0];
do {
    slow = nums[slow];
    fast = nums[nums[fast]];
} while (slow != fast);
slow = nums[0];
while (slow != fast) {
    slow = nums[slow];
    fast = nums[fast];
}
return slow;

🧠 How Devs Usually Mess This Up

You’ll spot devs lining up at LeetCode, bravely reaching for any tool except the one they actually need. Classic fails include:

• Sorting the array—congrats, you just broke the “no touchy” rule. Interviewer cringes in 1.6 seconds flat.
• Busting out a HashSet—fun, but hogs O(n) space, which the question specifically tells you not to do.
• All-pair brute force—takes O(n²) time, which even your grandpa’s floppy drive wouldn’t excuse.

All these either violate array sanctity or allocate memory like you’re prepping for a Black Friday cache stampede. Make a better excuse next time?

🔍 What’s Actually Going On

Sneaky interviewer: “There’s a duplicate, but you can’t look for it the easy way.” Here’s the trick—the array’s values (each between 1 and n) become next-pointers. Imagine each number as a node that points to its value’s index, and since there are n+1 nodes and n possible destinations, one value must point twice. Pigeonhole principle says: cycle!

Suddenly, your pristine array is masquerading as a linked list, with a cycle formed by the repeated number. Floyd’s algorithm isn’t just for CS201 homework—it’s for you, right now. The duplicate hides at the entrance to this “array cycle.”

🛠️ PseudoCode

• Start two pointers (let’s call them Chandler and Joey):

  int slow = nums[0];
  int fast = nums[0];

  Both begin at the start of your array—nervous, slightly lost.
• Find their meeting point in the cycle:

  do {
      slow = nums[slow];
      fast = nums[nums[fast]];
  } while (slow != fast);

  Chandler moves one node per step, Joey jumps two in caffeine-fueled bursts. Eventually they’ll “accidentally” meet inside the cycle.
• Reset one pointer and walk together:

  slow = nums[0];
  while (slow != fast) {
      slow = nums[slow];
      fast = nums[fast];
  }

  Once they’re both going the same speed from different spots, they meet at the duplicate. It’s science, with a dash of sitcom timing.

💻 The Code

public class FindDuplicate {
    public int findDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[0];
        // Step 1: Detect cycle
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        // Step 2: Find entry (duplicate)
        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• If you try to sort or use extra memory, congrats: you just flunked the one constraint that matters. Try again.
• Time complexity: O(n). Smooth as a fresh build, unless you go all-in on brute force.
• Space: O(1). Literally two pointers; could run on an 80s Casio watch.
• Edge cases? Even if the duplicate appears three times or more, this trick still grabs the right one. Floyd never skips breakfast (or duplicates).

🧠 Interviewer Brain-Tattoo

“If an array walks like a linked list and cycles like a linked list, it’s a job interview question.” Cycle detection isn’t just for graphs… or ducks.