Katkat
Back

Find the Unique Element in Pairs

XiaohongshuSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to use binary search on a sorted array to find a unique element where all other elements appear in identical pairs.

Problem Statement

You are given a sorted array of integers nums where every element appears exactly twice, except for one element that appears only once. Your task is to find and return that single unique element.

Your solution must run in O(log n) time complexity and O(1) auxiliary space.

Function Signature

def find_single_element(nums: list[int]) -> int:

Examples

Example 1: Input: nums = [1, 1, 2, 3, 3, 4, 4, 8, 8] Output: 2 Explanation: The unique element is 2.

Example 2: Input: nums = [3, 3, 7, 7, 10, 11, 11] Output: 10 Explanation: The unique element is 10.

Constraints

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^5

Edge Cases

  • Array with only one element.
  • The unique element is at the very beginning or the very end of the array.

Hints

Hint 1

Consider the indices of the paired elements: in the absence of a unique element, the first occurrence of a pair is at an even index and the second at an odd index.

Hint 2

When the unique element is introduced, notice how the index parity of subsequent pairs shifts.

Hint 3

Use binary search to check the mid index and its neighbor to determine which half of the array contains the unique element.

Follow-up questions

  • What changes if the array is not sorted?
  • How would you modify your approach if the elements appeared three times instead of two?
  • What if the unique element appeared twice and one of the other elements appeared only once?