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

1. Loop through the array by incrementing the count by two (2);
2. check if the current element is equal to the next element;
3. 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;    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.

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