Single Element in a Sorted Array

MEDIUM

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⁵
0 <= nums[i] <= 10⁵

Approaches

Checkout 3 different approaches to solve Single Element in a Sorted Array. Click on different approaches to view the approach and algorithm in detail.

Brute Force Linear Scan

This approach involves iterating through the sorted array and comparing adjacent elements. Since every element appears twice except for one, the pairs of identical numbers will be next to each other. We can check elements in pairs to find the one that breaks the pattern.

Algorithm

Iterate through the array from index 0 to n-2 with a step of 2.
At each step i, compare nums[i] and nums[i+1].
If nums[i] != nums[i+1], then nums[i] is the unique element. Return it.
If the loop finishes, the last element nums[n-1] is the unique one. Return it.

The algorithm iterates through the array with a step of 2. For each index i, it compares nums[i] with nums[i+1]. If they are different, nums[i] must be the single element because all preceding elements formed valid pairs. If the loop completes, the single element must be the last one in the array.

class Solution {
    public int singleNonDuplicate(int[] nums) {
        // Handle the edge case of a single element array
        if (nums.length == 1) {
            return nums[0];
        }

        // Iterate through the array by pairs
        for (int i = 0; i < nums.length - 1; i += 2) {
            // If a pair doesn't match, the first element is the single one
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }

        // If the loop finishes, the single element is the last one
        return nums[nums.length - 1];
    }
}

Complexity Analysis

Time Complexity: O(n) - In the worst-case scenario, we might have to traverse the entire array to find the single element (e.g., when it's the last element).Space Complexity: O(1) - We only use a constant amount of extra space for loop variables.

Pros and Cons

Pros:

Very simple to understand and implement.

Cons:

Inefficient for large inputs.
Does not meet the O(log n) time complexity requirement specified in the problem.

Code Solutions

Checking out 3 solutions in different languages for Single Element in a Sorted Array. Click on different languages to view the code.

class Solution {
public
  int singleNonDuplicate(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
      int mid = (left + right) >> 1;

Video Solution

Watch the video walkthrough for Single Element in a Sorted Array

Algorithms:

Binary Search

Data Structures:

Array

Companies:

Atlassian |Infosys |Nvidia |ServiceNow |