Single Element in a Sorted Array

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

Return the single element that appears only once.

Your solution must 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

Approach

Using the brute force approach, we first declare an object to store the frequency of each element. After saving the frequencies, we find the key with the value of 1.

const obj = {}
nums.forEach(x => {
    if(obj && obj[x]){
        obj[x] = obj[x] + 1
    }else{
        obj[x] = 1;
    }
})


return Object.keys(obj).find(x => obj[x] === 1)

• Time Complexity: O(n) - Iterating through the array once to count frequencies: O(n), where n is the number of elements in the array nums.
• Auxiliary Space: O(n) - Storing frequencies in an object: O(n), as it requires additional space proportional to the number of distinct elements in the array.

Optimized Approach

This approach utilizes the two-pointer technique to efficiently find the single element in a sorted array. By initializing two pointers, i and j, to adjacent indices, I traverse the array with the condition that i remains less than j and within the bounds of the array.

During traversal, if the elements at indices i and j are equal, I increment both pointers by 2, effectively skipping the pair. However, when encountering unequal elements, I check if the next element, nums[j+1], is equal to nums[j]. If it is, it indicates that the single element lies before nums[j]. In this case, I mark nums[i] as the single element and exit the loop.

let i = 0, j = 1;
let singleElement = 0;
while(i<j && i<=nums.length - 1){
    if(nums[i] == nums[j]){
       i = i+2;
       j =  j+2
    }else{
       
        if(nums[j] == nums[j+1]){
            singleElement = nums[i]
            break;
        }
    }
}
     
     return singleElement
};

• Time Complexity: O(n) - Traversing through the array once to identify the single element.
• Space Complexity: O(1) - Utilizing a constant amount of extra space for storing variables i, j, and singleElement.