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

single element in sorted array problem description
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;

}
  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

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

steps
  1. As with every binary search, it starts from the middle (divide the array into two halves);
  2. 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 (isEven)), there is no way the odd number would be in the second half if they are even.
  3. From the element at middle, it checks the element before it to know if they are equal.
  4. If they are equal and the variable isEven is true, it moves the right arrow to be at two elements before the middle element (mid-2). if the variable isEven is false, it moves the left arrow to start from an element after the middle element (mid+1).
  5. 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];
}

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Why so many RPA projects fail

HelloWorld Kubernetes Operator

Tips to Consider to Avoid Mobile Apps Crash

How to share Dynamic Variable among all Testcases in Cypress Automation

Changing the Color of Selection with CSS

GitHub Actions In Action

What the heck is… Le Wagon?!

Batch #253 nervously awaits the start of demo day.

Linked Lists:Data Structures::Peaches:Fruits

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Chunks

Chunks

More from Medium

A Simple explanation about 312.Burst Balloons

563. Binary Tree Tilt 🚀

How does bike rentals relate to insertion sort, online learning, and caching?

Quick Sort