Leetcode 540 - Single Element in a Sorted Array

Understanding the problem

The problem statement on LeetCode reads as follows:

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once.

Follow up: Your solution should run in O(log n) time and O(1) space.

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

Plan your solution

One way to solve this problem is to use a binary search algorithm. Since the array is sorted, we can take advantage of this property to find the single element that appears only once in O(log n) time.

We can start by setting the left and right pointers to the first and last elements in the array, respectively. Then, we can check if the middle element is equal to its left or right neighbor. If it is equal to its left neighbor, it means that the single element is on the right side of the array, so we can move the left pointer to the middle point between the left and right pointers. On the other hand, if it is equal to its right neighbor, it means that the single element is on the left side of the array, so we can move the right pointer to the middle point. We can repeat this process until the left and right pointers meet. This will give us the single element that appears only once.

Implement your solution

Now that we have a plan, let’s implement it in Python.

class Solution:
   def singleNonDuplicate(self,nums):
        # Set the left and right pointers to the first and last elements in the array
        left, right = 0, len(nums) - 1

        # While the left pointer is less than the right pointer
        while left < right:
            # Calculate the middle point between the left and right pointers
            mid = (left + right) // 2

            # Check if the middle element is equal to its left or right neighbor
            if nums[mid] == nums[mid - 1]:
                # If it is equal to its left neighbor, it means that the single element is on the right side of the array
                left = mid + 1
            elif nums[mid] == nums[mid + 1]:
                # If it is equal to its right neighbor, it means that the single element is on the left side of the array
                right = mid - 1
            else:
                # If it is not equal to either its left or right neighbor, it means that the middle element is the single element
                return nums[mid]

        # Return the left pointer (which is the single element)
        return nums[left]

Test your solution

Testing is an important step in the software development process, as it helps ensure that your code is correct and works as intended. In the case of the “Single Element in a Sorted Array” problem, we can test our solution by running a series of test cases that cover different scenarios and edge cases.

For example, we can test our solution with an array of length 1, an array of length 2, an array of length 3, and so on. We can also test our solution with arrays that have the single element at the beginning, middle, or end of the array. By running a variety of test cases, we can gain confidence that our solution is correct and will work for all inputs.

Related:

• binary subarrays with sum
• maximum average subarray i
• search in rotated sorted array
• kth smallest element in a bst with code

Related Posts

• Leetcode 424 - Longest Repeating Character Replacement
• Two Sum and Its Variants
• Leetcode 1004 - Max Consecutive Ones III
• Leetcode 222 - Count Complete Tree Nodes
• Leetcode 1027 - Longest Arithmetic Subsequence
• Question 1299 on leetcode
• Leetcode 240 - Search a 2D Matrix II
• Leetcode 1351 - Count Negative Numbers in a Sorted Matrix
• Leetcode 239 - Sliding Window Maximum
• Leetcode 209 - Minimum Size Subarray Sum
• LeetCode 230 - Kth Smallest Element in a BST with Code
• advanced-applications-of-binary-search
• Leetcode 96 - Unique Binary Search Trees
• Leetcode 1283 - Find the Smallest Divisor Given a Threshold
• Leetcode 74 - Search a 2D Matrix
• Leetcode 300 - Longest Increasing Subsequence
• Leetcode 930 - Binary Subarrays With Sum
• Blazingly fast solution to LeetCode #1342 - Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold (Cross-post from r/SoftwareEngineering)
• Leetcode 704 - Binary Search
• Leetcode 643 - Maximum Average Subarray I
• LeetCode - Two Sum Solution with Code
• a-binary-search-template
• Leetcode 1358 - Number of Substrings Containing All Three Characters
• Leetcode 33 - Search in Rotated Sorted Array
• Leetcode 1151 - Minimum Swaps to Group All 1’s Together