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:

1. Initialize two pointers, left and right, to the start and end of the array, respectively. These pointers will define the bounds of our search space.

2. Use a while loop to iterate as long as left is less than right. This condition ensures that the search continues until the search space is reduced to one element.

3. 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.

4. Determine if the element at mid is part of a pair that starts with an even index (mid being even and nums[mid] == nums[mid ^ 1]) or an odd index (mid being odd and nums[mid] == nums[mid ^ 1]). The bitwise XOR operator ^ is used here to compare the element with its adjacent pair member based on the parity of mid.

   • If nums[mid] == nums[mid ^ 1], the single element must be to the right of mid, thus left is set to mid + 1.

   • Conversely, if nums[mid] != nums[mid ^ 1], the single element must be to the left of mid (including mid itself), so right is set to mid.

5. This process halves the search interval with each iteration, quickly homing in on the single non-duplicate number.

6. The loop terminates when left equals right, signifying that the element at the left index is the non-duplicated number.

7. 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.

Example 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.

1. Initialize left = 0 and right = 4 (the start and end indices of the array).

2. Start the while loop. Since left < right (0 < 4), we proceed with binary search.

3. Calculate mid. (left + right) >> 1 is (0 + 4) >> 1, which equals 2. So, mid = 2, and nums[mid] = 2.

4. 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 compare nums[mid] and nums[mid ^ 1]. We compute mid ^ 1 as 2 ^ 1, which equals 3.
   • nums[mid] is 2 and nums[mid ^ 1] is 3. They're not equal (2 != 3), indicating that the single number must be to the left of mid, including mid itself.

5. Set right to mid (now right = 2).

6. The while loop continues. Now, left is 0 and right is 2. Check if left < right—yes, 0 < 2.

7. Calculate the new mid. (left + right) >> 1 is (0 + 2) >> 1, which equals 1. So now, mid = 1 and nums[mid] = 1.

8. Check the adjacency condition again.

   • mid is odd, so we check if nums[mid] == nums[mid ^ 1]. We compute mid ^ 1 as 1 ^ 1, which equals 0.
   • nums[mid] is 1 and nums[mid ^ 1] is also 1 (nums[0]), they are equal (1 == 1). So this means the single number should be to the right of mid.

9. Set left to mid + 1 (now left = 2).

10. Repeat the loop. left is now 2, and right is also 2, which means left is not less than right, so the loop ends.

11. 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

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.