Is Single Element in a Sorted Array easy or hard?

Single Element in a Sorted Array is rated Medium difficulty. The challenge is recognizing how the sorted pairing pattern changes after the single element and using that observation to adapt binary search.

Single Element in a Sorted Array Python/Java solution

Python and Java implementations usually follow the same binary search pattern: compute mid, check whether the pair structure is valid, and move the search boundaries accordingly. Both languages achieve O(log n) time and constant space with this approach.

How to solve Single Element in a Sorted Array in O(log n)?

Use binary search and observe the index parity of pairs. In a valid prefix of the array, the first occurrence of a pair appears at an even index and the second at an odd index. When this pattern breaks, the single element lies on that side of the array, allowing you to discard half the search space each step.

What is the best approach for Single Element in a Sorted Array?

Binary search is the best approach because the array is already sorted and duplicates appear in pairs. By checking whether the pairing pattern holds at the midpoint, you can discard half of the array each step. This reduces the runtime to O(log n) while using O(1) extra space.

Is Single Element in a Sorted Array asked at Google/Amazon/Meta?

Single Element in a Sorted Array frequently appears in coding interviews at companies like Google, Amazon, and Meta because it tests binary search variations and reasoning about sorted data structures. Interviewers often expect the O(log n) binary search solution rather than a linear scan.

What data structure is used in Single Element in a Sorted Array?

The problem primarily uses arrays along with the binary search algorithm. Some implementations also use bitwise XOR operations to cancel duplicate values when solving the problem with a linear scan.

What is the time complexity of Single Element in a Sorted Array?

The optimal binary search solution runs in O(log n) time with O(1) space. A simpler XOR-based scan takes O(n) time and O(1) space because it processes every element in the array.

Description Solution Video 8:26

540. Single Element in a Sorted Array

Medium59.3% acceptance19 companies

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 <= 10⁵
0 <= nums[i] <= 10⁵

Asked at 19 companies

Blinkit Bytedance Moloco

TCS Zomato Amazon Microsoft Bloomberg Zoho Coupang

Google Meta

+7 more

Adobe Flipkart Snowflake ServiceNow Oracle JPMorgan Chase Goldman Sachs

Topics

Array Binary Search

8:26

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def singleNonDuplicate(self, nums: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,1,2,3,3,4,4,8,8]

Input

[3,3,7,7,10,11,11]

Your code is saved on this device.Solution