# The Good, The Bad, The Ugly Solutions to Leetcode’s Single Element in a Sorted Array

This is a medium Leetcode 543 question. You are given an array of integers of which all elements in the array appear twice **except one.** The question is to get the one that does not have any duplicate (i.e appeared just once). See problem description below:

*NOTE: The solution should be in O(log n) and O(1) space.*

The above problems can be solved in so many ways but I will talk about three ways to solve it in decreasing order of performance.

**FIRST ALGORITHM (THE UGLY)**

The first solution that came to my mind was to use a HashMap. There is a saying that goes thus;

For every question you encounter, always think HashMaps, there is a probability that you will solve the problem with HasMap

😂😂😂.

The idea is to store the count of elements in the array inside a HashMap with the element as the key and the count as the value.

Then next step is to loop through return the key that its value is 1 because if the value is 1, definitely that’s the odd one. The code is shown below:

**public int singleNonDuplicateUsingHashMap***(*int*[] *nums*) {*

HashMap*<*Integer, Integer*> *map = new HashMap*<>()*;

//store the count of each element in the map

for *(*int i = 0; i < nums.length; i++*) {*

if *(*!map.containsKey*(*nums*[*i*])) {*

//if the key doesn't exist, create a new one

map.put*(*nums*[*i*]*, 1*)*;

*}*else *{*

//update the count of the existing by incrementing it by 1

map.put*(*nums*[*i*]*, map.get*(*nums*[*i*]) *+ 1*)*;

*}*

}

//loop through map and get the one that has the value of 1

for *(*Map.Entry*<*Integer, Integer*> *entry : map.entrySet*()) {*

if *(*entry.getValue*() *== 1*) {*

return entry.getKey*()*;

*}*

}

return -1;

*}*

The above code works just fine but the runtime is **O(n) **for each of the loops which translates to **O(n) + O(n) **which is equal to **2O(n). 2O(n) **is the same as **O(n) **because we don’t consider constants in calculating runtime. To make this slightly better, let’s look at another algorithm.

**SECOND ALGORITHM (THE BAD)**

- Loop through the array by incrementing the count by two (2);
- check if the current element is equal to the next element;
- if they are not, that means that current element is the odd one without a duplicate. See the steps in the image below;

**STEPS**

The first step starts from element at index 0(i=0), checks if the next element at index(i+1) is the same. Since they are the same, it increments the index (** i)** by 2. it follows the same process for Step 2.

For step 3 which is at index 4, it checks and finds out they are not the same, so it returns value at the current index (** i=4**)which is 10. The code is shown below:

**public int singleNonDuplicateLinearly***(*int*[] *nums*) {*

if *(*nums.length == 1*) *return nums*[*0*]*;

for *(*int i = 0; i < nums.length; i+=2*) {*

if *(*i == nums.length - 1*) *return nums*[*i*]*;

if *(*i+1 < nums.length && nums*[*i*] *!= nums*[*i+1*]) {*

return nums*[*i*]*;

*}*

}

return -1;

*}*

## THIRD ALGORITHM (THE GOOD😎😎😎)

If you look at the problem description, it says that the runtime should be **O(log n)** and space complexity of O(1).

Whenever you see a question that says runtime should be O(log n) and space complexity of O(1), just know that the solution would probably involve

Binary Search.

- As with every binary search, it starts from the middle (divide the array into two halves);
- checks the right half elements to know if they are even number of elements left. if they are even (stores the state in a variable (
)), there is no way the odd number would be in the second half if they are even.*isEven* - From the element at middle, it checks the element before it to know if they are equal.
- If they are equal and the variable
is true, it moves the right arrow to be at two elements before the middle element (*isEven*). if the variable*mid-2*is false, it moves the left arrow to start from an element after the middle element (*isEven***mid+1**). - If they are not equal, and
*isEven*is true, it moves the left arrow to two elements after the middle element. If they are not equal, it right arrow to an element before the middle element.

**public static int singleNonDuplicateUsingBinarySearch***(*int*[] *nums*) {*

int lowLeft = 0;

int highRight = nums.length-1;

boolean isEven;

while *(*highRight > lowLeft*) {*

int mid = lowLeft + *(*highRight - lowLeft*) */2;

//check if the right side is even

isEven = *(*highRight - mid*) *% 2 == 0;

if *(*nums*[*mid*] *== nums*[*mid-1*]) {*

if *(*isEven*) {*

highRight = mid - 2;

*}*else *{*

lowLeft = mid + 1;

*}*

}else if *(*nums*[*mid*] *== nums*[*mid + 1*]){*

if *(*isEven*) {*

lowLeft = mid + 2;

*}*else *{*

highRight = mid - 1;

*}*

}else *{*

return nums*[*mid*]*;

*}*

}

return nums*[*lowLeft*]*;

*}*

Thank you for reading. Please drop a comment.