Single Element in a Sorted Array

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];
    }
}

Enter fullscreen mode Exit fullscreen mode

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.

Enter fullscreen mode Exit fullscreen mode

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.

Enter fullscreen mode Exit fullscreen mode

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]

Enter fullscreen mode Exit fullscreen mode

then:

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

To simplify:

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

Enter fullscreen mode Exit fullscreen mode

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];
    }
}

Enter fullscreen mode Exit fullscreen mode

Dry Run

Input

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

Enter fullscreen mode Exit fullscreen mode

Iteration 1

low = 0
high = 6

mid = 3
mid = 2 (make even)

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

Enter fullscreen mode Exit fullscreen mode

Pair exists.

Move Right

low = 4

Enter fullscreen mode Exit fullscreen mode

Iteration 2

low = 4
high = 6

mid = 5
mid = 4

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

Pair broken.

Move Left

high = 4

Enter fullscreen mode Exit fullscreen mode

Result

low = high = 4

Answer = 3

Enter fullscreen mode Exit fullscreen mode

Why This Works?

Before the single element:

Pair starts at Even Index

Enter fullscreen mode Exit fullscreen mode

After the single element:

Pair starts at Odd Index

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode