Single Element in a Sorted Array

Single Element in a Sorted Array is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Binary Search Patterns pattern, in the On Sorted Array/List subpattern.

Problem statement

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.

Return the single element that appears only once.

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

Example 1:

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

Example 2:

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

Constraints:

- 1 <= nums.length <= 105

- 0 <= nums[i] <= 105

Topics and companies

Topics: Array, Binary Search.

Reported in interviews at Amazon, Facebook, Twitter.

How to practise Single Element in a Sorted Array on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(logn) time and O(1) space.

Open Single Element in a Sorted Array in the code editor, or read the Single Element in a Sorted Array editorial for a worked solution with its approach and complexity analysis.

Where Single Element in a Sorted Array sits in the DSA pattern sheet

• Binary Search Patterns pattern guide
• On Sorted Array/List subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Single Element in a Sorted Array

Other problems that use the same On Sorted Array/List and Binary Search Patterns techniques:

• Binary Search — Easy, same subpattern
• First Bad Version — Easy, same subpattern
• Guess Number Higher or Lower — Easy, same subpattern
• Kth Missing Positive Number — Easy, same subpattern
• Search a 2D Matrix — Medium, same subpattern
• Search Insert Position — Easy, same subpattern