Solution For Single Element In A Sorted Array
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:
- Initialize left and right pointers with 0 and length of array – 1 respectively.
- 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. - 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).
Step by Step Implementation For Single Element In A Sorted Array
class Solution { public int singleNonDuplicate(int[] nums) { //check for empty array if(nums.length == 0){ return 0; } //check for single element array if(nums.length == 1){ return nums[0]; } //binary search solution int left = 0; int right = nums.length - 1; while(left < right){ int mid = left + (right - left)/2; //if the mid element is not equal to either of its adjacent elements, it is the single element if(nums[mid] != nums[mid+1] && nums[mid] != nums[mid-1]){ return nums[mid]; } //if the mid element is equal to the element to its right, that means the single element is on the left side else if(nums[mid] == nums[mid+1]){ //if the mid element is even, the single element is to the left of mid-1 if(mid % 2 == 0){ right = mid - 1; } //if the mid element is odd, the single element is to the left of mid+1 else{ left = mid + 2; } } //if the mid element is equal to the element to its left, that means the single element is on the right side else{ //if the mid element is even, the single element is to the right of mid+1 if(mid % 2 == 0){ left = mid + 2; } //if the mid element is odd, the single element is to the right of mid-1 else{ right = mid - 1; } } } return nums[left]; } }
class Solution: def singleNonDuplicate(self, nums: List[int]) -> int: # edge case: empty list if not nums: return None # edge case: list of length 1 if len(nums) == 1: return nums[0] # initializing left and right pointers left = 0 right = len(nums) - 1 # binary search while left < right: # find the middle element mid = left + (right - left) // 2 # if the middle element is not the single element if nums[mid] != nums[mid-1] and nums[mid] != nums[mid+1]: # the single element must be to the left right = mid # if the middle element is the single element else: # the single element must be to the right left = mid + 1 # return the single element return nums[left]
var singleNonDuplicate = function(nums) { // edge case: if (nums.length === 1) { return nums[0]; } // set up pointers let left = 0; let right = nums.length - 1; // as long as the pointers haven't crossed: while (left < right) { // find the middle element let mid = Math.floor((left + right) / 2); // if the middle element is equal to its neighbor to the right: if (nums[mid] === nums[mid + 1]) { // the single element must be to the left of the current middle element right = mid; // if the middle element is equal to its neighbor to the left: } else if (nums[mid] === nums[mid - 1]) { // the single element must be to the right of the current middle element left = mid + 1; // otherwise, the single element must be the current middle element } else { return nums[mid]; } } // if the pointers have crossed, the single element must be at the left pointer return nums[left]; };
class Solution { public: int singleNonDuplicate(vector& nums) { // Your code here } };
public class Solution { public int SingleNonDuplicate(int[] nums) { // check for empty or null array if (nums == null || nums.Length == 0) { return -1; } // set left and right pointers int left = 0; int right = nums.Length - 1; // while the left pointer is less than the right pointer while (left < right) { // calculate the middle index int mid = left + (right - left) / 2; // if the middle index is even if (mid % 2 == 0) { // if the number at the middle index is the same as the number at the middle index + 1 // then the single element must be on the right side of the array so we move the left pointer if (nums[mid] == nums[mid + 1]) { left = mid + 2; } // otherwise the single element must be on the left side of the array so we move the right pointer else { right = mid; } } // if the middle index is odd else { // if the number at the middle index is the same as the number at the middle index - 1 // then the single element must be on the right side of the array so we move the left pointer if (nums[mid] == nums[mid - 1]) { left = mid + 1; } // otherwise the single element must be on the left side of the array so we move the right pointer else { right = mid - 1; } } } // at this point the left pointer will be equal to the right pointer and that will be the index of the single element return nums[left]; } }