algoadvance

Given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once, find this single element that appears only once.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Clarifying Questions

  1. Input Constraints: What is the range of the length of the array? (e.g., Is it small enough to consider edge cases, or large enough that performance concerns are significant?)
  2. Input Format: Is the array always non-empty and guaranteed to contain the single element?

Code

def singleNonDuplicate(nums):
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = left + (right - left) // 2
        
        # Ensuring we are always at the start of a pair
        if mid % 2 == 1:
            mid -= 1
        
        if nums[mid] == nums[mid + 1]:
            left = mid + 2
        else:
            right = mid
    
    return nums[left]

Strategy

  1. Binary Search Approach:
    • Use binary search to find the single element.
    • Given the sorted nature of the array, pairs should start at even indexes (e.g., 0, 2, 4, ...) and their other element at the next odd index (1, 3, 5, ...).
    • While traversing, adjust the search space based on where pairs start and whether we’ve encountered a pair mismatch.
  2. Steps Explanation:
    • Initialize two pointers left at 0 and right at length of nums - 1.
    • Compute the mid index.
    • Ensure that mid is always the start of a pair by making mid even, if it’s odd then decrement it by 1.
    • Check if the element at mid is the same as the element at mid + 1:
      • If it is, then the single element is further down the second half, hence, update left to mid + 2.
      • Otherwise, it means the single element is somewhere in the first half, hence, update right to mid.
    • Lastly, when left equals right, that index will hold the single element.

Time Complexity

This ensures that the solution is both efficient and within the constraints specified.

Try our interview co-pilot at AlgoAdvance.com