{x}
blog image

Single Element in a Sorted Array

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 <= 105
  • 0 <= nums[i] <= 105

540. Single Element in a Sorted Array

Problem Description

Given a sorted array of integers where every element appears exactly twice except for one element which appears exactly once, find this single element. The solution must run in O(log n) time and O(1) space.

This problem can be efficiently solved using binary search due to the sorted nature of the input array. The core idea is to exploit the pattern created by the duplicate elements. Pairs of duplicate numbers will always be adjacent. The single, unique element will break this pattern.

Algorithm:

  1. Initialization: Set left pointer to 0 and right pointer to n-1 (where n is the length of the array).

  2. Iteration: While left is less than right:

    • Calculate mid as (left + right) / 2 (or (left + right) >> 1 for bitwise efficiency).
    • Check for the unique element: If nums[mid] is not equal to nums[mid ^ 1], this means nums[mid] is the unique element or it's in the left half (because if it's a duplicate, its pair would be at mid ^ 1). Therefore, update right to mid.
    • Otherwise: The unique element is in the right half. Update left to mid + 1.

  3. Return: When the loop terminates (left == right), nums[left] will hold the unique element.

Time Complexity: O(log n) due to the binary search.

Space Complexity: O(1) as we are using only constant extra space.

Code Implementation

Here's the code in various programming languages:

Python:

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1
        while l < r:
            mid = (l + r) >> 1
            if nums[mid] != nums[mid ^ 1]:
                r = mid
            else:
                l = mid + 1
        return nums[l]

Java:

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] != nums[mid ^ 1]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return nums[l];
    }
}

C++:

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] != nums[mid ^ 1]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return nums[l];
    }
};

Go:

func singleNonDuplicate(nums []int) int {
	l, r := 0, len(nums)-1
	for l < r {
		mid := (l + r) >> 1
		if nums[mid] != nums[mid^1] {
			r = mid
		} else {
			l = mid + 1
		}
	}
	return nums[l]
}

JavaScript:

const singleNonDuplicate = (nums) => {
    let l = 0, r = nums.length - 1;
    while (l < r) {
        let mid = Math.floor((l + r) / 2);
        if (nums[mid] !== nums[mid ^ 1]) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return nums[l];
};

TypeScript:

function singleNonDuplicate(nums: number[]): number {
    let l = 0, r = nums.length - 1;
    while (l < r) {
        let mid = Math.floor((l + r) / 2);
        if (nums[mid] !== nums[mid ^ 1]) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return nums[l];
}

Rust:

impl Solution {
    pub fn single_non_duplicate(nums: Vec<i32>) -> i32 {
        let (mut l, mut r) = (0, nums.len() - 1);
        while l < r {
            let mid = (l + r) / 2;
            if nums[mid] != nums[mid ^ 1] {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        nums[l]
    }
}

C#:

public class Solution {
    public int SingleNonDuplicate(int[] nums) {
        int l = 0, r = nums.Length - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] != nums[mid ^ 1]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return nums[l];
    }
}

These implementations all follow the same binary search algorithm, demonstrating its elegance and efficiency in solving this problem. The mid ^ 1 cleverly handles both even and odd indices to access the potential pair of the element at mid.