#540

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Single Element in a Sorted Array

Find the single non-duplicate element in a sorted array where every other element appears exactly twice.

Problem Statement

You are given a sorted array of integers where every element appears exactly twice, except for one element that appears exactly once. Your task is to identify and return this unique element in the array.

The solution must operate in O(log n) time complexity and use O(1) space, implying the use of an efficient algorithm like binary search over the valid answer space. Avoid using extra space or brute force methods.

Examples

Example 1

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

Output: 2

Example details omitted.

Example 2

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

Output: 10

Example details omitted.

Constraints

1 <= nums.length <= 105
0 <= nums[i] <= 105

Solution Approach

Binary Search

Use binary search to divide the array into two halves and examine whether the unique element lies in the left or right half. The key observation is that elements appearing in pairs will always appear in an even-indexed pair if the array is split correctly.

Analyzing Pairing Pattern

During each binary search step, examine the index of the middle element to check if it is part of a pair. If it is, adjust the search boundaries accordingly. This ensures that you narrow down to the side of the array where the unique element exists.

Edge Case Handling

Handle edge cases like the smallest array size, where the only element is the unique one. Additionally, consider arrays with elements all paired but with the unique element at the beginning or end.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The binary search approach guarantees O(log n) time complexity as the search space is halved at each step. The space complexity is O(1) since no additional storage is required beyond the input array and the two pointers used for searching.

What Interviewers Usually Probe

Candidate demonstrates an understanding of binary search on sorted arrays.
Candidate can correctly identify the relationship between array splitting and pair identification.
Candidate handles edge cases such as arrays with only one element and arrays with unique elements at the boundaries.

Common Pitfalls or Variants

Common pitfalls

Forgetting the O(log n) time complexity requirement and attempting brute force methods.
Misunderstanding the array's structure and mistakenly assuming multiple unique elements exist.
Failing to account for edge cases, especially small arrays or unique elements at the boundaries.

Follow-up variants

Consider solving the problem in O(n) time with a hashmap, but note that this doesn’t satisfy the time complexity requirement.
Change the problem to a rotated sorted array where binary search still applies but requires adjusted logic.
Extend the problem to find multiple non-duplicate elements in a sorted array, requiring a different strategy.

FAQ

How can I solve the Single Element in a Sorted Array problem?

Use binary search to efficiently narrow down the half of the array where the unique element exists, while ensuring O(log n) time complexity.

What is the time complexity of solving the problem?

The time complexity of the optimal solution is O(log n) due to the binary search method.

Can I solve this problem with a hashmap?

While using a hashmap is possible, it would result in O(n) time complexity and does not satisfy the problem's constraints of O(log n) time.

How do I handle edge cases like arrays with only one element?

For arrays with one element, simply return that element as it is the unique one.

What is the primary algorithmic pattern in the Single Element in a Sorted Array problem?

The main pattern is binary search over the valid answer space, focusing on the structure of the sorted array to efficiently find the unique element.

terminal

Solution

Solution 1: Binary Search

The given array $\textit{nums}$ is sorted, and we need to find the element that appears only once in $\textit{O}(\log n)$ time. Therefore, we consider using binary search to solve this problem.

1

2

3

4

5

6

7

8

9

10

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]

Continue Practicing

#532 k diff pairs in an array #528 random pick with weight #497 random point in non overlapping rectangles