Teaching to learn: Single Element in a Sorted Array

Leetcode: Single Element in a Sorted Array

This post is part of series where I will be breaking down coding problems that I have solved and sharing the lessons I learned while finding an answer. The coding language will be in JavaScript.

Single Element in a Sorted Array is brief and to the point. It asks us to simply find a single integer among the duplicate integers in the array and return it. The catch is: there is a note requesting that we do this in O(log(n)) time and O(1) space.

Even though the note is asking us for this specific time complexity I am going to start off by showing the brute force approach that first popped into my head. After that I will show you how I was able to improve the time complexity using a Binary Search algorithm. Off we go!

Understanding the problem

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

Note: Your solution should run in O(log n) time and O(1) space.”

As I said before we are simply looking for a single integer that is not duplicated in the array. We are guaranteed that all other integers in the same given array will have a clone.

The following pseudo-code is the steps I came up with for a brute force solution which does not meet the required O(log(n)) time complexity. I like to write out the most obvious solutions first even if they are slow and less efficient than others. Doing so can provide insights into the problem you might not have noticed if you tried to go straight for efficiency or cleverness.

Pseudo-code:

1. Define a variable i which will be set to nums.length -1
2. Loop while nums.length is > 0. Inside the while loop:
3. If nums[i] === nums[i -1] then pop from nums twice and then subtract 2 from i
4. Else return nums[i]

I am looping through nums backwards in the above steps, starting i at the end of our nums array and decreasing it by 2 each time we know that the current value (nums[i]) is equal to the previous value in the array (nums[i -1]).

We have to decrease i by 2 when we find values next to each other to prevent from getting a false positive. Say we have an array [0,0,1,1,2,2,3,4,4] with length of 9. If we are at index 8 (the end of the array) and we see that index 7 is the same value (4) then we know that 4 is not our answer.

If we continue to loop and decrement our counter by just 1 then we would look at index 7 and see that index 7 (4) does not equal index 6 (3) and we would return index 7 (4) which is incorrect. This is why we have to decrement i by two when we have found matching values.

The code:

O(n) Time Complexity / O(1) Space Complexity

Our worst case time with this solution would be if the single-integer was at the beginning of the array. We would have to check all indices in the array before we found our solution which gives us a worst case time complexity of O(n).

This solution was accepted by Leetcode (there are only 12 test cases at the moment for this challenge). Although it was accepted it does not meet the requirements specified in the note:

“Note: Your solution should run in O(log n) time and O(1) space.”

Now that we have seen the simple solution lets try and optimize using a Binary Search algorithm.

Another solution:

In order to use Binary Search we need to think about how we would split our nums array in half in order to reduce the number of iterations we have to perform to find our answer. What is the condition that would make us look at the left side of the nums array, or the right side?

Since we know that each value that is not our answer has a matching value next to it in the nums array (since the array is sorted) we can check the values to the left and right of our current value to see if it has a match and adjust our search accordingly if we find a matching value. If we do not find a matching value to the left or right of our current value then that means we have found our single integer in the array and can return the current value.

Here are the steps we can take to implement such a solution.

Pseudo-code:

1. Define left and right variables
2. Set left to 0 and right to nums.length
3. Loop while left <= right. Inside while loop:
4. Define mid variable which is rounded down (left+right / 2) (this is how we split the nums array into left and right sides)
5. (if) nums[mid] === nums[mid + 1]: if mid is even: left = mid + 1, else right = mid
6. (else if) nums[mid] === nums[mid — 1]: if mid is even: right = mid, else left = mid + 1
7. (else) return nums[mid] (we found the single integer answer)

The if statements are checking to see if we need to move our boundary on the right side lower or move our boundary of the left side higher.

Our focal point is on the variable mid.

If mid is equal to mid + 1 and mid is even then we want to look to the right of the current value of mid. In this case we know that our current mid value cannot be the answer because it has a match to the right of it. Since the number of values including mid is even we know that our single-integer answer cannot be on the left side of the array (since there is an even number of values on the left side of the array and every value has exactly 1 matching partner, it is impossible for there to be an even number of values on the side of the array that would have our single-integer answer). We need to look at everything on the right side of the array excluding current mid.

This logic is used in opposite context for searching the left side of the current mid value. Each time we are cutting out half of the possible values that could be our solution until eventually we land on our solution by process of elimination. Good old divide and conquer.

Let’s see what the code looks like.

The code:

O(log(n)) Time Complexity / O(1) Space Complexity

You could also implement this Binary Search solution recursively. However this version does the very same thing a recursive version would do.

That is all the insight I have relating to this challenge. I hope it has helped you or at least entertained. If you have another way of solving this challenge or any tips, let me know!