Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

540. Single Element in a Sorted Array - Leetcode Solution

Code Implementation

class Solution:
    def singleNonDuplicate(self, nums):
        left, right = 0, len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if mid % 2 == 1:
                mid -= 1
            if nums[mid] == nums[mid + 1]:
                left = mid + 2
            else:
                right = mid
        return nums[left]
      
class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (mid % 2 == 1) mid--;
            if (nums[mid] == nums[mid + 1])
                left = mid + 2;
            else
                right = mid;
        }
        return nums[left];
    }
};
      
class Solution {
    public int singleNonDuplicate(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (mid % 2 == 1) mid--;
            if (nums[mid] == nums[mid + 1])
                left = mid + 2;
            else
                right = mid;
        }
        return nums[left];
    }
}
      
var singleNonDuplicate = function(nums) {
    let left = 0, right = nums.length - 1;
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (mid % 2 === 1) mid--;
        if (nums[mid] === nums[mid + 1]) {
            left = mid + 2;
        } else {
            right = mid;
        }
    }
    return nums[left];
};

Problem Description

You are given a sorted array nums where every element appears exactly twice, except for one element which appears only once. Your task is to find and return the single element that appears only once. The solution must run in O(log n) time and use O(1) extra space.
  • Each element in nums is an integer.
  • The array is sorted in non-decreasing order.
  • There is exactly one element that appears only once, and all other elements appear exactly twice.
  • You cannot use extra space proportional to the input size (no hash maps, etc.).

Thought Process

At first glance, the problem might suggest a simple linear scan: check each pair of elements and find the one that does not match. However, the strict time requirement of O(log n) hints that a binary search or other divide-and-conquer method is necessary. Since the array is sorted and all elements except one appear in pairs, we can leverage the properties of indices and the structure of the data. The main realization is that before the single element, pairs start at even indices, and after the single element, pairs start at odd indices. This pattern lets us repeatedly halve the search space. The brute-force approach (linear scan or XOR) is too slow or not allowed due to constraints. Instead, we focus on how to apply binary search effectively.

Solution Approach

To solve the problem efficiently, we use a binary search algorithm that exploits the pairing property of the sorted array.
  1. Initialize pointers: Set left to 0 and right to the last index of nums.
  2. Binary search loop: While left < right, do the following:
    • Compute mid as the midpoint between left and right.
    • If mid is odd, decrement it by 1. This ensures mid always points to the first element in a pair.
    • Compare nums[mid] and nums[mid + 1]:
      • If they are equal, the single element must be to the right of mid + 1 (since all pairs before the unique element are correct). Set left = mid + 2.
      • If they are not equal, the single element is at mid or to its left. Set right = mid.
  3. Termination: When left == right, the single element is at index left.
This approach is efficient because each comparison halves the search space, and we never use extra space beyond a few variables.

Example Walkthrough

Let's walk through an example with nums = [1,1,2,3,3,4,4,8,8].
  • Step 1: left = 0, right = 8
  • Step 2: mid = (0+8)//2 = 4. Since 4 is even, we check nums[4] == nums[5] (3 == 4)? No.
    • Since they are not equal, set right = 4.
  • Step 3: left = 0, right = 4, mid = 2. nums[2] == nums[3] (2 == 3)? No.
    • Again, set right = 2.
  • Step 4: left = 0, right = 2, mid = 1 (odd, so mid = 0). nums[0] == nums[1] (1 == 1)? Yes.
    • Set left = 2.
  • Step 5: left = 2, right = 2. Loop ends. The answer is nums[2] = 2.
Thus, the unique element 2 is found efficiently.

Time and Space Complexity

  • Brute-force approach: Scanning the whole array takes O(n) time and O(1) space (if using XOR), or O(n) space if using a hash map.
  • Optimized approach (binary search): Each iteration halves the search space, so the time complexity is O(log n). Only a few variables are used, so space complexity is O(1).
The optimized binary search meets the problem's constraints and is much faster for large arrays.

Summary

The key insight is recognizing the pattern of pairs in a sorted array and how the single element disrupts that pattern. By using binary search and always checking pairs at even indices, we can efficiently find the unique element in O(log n) time and O(1) space. This approach is both elegant and optimal for the problem's constraints.