Single Element in a Sorted Array

Medium
64.

Single Element in a Sorted Array

Single Element in a Sorted Array is a medium coding problem on arrays and binary search, asked in Zomato interviews.

You are given a sorted array where every element appears exactly twice, except one element that appears once. Return that single element in O(log n) time and O(1) space.

Example 1

Input
nums = [1,1,2,3,3,4,4,8,8]
Output
2

Example 2

Input
nums = [3,3,7,7,10,11,11]
Output
10

Constraints

  • 1 <= nums.length <= 31 (odd)
  • 0 <= nums[i] <= 100
  • Sorted; every value twice except one.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNonDuplicate = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Single Element in a Sorted Array — Problem & Solution

Single Element in a Sorted Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Single Element in a Sorted Array is a medium coding problem on arrays and binary search, asked in Zomato interviews.

  • Difficulty: Medium
  • Topics: Arrays, Binary Search
  • Asked at: Zomato
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a sorted array where every element appears exactly twice, except one element that appears once. Return that single element in O(log n) time and O(1) space.

Example 1

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2

Input: nums = [3,3,7,7,10,11,11]
Output: 10

Constraints

  • 1 <= nums.length <= 31 (odd)
  • 0 <= nums[i] <= 100
  • Sorted; every value twice except one.

Hints for Single Element in a Sorted Array

  1. Hint 1

    Before the single element, pairs start at even indices; after it, they start at odd indices.

  2. Hint 2

    Binary search on that parity flip.

How to solve Single Element in a Sorted Array

Pairing gives the array a hidden structure. Before the lone element, every pair starts at an even index; after it, the pairing is shifted and pairs start at odd indices. That parity flip happens exactly at the single element, and a binary search can hunt for it.

Approach

  1. Search a range [lo, hi] over indices, looping while lo < hi.
  2. Take mid, and if it is odd, step it down by one so it always points at a potential pair start.
  3. If nums[mid] == nums[mid + 1], the pairing is still intact here — the single element is further right, so lo = mid + 2.
  4. Otherwise the pairing has already broken — the single element is at mid or before it, so hi = mid.
  5. When the range collapses, nums[lo] is the answer.

Why it works

Left of the unique element the array is a perfect sequence of pairs on even boundaries, so nums[even] == nums[even + 1] holds throughout. From the unique element onwards everything shifts by one, so that equality fails. Forcing mid to be even makes the test a direct probe of which side of the flip you are on, and since the flip point is unique the predicate is monotone — exactly what binary search needs.

Complexity

  • Time — O(log n)
  • Space — O(1)

Pitfalls

  • Round mid down to even before comparing; testing an odd index inverts the meaning of the result.
  • Advance by mid + 2 on a matched pair — skipping a whole pair is the point.
  • Use hi = mid so the candidate stays in range.
  • The array length is always odd, and both the first and last position are valid answers.

Reference solution

Python

from typing import List

def singleNonDuplicate(nums: List[int]) -> int:
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if mid % 2 == 1:
            mid -= 1
        if nums[mid] == nums[mid + 1]:
            lo = mid + 2
        else:
            hi = mid
    return nums[lo]

Java

public static int singleNonDuplicate(int[] nums) {
    int lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (mid % 2 == 1) mid--;
        if (nums[mid] == nums[mid + 1]) lo = mid + 2;
        else hi = mid;
    }
    return nums[lo];
}

C++

int singleNonDuplicate(vector<int>& nums) {
    int lo = 0, hi = (int) nums.size() - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (mid % 2 == 1) mid--;
        if (nums[mid] == nums[mid + 1]) lo = mid + 2;
        else hi = mid;
    }
    return nums[lo];
}

JavaScript

var singleNonDuplicate = function(nums) {
    let lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        let mid = (lo + hi) >> 1;
        if (mid % 2 === 1) mid--;
        if (nums[mid] === nums[mid + 1]) lo = mid + 2;
        else hi = mid;
    }
    return nums[lo];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search