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];
}
}