LeetCode 540: Single Element in a Sorted Array Solution in Python – A Step-by-Step Guide

What Is LeetCode 540: Single Element in a Sorted Array?

In LeetCode 540: Single Element in a Sorted Array, you’re given a sorted array nums where every element appears exactly twice except for one element that appears once, and your task is to find that single element. The array is sorted in ascending order, and the solution must run in O(log n) time with O(1) space. For example, in nums = [1, 1, 2, 3, 3, 4, 4], the single element is 2. This problem builds on LeetCode 704: Binary Search for binary search techniques and leverages the paired structure of the array.

Problem Statement

• Input: nums (List[int])—sorted array with paired elements except one.
• Output: Integer—single element appearing once.
• Rules: O(log n) time complexity, O(1) space; all elements appear twice except one.

Constraints

• 1 <= nums.length <= 10⁵
• Length is odd.
• 0 <= nums[i] <= 10⁵
• Every element appears twice except one.

Examples

• Input: nums = [1,1,2,3,3,4,4]
• Output: 2
• Pairs: (1, 1), (3, 3), (4, 4); 2 is single.
• Input: nums = [3,3,7,7,10,11,11]
• Output: 10
• Pairs: (3, 3), (7, 7), (11, 11); 10 is single.
• Input: nums = [1]
• Output: 1
• Single element.

Understanding the Problem: Finding the Lone Number

To solve LeetCode 540: Single Element in a Sorted Array in Python, we need to find the one element that appears once in a sorted array where all others appear twice. The sorted nature and paired structure suggest binary search, as the single element disrupts the pairing pattern. A naive approach might scan linearly (O(n)), but with up to 10⁵ elements and an O(log n) requirement, we need efficiency. We’ll explore:

• Best Solution (Binary Search with Pair Adjustment): O(log n) time, O(1) space—fast and optimal.
• Alternative Solution (Linear Scan with Pair Check): O(n) time, O(1) space—simple but slow.

Let’s dive into the binary search solution with a friendly breakdown!

Best Solution: Binary Search with Pair Adjustment

Why Binary Search Wins

The binary search with pair adjustment is the best for LeetCode 540 because it exploits the sorted, paired structure of the array to find the single element in O(log n) time and O(1) space, meeting the problem’s requirements perfectly. It adjusts the search space by checking pairs, narrowing down to the unpaired element. It’s like playing a guessing game with the array, zeroing in on the odd one out!

How It Works

Think of this as a pair-checking detective:

• Step 1: Pair Adjustment:
• Ensure mid points to the first of a pair (even index).
• Step 2: Binary Search:
• If nums[mid] == nums[mid+1], pair is intact, single element is in right half.
• If not, single element disrupts pairing, search left half.
• Step 3: Narrow Search:
• Update left or right based on pair check.
• Step 4: Return Single:
• When left == right, that’s the single element.
• Why It Works:
• Sorted pairs mean disruption by single element splits array.
• Binary search halves the space each step.

It’s like a BST pair sleuth!

Step-by-Step Example

Example: nums = [1, 1, 2, 3, 3, 4, 4]

• Init: left = 0, right = 6 (len-1).
• Step 1: mid = 3, adjust to 2 (even), check pair:
• nums[2] = 2, nums[3] = 3, not paired, single in left (0 to 2).
• Step 2: left = 0, right = 2:
• mid = 1, adjust to 0, nums[0] = 1, nums[1] = 1, paired, single in right (2 to 2).
• Step 3: left = 2, right = 2:
• left == right, return nums[2] = 2.
• Result: 2.

Example: nums = [3, 3, 7, 7, 10, 11, 11]

