540. Single Element in a Sorted Array
Single Element in a Sorted Array (LeetCode 540) 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.
How to solve Single Element in a Sorted Array
Single Element in a Sorted Array is a Binary Search on Sorted Array problem, part of Binary Search Patterns. Master standard binary search on sorted arrays. Learn search insert position, sqrt calculation, and 2D matrix search.
Work towards the solution in these steps:
- Consider using a binary search approach since the array is sorted and you need a logarithmic time solution.
- Think about how pairs of identical elements are arranged in the array before and after the single element.
- Analyze the relationship between the index and the pairing pattern: whether the first or second occurrence of each pair falls on even or odd indices.
The reference solution runs in O(logn) time and O(1) space.
The Single Element in a Sorted Array solution and editorial walks through the full approach with reference code.
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
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
Single Element in a Sorted Array FAQ
What is the LeetCode number of Single Element in a Sorted Array?
Single Element in a Sorted Array is LeetCode problem 540, rated Medium.
What pattern is used to solve Single Element in a Sorted Array?
Single Element in a Sorted Array is a Binary Search on Sorted Array problem. It belongs to the Binary Search Patterns pattern, in the On Sorted Array/List subpattern.
What is the time complexity of Single Element in a Sorted Array?
The reference solution runs in O(logn) time and O(1) space.
Which companies ask Single Element in a Sorted Array?
Single Element in a Sorted Array has been reported in interviews at Amazon, Facebook, Twitter.