Single Element in a Sorted Array

leetcode.com

Problem Statement

Given a sorted array where:

• Every element appears exactly twice.
• Only one element appears once.

Find the single element in O(log N) time and O(1) space.

---

Brute Force Intuition

In an interview, you can explain it like this:

Since every element appears twice except one, we can iterate through the array and count frequencies. The element with frequency 1 is our answer. This works but doesn't utilize the sorted nature of the array.

Complexity

• Time Complexity: O(N)
• Space Complexity: O(1)

Brute Force Code

class Solution {

    public int singleNonDuplicate(int[] nums) {

        for (int i = 0; i < nums.length - 1; i += 2) {

            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }

        return nums[nums.length - 1];
    }
}

---

Moving Towards the Optimal Approach

The important observation is:

Before the single element:

Index: 0 1 2 3 4 5
Array: 1 1 2 2 3 3

Pairs start at EVEN indices.

After the single element:

Index: 0 1 2 3 4 5 6
Array: 1 1 2 3 3 4 4

Pairs start at ODD indices.

The single element breaks the pairing pattern.

This allows us to use Binary Search.

---

Pattern Recognition

Whenever you see:

• Sorted Array
• Pair Pattern
• One Missing / One Unique Element

Think:

Binary Search on Index Pattern

---

Optimal Approach

Observation

If:

nums[mid] == nums[mid + 1]

then:

• If mid is even → single element lies on right.
• Otherwise → lies on left.

To simplify:

if(mid % 2 == 1)
    mid--;

Now every mid becomes even.

---

Optimal Java Solution

class Solution {

    public int singleNonDuplicate(int[] nums) {

        int low = 0;
        int high = nums.length - 1;

        while (low < high) {

            int mid = low + (high - low) / 2;

            if (mid % 2 == 1)
                mid--;

            if (nums[mid] == nums[mid + 1]) {
                low = mid + 2;
            } else {
                high = mid;
            }
        }

        return nums[low];
    }
}

---

Dry Run

Input

nums = [1,1,2,2,3,4,4]

Iteration 1

low = 0
high = 6

mid = 3
mid = 2 (make even)

nums[2] = 2
nums[3] = 2

Pair exists.

Move Right

low = 4

---

Iteration 2

low = 4
high = 6

mid = 5
mid = 4

nums[4] = 3
nums[5] = 4

Pair broken.

Move Left

high = 4

---

Result

low = high = 4

Answer = 3

---

Why This Works?

Before the single element:

Pair starts at Even Index

After the single element:

Pair starts at Odd Index

Binary Search helps identify where this pattern breaks.

---

Complexity Analysis

Metric	Complexity
Time Complexity	O(log N)
Space Complexity	O(1)

---

Interview One-Liner

In a sorted array, pairs start at even indices before the single element and at odd indices after it. Binary search on this pattern finds the answer in O(log N).

---

Pattern Learned

Sorted Array
+
Pair Structure
+
One Unique Element

=> Binary Search on Index Pattern