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.

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.

💪
Level Up Your
Algo Skills

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.

Python Solution

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

Java Solution

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

C++ Solution

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

Typescript Solution

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.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