Quick Overview

Find the only unpaired value in a sorted array where every other distinct number appears exactly twice. The problem measures binary-search invariants, pair alignment, constant-space reasoning, and boundary handling when the answer lies at either end.

Find the Single Value in a Sorted Array of Pairs

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

## Find the Single Value in a Sorted Array of Pairs ### Problem Implement `singleNonDuplicate(values) -> value`. `values` is sorted in nondecreasing order. Exactly one value appears once, and every other distinct value appears exactly twice. Return the value that appears once. ### Portable Contract - `values` is a nonempty integer array with odd length and `1 <= values.length <= 15,001`. - Every element is between `-1,000,000,000` and `1,000,000,000`. - Exactly one distinct value occurs once; every other distinct value occurs twice. - Do not modify `values`. - Let `B` be the compact UTF-8 JSON byte length of `values`, counting every bracket, comma, minus sign, and digit. Inputs satisfy `B <= 96,000`; the returned integer adds at most eleven serialized bytes. - Target `O(log n)` time and `O(1)` auxiliary space for `n = values.length`. All four languages use and return ordinary signed integers: `list[int]` in Python, an array in JavaScript, `List<Integer>` in Java, and `vector<int>` in C++. ```hint Track where pairs should begin Before the unpaired value, equal pairs start at one index parity; after it, that alignment shifts. ``` ```hint Normalize the midpoint to a pair boundary Comparing a candidate pair is simpler when the inspected index always denotes the first position of a pair. ``` ### Examples ```text values = [1, 1, 2, 3, 3, 8, 8] value = 2 ``` ```text values = [7] value = 7 ``` ### Discussion Requirements - State the pair-alignment invariant used to discard half of the array. - Explain why a linear scan is correct but does not meet the target complexity. - Cover the unique value at the beginning, middle, and end, plus the one-element case. - Show how a parity-based formulation avoids an unnecessarily complex three-way branch inside the loop.

Quick Answer: Find the only unpaired value in a sorted array where every other distinct number appears exactly twice. The problem measures binary-search invariants, pair alignment, constant-space reasoning, and boundary handling when the answer lies at either end.

## Find the Single Value in a Sorted Array of Pairs ### Problem Implement `singleNonDuplicate(values) -> value`. `values` is sorted in nondecreasing order. Exactly one value appears once, and every other distinct value appears exactly twice. Return the value that appears once. ### Portable Contract - `values` is a nonempty integer array with odd length and `1 <= values.length <= 15,001`. - Every element is between `-1,000,000,000` and `1,000,000,000`. - Exactly one distinct value occurs once; every other distinct value occurs twice. - Do not modify `values`. - Let `B` be the compact UTF-8 JSON byte length of `values`, counting every bracket, comma, minus sign, and digit. Inputs satisfy `B <= 96,000`; the returned integer adds at most eleven serialized bytes. - Target `O(log n)` time and `O(1)` auxiliary space for `n = values.length`. All four languages use and return ordinary signed integers: `list[int]` in Python, an array in JavaScript, `List<Integer>` in Java, and `vector<int>` in C++. The answer is unique: the pairing invariant guarantees exactly one qualifying value, so there is no tie to break and no ordering to choose. ### Examples ```text values = [1, 1, 2, 3, 3, 8, 8] value = 2 ``` ```text values = [7] value = 7 ``` ### Discussion Requirements - State the pair-alignment invariant used to discard half of the array. - Explain why a linear scan is correct but does not meet the target complexity. - Cover the unique value at the beginning, middle, and end, plus the one-element case. - Show how a parity-based formulation avoids an unnecessarily complex three-way branch inside the loop.

Constraints

  • 1 <= values.length <= 15001
  • values.length is odd
  • values is sorted in nondecreasing order
  • -1000000000 <= values[i] <= 1000000000
  • Exactly one distinct value occurs once; every other distinct value occurs exactly twice
  • Do not modify values
  • Let B be the compact UTF-8 JSON byte length of values; inputs satisfy B <= 96000, and the returned integer adds at most eleven serialized bytes
  • Target O(log n) time and O(1) auxiliary space for n = values.length

Examples

Input: ([1, 1, 2, 3, 3, 8, 8],)

Expected Output: 2

Input: ([7],)

Expected Output: 7

Hints

  1. A left-to-right scan is correct, but it reads every element. The array is sorted and almost entirely paired, so each comparison should be able to rule out half of the remaining range.
  2. Track where pairs should begin: before the unpaired value, every equal pair starts at an even index; after it, that alignment shifts by one.
  3. Comparing a candidate pair is much simpler when the index you inspect always denotes the first position of a pair. Normalize your midpoint to a pair boundary before you compare, and the loop collapses to two branches instead of three.

Loading coding console...