Single Element in a Sorted Array — Parity Index Binary Search [LC 540, Google, Facebook]

Problem Statement#

LeetCode 540 — Single Element in a Sorted Array · Difficulty: Medium

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element and return it.

You must implement a solution with O(log n) runtime complexity and O(1) space complexity.

Constraints:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^5
• The array length is always odd (since pairs + one single element)

Example 1:

Input:  nums = [1, 1, 2, 3, 3, 4, 4, 8, 8]
Output: 2
Explanation: Every element appears twice except 2.

Example 2:

Input:  nums = [3, 3, 7, 7, 10, 11, 11]
Output: 10
Explanation: Every element appears twice except 10.

Example 3:

Input:  nums = [1]
Output: 1
Explanation: Single element array — the one element is the answer.

Why This Problem Matters#

LC 540 is asked at Google and Facebook to test a subtle but important skill: extracting a binary decision from an index-level observation, not just from element values. Most binary search problems use element values to decide which half to search. This problem requires you to look at the parity of the index — an entirely structural observation about the array.

This matters in real engineering contexts whenever your data has an expected pairing structure and you need to quickly locate where that structure breaks down. Think of version-control blame trees, paired sensor readings where one sensor failed, or encoded data with expected XOR checksums. The parity observation generalises far beyond this problem.

For interviews, this problem also distinguishes candidates who know only the XOR trick (which runs in O(n) linear time and uses the bit-manipulation pattern from LC 136) from those who can achieve the required O(log n). The XOR approach is correct but not fast enough — and the interviewer knows it.

The Core Insight#

Before the singleton, every pair occupies positions (even, odd): first copy at an even index, second copy at an odd index. After the singleton, the pairing shifts: pairs occupy (odd, even) — first copy at an odd index, second at an even index.

This shift is the binary search signal. At any even index mid:

• If nums[mid] == nums[mid + 1]: this pair is intact and in the normal (even, odd) order. The singleton has not appeared yet — it lies to the right of this pair. Move lo = mid + 2.
• If nums[mid] != nums[mid + 1]: the pair at mid is broken (it should match its right neighbor but doesn't). The singleton is at mid or to the left. Move hi = mid.

By always keeping mid on an even index, we make a clean, unambiguous decision every step.

Why must mid be even? The comparison nums[mid] == nums[mid+1] is only meaningful for a "first-of-pair" position. If mid is odd, it is the second copy of the previous pair, and the comparison does not tell us about the singleton's location. We normalise by doing mid -= 1 if mid is odd before making the comparison.

The invariant: the singleton always lies within [lo, hi]. When lo == hi, we have found it.

Visual Dry Run#

Input: nums = [1, 1, 2, 3, 3, 4, 4, 8, 8] (indices 0–8)

Wait — that gives 8, but the answer is 2. Let me re-examine: the singleton (2) is at index 2. In step 1, mid = 4, nums[4] = 3, nums[5] = 4. They do NOT match. So hi = mid = 4.

Result: 2. Correct.

Input: nums = [3, 3, 7, 7, 10, 11, 11] (indices 0–6)

Result: 10. Correct.

Common Mistakes#

1. Using XOR on the full array. XOR of all elements gives the single element in O(n) time. This is clever and correct for LC 136 (unsorted), but LC 540 requires O(log n). The interviewer will explicitly reject the XOR answer. Always mention it as a linear baseline, then implement binary search.

2. Forgetting to normalise mid to an even index. If mid is odd, nums[mid] is the second copy of the pair before the singleton (or after). The nums[mid] == nums[mid+1] comparison gives wrong information. Always do if mid % 2 == 1: mid -= 1 before the comparison.

3. Moving lo = mid + 1 instead of lo = mid + 2 when the pair is intact. When nums[mid] == nums[mid+1] and mid is even, both mid and mid+1 belong to an intact pair. The singleton is after mid+1, so lo = mid + 2. Using lo = mid + 1 puts lo at the second copy of the same pair, causing an infinite loop.

4. Using hi = mid - 1 instead of hi = mid when the pair is broken. When nums[mid] != nums[mid+1], the singleton could be at mid itself. You must keep mid in the search window: hi = mid. Using hi = mid - 1 loses the potential singleton.

5. Using the while lo <= hi (exact-match) template. This problem uses the left-boundary template (while lo < hi) because we are converging on a position, not doing a three-way comparison. Mixing templates causes off-by-one termination errors.

6. Failing to handle the single-element array edge case. When nums = [x], lo = hi = 0, the loop never executes, and we return nums[0]. This is correct, but verify it mentally before the interview — examiners sometimes probe edge cases explicitly.

Solutions#

Python#

def singleNonDuplicate(nums: list[int]) -> int:
    lo, hi = 0, len(nums) - 1       # search over the full array; odd length guaranteed
 
    while lo < hi:                   # converge until one candidate remains
        mid = lo + (hi - lo) // 2   # raw midpoint
 
        # Normalise to an even index: even index = "first of pair" position.
        # This makes the pair-check comparison meaningful.
        if mid % 2 == 1:
            mid -= 1                 # step back to the even index
 
        if nums[mid] == nums[mid + 1]:
            # Pair at (mid, mid+1) is intact (both copies present).
            # The singleton lies to the RIGHT of this pair.
            lo = mid + 2            # skip both copies of this intact pair
        else:
            # Pair at mid is broken — nums[mid] does not match its expected partner.
            # The singleton is AT mid or to the LEFT.
            hi = mid                # keep mid in the window
 
    # lo == hi: the single remaining index holds the singleton
    return nums[lo]

JavaScript#

function singleNonDuplicate(nums) {
    let lo = 0;
    let hi = nums.length - 1;       // inclusive; array length is always odd
 
    while (lo < hi) {               // converge until one index remains
        let mid = lo + Math.floor((hi - lo) / 2); // raw midpoint
 
        // Normalise mid to an even index (first-of-pair position).
        // An odd mid is the second copy of its pair — not useful for our check.
        if (mid % 2 === 1) {
            mid--;                   // move to the even index to the left
        }
 
        if (nums[mid] === nums[mid + 1]) {
            // This pair (mid, mid+1) is intact — both copies are present.
            // The singleton has not appeared yet; it's to the right.
            lo = mid + 2;           // skip this intact pair entirely
        } else {
            // The pair starting at mid is broken — singleton is here or left.
            // Do NOT exclude mid — it could be the singleton itself.
            hi = mid;
        }
    }
 
    // lo === hi: converged to the singleton's index
    return nums[lo];
}

Complexity Analysis#

The binary search halves the range each iteration: the while lo < hi loop runs at most ceil(log₂(n)) times. For n = 100,000 that is at most 17 iterations. Space is O(1) — only index variables are used.

Follow-up Questions#

Q: What if the array is not sorted? Then the parity observation breaks down. Use XOR over all elements (O(n) time, O(1) space) — LC 136 is the unsorted version.

Q: Can every element appear three times instead of two, with one exception? Yes — this is LC 137 (Single Number II). The parity trick does not extend here; you need bit-counting or a state machine for the 3-copy case.

Q: What if there are multiple singletons? The problem guarantees exactly one. With multiple singletons, the parity signal becomes ambiguous (the shift could be caused by any singleton). You'd need a different approach.

Q: Why is the array length always odd? n pairs contribute 2n elements; 1 singleton contributes 1. Total: 2n + 1, which is always odd. If the length were even, the problem would be ill-formed (you couldn't have all pairs plus one singleton).

Q: Can you do this with mid ^ 1? Yes — mid ^ 1 (XOR with 1) flips the last bit: if mid is even, mid ^ 1 = mid + 1; if mid is odd, mid ^ 1 = mid - 1. This is a more compact way to get the pair partner, but using if mid % 2 == 1: mid -= 1 is easier to reason about under interview pressure.

This Pattern Solves#

• LC 540 — Single Element in a Sorted Array (this problem)
• LC 136 — Single Number (unsorted XOR version)
• LC 137 — Single Number II (three-copy version, bit-counting)
• Any problem where a sorted array has an expected structural property (pairing, ordering) that breaks at exactly one position and you must locate the break point

Key Takeaway#

The parity insight is the heart of LC 540: before the singleton, pairs occupy (even, odd) positions; after the singleton, pairs occupy (odd, even) positions. Always normalise mid to an even index before comparing. If the pair at (mid, mid+1) is intact, the singleton is to the right (lo = mid + 2); if broken, it is at or to the left (hi = mid). This parity-based binary search runs in O(log n) — far better than the XOR linear scan — and demonstrates the advanced technique of using index structure, not just element values, to drive binary search decisions.

Key Takeaways#

• LC 540 is a hard binary search problem asked by Facebook and Google; the key insight is using index parity, not element values, to drive the search.
• Before the singleton, all pairs occupy (even, odd) index slots; after the singleton, pairs shift to (odd, even) — this parity flip is the searchable signal.
• Always normalise mid to an even index before the pair comparison to ensure you are looking at the first element of a pair.
• If nums[mid] == nums[mid + 1], the pair is intact and the singleton is to the right (lo = mid + 2); otherwise the singleton is at or before mid (hi = mid).
• The algorithm runs in O(log n) — the XOR approach runs in O(n) and is not the intended solution for a sorted array.
• The constraint that n is always odd (all pairs plus one singleton) is essential; check this when verifying the problem setup in an interview.
• mid ^ 1 is a compact alternative to the even-normalisation step: it flips the last bit, giving the pair partner of any index.