Single Element in a Sorted Array | Leetcode 540 | Optimal Binary Search

The “Single Element in a Sorted Array” problem is a great example of using binary search in a clever way. In this blog, we’ll explain the problem, walk you through both brute force and optimal solutions, and make everything easy to understand with code comments, dry runs, and clear explanations.

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.

Here’s the [Problem Link] to begin with.

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

Brute Force Solution (Linear Scan)

Intuition and Approach

Let’s solve the problem in the most straightforward way:

1. Check Each Element:
   Go through the array from start to end.
2. Compare with Neighbors:
   • If the element is at the start, check if it’s different from the next.
   • If it’s at the end, check if it’s different from the previous.
   • Otherwise, check if it’s different from both neighbors.
3. Why does this work?
   Since the array is sorted and all elements except one appear twice, the unique element will not be equal to its neighbors.

This approach is easy to understand but not efficient for large arrays.

Code Implementation

class Solution:
    def singleNonDuplicate(self, arr: List[int]) -> int:
        n = len(arr)
        if n == 1:
            return arr[0]
        for i in range(n):
            if i == 0:
                if arr[i] != arr[i + 1]:
                    return arr[i]
            elif i == n - 1:
                if arr[i] != arr[i - 1]:
                    return arr[i]
            else:
                if arr[i] != arr[i - 1] and arr[i] != arr[i + 1]:
                    return arr[i]

Code Explanation

• If the array has only one element, return it.
• For each element, check if it’s different from its neighbors.
• If so, return it as the unique element.

Dry Run

Input:
arr = [1][1]

• i=0: 1 == 1 → skip
• i=1: 1 == 1 → skip
• i=2: 2 != 1 and 2 != 3 → return 2

Final Output:
2

Time and Space Complexity

• Time Complexity: O(n)
  We may have to check every element.
• Space Complexity: O(1)
  Only a variable for looping.

Conclusion

The brute force approach is simple and works for small arrays, but it’s too slow for large inputs.

Optimal Solution (Binary Search)

Intuition and Approach

We can do much better using binary search:

1. Binary Search:
   Use two pointers (low and high) to perform binary search.
2. Check Pairing Pattern:
   • In a sorted array with pairs, the first occurrence of a pair is at even index, second at odd index.
   • If the unique element is before mid, the pairing will break.
3. Move Search Window:
   • If mid is the unique element, return it.
   • If mid is equal to its previous and mid is odd, search right.
   • If mid is equal to its next and mid is even, search right.
   • Otherwise, search left.
4. Why does this work?
   Binary search helps us find the unique element in O(log n) time by leveraging the sorted and paired property.

Code Implementation

class Solution:
    def singleNonDuplicate(self, arr: List[int]) -> int:
        low = 0
        high = len(arr) - 1
        while low <= high:
            mid = (low + high) // 2
            if low == high:
                return arr[low]
            if arr[mid] != arr[mid - 1] and arr[mid] != arr[mid + 1]:
                return arr[mid]
            if arr[mid] == arr[mid - 1]:
                if mid % 2 == 1:
                    low = mid + 1
                else:
                    high = mid - 1
            elif arr[mid] == arr[mid + 1]:
                if mid % 2 == 1:
                    high = mid - 1
                else:
                    low = mid + 1

Code Explanation

• We use binary search with pointers low and high.
• If the unique element is found at mid, return it.
• If mid is part of a pair, adjust the search window based on the index parity.
• Continue until low meets high, then return the element.

Dry Run

Input:
arr = [1][1]

• low = 0, high = 8
• mid = 4 (arr=3)
• arr == arr (3==3), mid is even, so move high = mid – 1 = 3
• low = 0, high = 3
• mid = 1 (arr=1)
• arr == arr (1==1), mid is odd, so move low = mid + 1 = 2
• low = 2, high = 3
• mid = 2 (arr=2)
• arr != arr and arr != arr → found unique, return 2

Final Output:
2

Time and Space Complexity

• Time Complexity: O(log n)
  Binary search divides the array each time.
• Space Complexity: O(1)
  Only a few pointers.

Conclusion

The optimal solution is efficient and works well for large arrays. It’s the best approach for interviews and practical use.

Final Thoughts

The “Single Element in a Sorted Array” problem is a great example of how to optimize from brute force to an efficient binary search solution. Start with brute force to understand the basics, then use binary search for best performance.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.