Katkat
Back

Find the Single Value in a Sorted Array of Pairs

AmazonSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests the ability to optimize a linear search into a logarithmic one by leveraging the properties of sorted pairs using binary search.

Problem Statement

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

Implement the function findSingleElement(nums: List[int]) -> int.

Constraints

  • nums is sorted in non-decreasing order.
  • The length of nums is always odd.
  • You must solve this in O(log n) time complexity.

Examples

Example 1: Input: nums = [1, 1, 2, 3, 3, 4, 4] Output: 2 Explanation: 1, 3, and 4 appear twice; 2 appears once.

Example 2: Input: nums = [1, 1, 2, 2, 3] Output: 3 Explanation: 1 and 2 appear twice; 3 appears once.

Edge Cases

  • The single element is at the very beginning of the array.
  • The single element is at the very end of the array.
  • The array contains only one element.

Hints

Hint 1

Consider the index of the pairs; before the single element, the first occurrence of a pair is at an even index and the second is at an odd index.

Hint 2

After the single element, the pattern of pairs shifts so that the first occurrence is at an odd index and the second is at an even index.

Hint 3

Use binary search to check if the mid element matches its neighbor; use the index parity to decide which half of the array to discard.

Follow-up questions

  • What happens to your logic if the array is not sorted but still contains pairs and one single element?
  • How would you modify your solution if the problem stated every element appears three times instead of two, except for one?
  • Can you explain why the time complexity is O(log n) using the master theorem or a recurrence relation?