540. Single Element in a Sorted Array
Problem Description
In this LeetCode problem, we have a sorted array where each number normally appears twice, except for one particular number that appears only once. The challenge is to identify the single number that doesn't have a pair. Moreover, the solution must be efficient, running in logarithmic time complexity, which suggests that we should use an algorithm like binary search, and the space complexity must be constant, not dependent on the size of the input array.
Intuition
To solve this problem, we leverage the sorted nature of the array and the requirements for time and space complexity to determine that binary search is the right approach. Binary search helps us cut down the problem space in half with each iteration, making our time complexity O(log n).
The key insight here is to understand how pairs of the same numbers are arranged in the array. Since the array is sorted, identical numbers are adjacent. If we take the first occurrence of a pair, it should be at an even index, and its pair should be immediately next, at an odd index, and this pattern continues until we hit the single element. After the single element, this pattern will flip because of the missing pair.
By examining the middle index and its adjacent numbers, we can decide whether the single number lies on the left or right of our current middle point. Specifically, we use XOR operator to quickly check if a number at an even index does not have its pair at the next odd index, or vice versa for an odd index. The XOR operation is mid ^ 1
, which essentially gives us the index that should hold the identical number to the one at mid
. If the condition is true, it means the single number is at mid
or left of it, so we shift our search window to the left. Otherwise, the single non-duplicate must be to the right, so we adjust our window accordingly.
We repeat this until we narrow down to one element, left
index ends up pointing to the single element, as right
converges towards it. Hence, the element at the left
index is the non-duplicated number and our answer.
Learn more about Binary Search patterns.
Solution Approach
The provided solution approach uses binary search, which is an efficient algorithm for finding an item in a sorted array, using a divide and conquer strategy. The basic idea of binary search is to repeatedly divide the search interval in half. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.
Here's a step-by-step breakdown of the implementation:
-
Initialize two pointers,
left
andright
, to the start and end of the array, respectively. These pointers will define the bounds of our search space. -
Use a while loop to iterate as long as
left
is less thanright
. This condition ensures that the search continues until the search space is reduced to one element. -
Calculate the
mid
index, which is central to binary search's divide-and-conquer approach, using(left + right) >> 1
. The rightward shift operator>>
effectively divides the sum by two but is faster than standard division. -
Determine if the element at
mid
is part of a pair that starts with an even index (mid
being even andnums[mid] == nums[mid ^ 1]
) or an odd index (mid
being odd andnums[mid] == nums[mid ^ 1]
). The bitwise XOR operator^
is used here to compare the element with its adjacent pair member based on the parity ofmid
.-
If
nums[mid] == nums[mid ^ 1]
, the single element must be to the right ofmid
, thusleft
is set tomid + 1
. -
Conversely, if
nums[mid] != nums[mid ^ 1]
, the single element must be to the left ofmid
(includingmid
itself), soright
is set tomid
.
-
-
This process halves the search interval with each iteration, quickly homing in on the single non-duplicate number.
-
The loop terminates when
left
equalsright
, signifying that the element at theleft
index is the non-duplicated number. -
Finally, return the value at the
left
index.
By following this approach, we harness binary search's efficiency in concert with the array's particular properties (sorted with pairs of numbers) to achieve the desired logarithmic time complexity and constant space complexity.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through an example to illustrate the solution approach described above using the array nums = [1, 1, 2, 3, 3]
. We need to find the single number that does not have a pair.
-
Initialize
left = 0
andright = 4
(the start and end indices of the array). -
Start the while loop. Since
left < right
(0 < 4), we proceed with binary search. -
Calculate
mid
.(left + right) >> 1
is(0 + 4) >> 1
, which equals 2. So,mid = 2
, andnums[mid] = 2
. -
We need to check the parity of
mid
and use the XOR operator to determine which side to search next.- Since
mid
is even, we comparenums[mid]
andnums[mid ^ 1]
. We computemid ^ 1
as2 ^ 1
, which equals 3. nums[mid]
is 2 andnums[mid ^ 1]
is 3. They're not equal (2 != 3
), indicating that the single number must be to the left ofmid
, includingmid
itself.
- Since
-
Set
right
tomid
(nowright = 2
). -
The while loop continues. Now,
left
is 0 andright
is 2. Check ifleft < right
āyes, 0 < 2. -
Calculate the new
mid
.(left + right) >> 1
is(0 + 2) >> 1
, which equals 1. So now,mid = 1
andnums[mid] = 1
. -
Check the adjacency condition again.
mid
is odd, so we check ifnums[mid] == nums[mid ^ 1]
. We computemid ^ 1
as1 ^ 1
, which equals 0.nums[mid]
is 1 andnums[mid ^ 1]
is also 1 (nums[0]
), they are equal (1 == 1
). So this means the single number should be to the right ofmid
.
-
Set
left
tomid + 1
(nowleft = 2
). -
Repeat the loop.
left
is now 2, andright
is also 2, which meansleft
is not less thanright
, so the loop ends. -
The single number is at the
left
index, which is 2.nums[left]
is 2, which is the single number we were looking for.
By following these steps, we used binary search efficiently to find the single non-duplicate number in a sorted array.
Solution Implementation
1from typing import List
2
3class Solution:
4 def single_non_duplicate(self, nums: List[int]) -> int:
5 # Initialize the search space
6 left, right = 0, len(nums) - 1
7
8 # Perform binary search to find the non-duplicate integer
9 while left < right:
10 # Calculate the middle index of the current search space
11 mid = (left + right) // 2
12
13 # Check if the middle element's value is equal to the next
14 # or the previous based on whether mid is odd or even
15 # Using XOR operation. If mid is even, mid ^ 1 will be mid + 1,
16 # and if mid is odd, mid ^ 1 will be mid - 1.
17 if nums[mid] != nums[mid ^ 1]:
18 # If they are not equal, move the right pointer to mid.
19 # We do this because the single element must be in the
20 # first half if the pair is not complete in the mid.
21 right = mid
22 else:
23 # If they are equal, this means the single element is in the
24 # second half of the array. Move the left pointer to mid + 1.
25 left = mid + 1
26
27 # When left == right, the search space has been narrowed down to one element.
28 # This remaining element is the non-duplicate integer we're looking for.
29 return nums[left]
30
31# Example usage:
32# sol = Solution()
33# result = sol.single_non_duplicate([1, 1, 2, 3, 3, 4, 4, 8, 8])
34# print(result) # Output should be 2
35
1class Solution {
2 public int singleNonDuplicate(int[] nums) {
3 // Initialize the left and right pointers
4 int left = 0;
5 int right = nums.length - 1;
6
7 // Continue searching while the left pointer is less than the right pointer
8 while (left < right) {
9 // Calculate the middle index
10 int mid = left + (right - left) / 2;
11
12 // The XOR operation here is a clever trick. Since we're looking for
13 // the single non-duplicate number, pairs will be adjacent.
14 // For even mid index, mid ^ 1 will be the next index, which should be identical in the case of pairs.
15 // For odd mid index, mid ^ 1 will be the previous index, which, again, should be identical in case of pairs.
16 // If they're not identical, then the single element must be to the left, so adjust the right pointer.
17 if (nums[mid] != nums[mid ^ 1]) {
18 right = mid;
19 } else {
20 // If they are identical, the single element must be to the right, so adjust the left pointer.
21 left = mid + 1;
22 }
23 }
24
25 // When left == right, we have found the single non-duplicate element.
26 return nums[left];
27 }
28}
29
1#include <vector> // Include necessary header for the vector container
2
3// Solution class to encapsulate the method that finds the single non-duplicate number
4class Solution {
5public:
6 // The singleNonDuplicate method takes a vector of integers and returns the single non-duplicate number.
7 int singleNonDuplicate(std::vector<int>& nums) {
8 // Initialize the left and right pointers for binary search
9 int left = 0;
10 int right = nums.size() - 1;
11
12 // Execute binary search while the left pointer is less than the right pointer
13 while (left < right) {
14 // Calculate the middle index
15 int mid = left + (right - left) / 2; // Avoid potential overflow by using left + (right - left) / 2 instead of (left + right) / 2
16
17 // Check for the single element
18 // XORing the index 'mid' with 1 will give us the pair index for even 'mid'(mid ^ 1 = mid + 1) and
19 // the previous index for odd 'mid'(mid ^ 1 = mid - 1)
20 if (nums[mid] != nums[mid ^ 1]) {
21 // If nums[mid] is not the same as its adjacent (pair), we found our single element or it is to the left.
22 // Hence, we move the 'right' pointer to 'mid'
23 right = mid;
24 } else {
25 // If nums[mid] is the same as its adjacent, the single element must be to the right of 'mid'
26 // So, move the 'left' pointer to 'mid + 1'
27 left = mid + 1;
28 }
29 }
30
31 // At the end of the loop, 'left' will have converged to the single non-duplicate element
32 return nums[left];
33 }
34};
35
1// Function to find the single non-duplicate number in a sorted array.
2// All numbers except one appears exactly twice, the non-duplicate number appears only once.
3function singleNonDuplicate(nums: number[]): number {
4 // Define pointers for the binary search
5 let leftPointer = 0;
6 let rightPointer = nums.length - 1;
7
8 // Start binary search
9 while (leftPointer < rightPointer) {
10 // Calculate the middle index using bit manipulation
11 // (right shift by 1 is equivalent to dividing by 2)
12 const middleIndex = (leftPointer + rightPointer) >> 1;
13
14 // Check if the middle element is not equal to its neighbor.
15 // XOR with 1 will check the neighbor, for even mid it will check next, for odd mid it will check previous.
16 if (nums[middleIndex] != nums[middleIndex ^ 1]) {
17 // If it's not equal, the single element must be on the left side.
18 // Move the right pointer to the middle index.
19 rightPointer = middleIndex;
20 } else {
21 // Otherwise, the single element is on the right side.
22 // Move the left pointer to one past the middle index.
23 leftPointer = middleIndex + 1;
24 }
25 }
26 // At the end of the loop, leftPointer will point to the single element.
27 // Return the element at the leftPointer index.
28 return nums[leftPointer];
29}
30
31// Example usage:
32// const result = singleNonDuplicate([1,1,2,3,3,4,4,8,8]);
33// console.log(result); // Outputs: 2
34
Time and Space Complexity
Time Complexity
The time complexity of the given code is O(log n)
. This is because the algorithm applies a binary search over the input array nums
. During each iteration of the while loop, the search space is halved by updating either the left
or right
pointers, which results in a logarithmic number of steps relative to the size of the input array.
Space Complexity
The space complexity of the code is O(1)
. No additional data structures that scale with input size are used within the method. The variables left
, right
, and mid
occupy constant space, so the space usage does not depend on the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the relationship between a tree and a graph?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!