Skip to main content

Single Element in a Sorted Array

LeetCode 540 | Difficulty: Medium​

Medium

Problem Description​

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.

Return the single element that appears only once.

Your solution must run 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 <= 10^5`

- `0 <= nums[i] <= 10^5`

Topics: Array, Binary Search

Approach​

Binary search reduces the search space by half at each step. The key insight is identifying the monotonic property — what condition lets you decide to go left or right?

When to use

Sorted array, or searching for a value in a monotonic function/space.

Solutions​

Solution 1: C# (Best: 96 ms)​

MetricValue
Runtime96 ms
Memory45.3 MB
Date2022-02-13
Solution
public class Solution {
    public int SingleNonDuplicate(int[] nums) {
        int lo = 0, hi = nums.Length-1;
    while(lo<hi)
    {
        int mid = lo + (hi-lo)/2;
        int nei = (mid%2==1) ? mid-1 : mid+1;
        if(nums[mid]==nums[nei]) lo = mid+1;
        else hi = mid;
    }
    return nums[lo];
    }
}
📜 1 more C# submission(s)

Submission (2022-02-13) — 157 ms, 43 MB​

public class Solution {
    public int SingleNonDuplicate(int[] nums) {
        int i = 0;
    int len = nums.Length;
    
    while(i+1<nums.Length)
    {
        if(nums[i]!=nums[i+1]) return nums[i];
        i=i+2;      
    }
    return nums[i];
    }
}

Complexity Analysis​

ApproachTimeSpace
Binary Search$O(log n)$$O(1)$

Interview Tips​

Key Points
  • Discuss the brute force approach first, then optimize. Explain your thought process.
  • Precisely define what the left and right boundaries represent, and the loop invariant.