Single Element In A Sorted Array - Leetcode Solution

The Single Element In A Sorted Array problem on LeetCode is a popular problem that requires finding the element that appears only once in a sorted array. In other words, given a sorted array where each element appears twice except for one element, the task is to find the element that appears only once.

To solve this problem, we can use binary search since the array is sorted. The approach involves comparing the mid element of the array with its adjacent element to determine if the single element lies on the left or right side of the array. We repeat the comparison on the sub-array where the single element is expected to be found until we find the single element.

Algorithm:

1. Initialize left and right pointers with 0 and length of array - 1 respectively.
2. While left is less than or equal to right, perform the following steps: a. Compute mid as (left + right) / 2. b. Check if the mid element is the single element by comparing it with its adjacent elements. i. If the mid element is the single element, return it. ii. Else, if mid is even and mid+1 element is equal to mid element, the single element lies on the right side of the mid. So, we update our left pointer to mid+2. iii. Else, single element lies on the left side of the mid. Update right pointer to mid - 1.
3. If the loop terminates without finding the single element, return -1.

Code:

Here is the Python code for the above algorithm:

def singleNonDuplicate(nums: List[int]) -> int: n = len(nums) left, right = 0, n-1 while left <= right: mid = (left + right) // 2 if mid == 0 or mid == n-1: # edge case return nums[mid] if nums[mid] != nums[mid-1] and nums[mid] != nums[mid+1]: return nums[mid] elif nums[mid] == nums[mid-1] and mid % 2 == 0: right = mid - 1 elif nums[mid] == nums[mid+1] and mid % 2 == 1: right = mid - 1 else: left = mid + 1 return -1

Time Complexity: The time complexity of our solution is O(log N) because we are cutting the search area in half after each iteration of the loop.

Space Complexity: The space complexity of our solution is O(1). We are not using any extra space, just manipulating the given input array.

In conclusion, the Single Element In A Sorted Array problem on LeetCode can be solved using binary search. We compare the mid element with its adjacent elements and proceed to search on the left or right side of the mid depending on the values of the adjacent elements. This approach has a time complexity of O(log N) and a space complexity of O(1).

1