• Init: left = 0, right = 6.
• Step 1: mid = 3, adjust to 2, nums[2] = 7, nums[3] = 7, paired, right (4 to 6).
• Step 2: left = 4, right = 6:
• mid = 5, adjust to 4, nums[4] = 10, nums[5] = 11, not paired, left (4 to 4).
• Step 3: left = 4, right = 4, return nums[4] = 10.
• Result: 10.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeclass Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        # Step 1: Initialize binary search bounds
        left, right = 0, len(nums) - 1

        # Step 2: Binary search with pair adjustment
        while left < right:
            mid = (left + right) // 2

            # Ensure mid points to first of pair
            if mid % 2 == 1:
                mid -= 1

            # Step 3: Check pair
            if nums[mid] == nums[mid + 1]:
                # Pair intact, single in right half
                left = mid + 2
            else:
                # Pair disrupted, single in left half
                right = mid

        # Step 4: Return single element
        return nums[left]

• Line 4: Set search bounds.
• Line 7: Loop until left meets right.
• Lines 10-12: Adjust mid to even index (first of pair).
• Lines 15-19: If pair matches, skip it (left moves past); else, single is left (right moves to mid).
• Line 22: left points to single element.
• Time Complexity: O(log n)—binary search halves space.
• Space Complexity: O(1)—no extra space.

It’s like a pair-disrupting detective!

Alternative Solution: Linear Scan with Pair Check

Why an Alternative Approach?

The linear scan with pair check iterates through the array in steps of 2, checking each pair for a mismatch to find the single element in O(n) time and O(1) space. It’s simple and intuitive but doesn’t meet the O(log n) requirement, making it a good baseline for understanding. Great for linear scan learners!

How It Works

Picture this as a pair-walking checker:

• Step 1: Iterate in steps of 2.
• Step 2: Check each pair:
• If nums[i] != nums[i+1], nums[i] is single.
• Step 3: Handle last element if unpaired.

It’s like a pair-stepping spotter!

Step-by-Step Example

Example: nums = [1, 1, 2, 3, 3, 4, 4]

• Step 1: Iterate:
• i=0: 1, 1—paired.
• i=2: 2, 3—not paired, return 2.
• Result: 2.

Example: nums = [3, 3, 7, 7, 10, 11, 11]

• Step 1: Iterate:
• i=0: 3, 3—paired.
• i=2: 7, 7—paired.
• i=4: 10, 11—not paired, return 10.
• Result: 10.

Code for Linear Scan Approach

Copy codeclass Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        # Step 1: Iterate in steps of 2
        for i in range(0, len(nums) - 1, 2):
            # Step 2: Check pair
            if nums[i] != nums[i + 1]:
                return nums[i]

        # Step 3: Handle last element if single
        return nums[-1]

• Line 4: Step by 2 to check pairs.
• Lines 6-7: If pair mismatches, return first element.
• Line 10: Return last if single (odd length ensures this).
• Time Complexity: O(n)—linear scan.
• Space Complexity: O(1)—no extra space.

It’s a linear pair checker!

Comparing the Two Solutions

• Binary Search (Best):
• Pros: O(log n), O(1), meets requirement.
• Cons: Binary logic.
• Linear Scan (Alternative):
• Pros: O(n), O(1), simple.
• Cons: Too slow for O(log n).

Binary search wins for efficiency!

Additional Examples and Edge Cases

• [1]: 1.
• [1, 1, 2, 2, 3]: 3.
• [7, 7, 10, 10, 11, 11, 12]: 12.

Binary search handles them all!

Complexity Recap

• Binary Search: Time O(log n), Space O(1).
• Linear Scan: Time O(n), Space O(1).

Binary search’s the speed champ!

Key Takeaways

• Binary Search: Pair power—learn at Python Basics!
• Linear: Simple but slow.
• Arrays: Singles are fun.
• Python: Binary or linear, your pick!

Final Thoughts: Find That Singleton!

LeetCode 540: Single Element in a Sorted Array in Python is a clever array challenge. Binary search with pair adjustment is your fast track, while linear scan offers a basic alternative. Want more? Try LeetCode 704: Binary Search or LeetCode 136: Single Number. Ready to search? Head to Solve LeetCode 540 on LeetCode and spot that single element today!