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:

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).

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