The O(n) Club: Single Element in a Sorted Array — When XOR Won’t Save You

The O(n) Club: Single Element in a Sorted Array — When XOR Won’t Save You

⚡ TL;DR

Given a sorted array where every element appears twice except for one poor, lonely outcast, you need to find that rebel. Brute force or XOR would work… if you enjoy suboptimal solutions and making your interviewer yawn. For real log n glory, use binary search. Quick and dirty Java version:

// Brute Force (O(n)), for rebels only
for (int i = 0; i < nums.length - 1; i += 2) {
    if (nums[i] != nums[i + 1]) return nums[i];
}
return nums[nums.length - 1];

🧠 How Devs Usually Mess This Up

If you default to a linear scan or roll in with that fan-favorite XOR trick, congratulations—you missed the “O(log n)” clue. Interviewers everywhere sigh in disappointment (and secretly wish they had your optimism). Plus, tripwire #2: off-by-one errors. Midpoint sloppiness and neighbor confusion can have you debugging past midnight. Fun fact: If you assume the unique element can’t be at the array boundary, say hello to subtle bugs and a strongly worded rejection email.

🔍 What’s Actually Going On

Imagine your array like a rowdy conga line. Before the oddball shows up, every element is paired (even, then odd index—nice and orderly). Once the lonely dancer jumps in, the pairs start tripping: after the unique, pairs start at odd indices. The secret sauce? Use binary search to find where the pattern breaks. Don’t overthink by value—focus on index parity.

🛠️ PseudoCode

• Set pointers: left = 0, right = nums.length - 1
• While left < right:
• Calculate mid = (left + right) / 2
• If mid % 2 == 1, back it up one (so mid is even)
• If nums[mid] == nums[mid + 1], unique is further right: left = mid + 2
• Else, unique is left or at mid: right = mid
• When left == right, that’s your lonely element.

💻 The Code

public int singleNonDuplicate(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        // Always work from an even index!
        if (mid % 2 == 1) mid--;
        if (nums[mid] == nums[mid + 1]) {
            left = mid + 2;
        } else {
            right = mid;
        }
    }
    return nums[left];
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Forgetting to push mid to even = OutOfBoundsException (and existential dread).
• Ignoring array edges: Unique could be at index 0 or the very end. Always check boundaries.
• If your loop updates don’t actually shrink the range, prepare for an infinite existential loop—possibly yours.
• Complexity: O(log n) time, O(1) space. XOR gets a gold star for neatness, but not for speed.

🧠 Interviewer Brain-Tattoo

“If you see ‘sorted’ and ‘O(log n)’, but code a linear scan, the real single element is you.”