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

single element in sorted array problem description

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

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;

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

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.

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

--

--

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