For any Algorithm question, whenever you see a keyword Sorted think of Binary Search
In the given problem, there is one unique element and rest of all the elements are paired, also the elements are in sorted array
Let's consider this example, with start and end index pointing to first and last element of the array
nums = [1,1,2,3,3,4,4,8,8]
Now the mid is 3
if you analyze the diagram
- nums[mid] == nums[mid - 1]
Now there are two cases
- Either the element lies from start to mid
- Or the element lies from mid to end
You can say the element lies in a part where the length is not even
So the conditions will be
- if mid to end is even then the element lies from start to mid, so
end = mid - 2
. Whymid - 2
because we don't want to iteratenums[mid]
andnums[mid - 1]
again - if mid to end is odd then the element lies from mid to end, so
start = mid + 1
Now Let's consider a case where nums[mid] == nums[mid + 1]
The conditions for this scenario is
- if start to mid is even, then element lies from mid to end, so
start = mid + 2
- else
end = mid - 1
Now there comes a scenario where nums[mid] is not equal to nums[mid + 1] or nums[mid -1], that's the element we have to return
Here is the code
var singleNonDuplicate = function(nums) {
let start = 0, end = nums.length - 1
while(start <= end) {
let mid = Math.floor((start + end) / 2)
if(nums[mid] == nums[mid - 1]) {
let isEven = (end - mid) % 2 == 0
if(isEven) {
end = mid - 2
} else {
start = mid + 1
}
} else if(nums[mid] == nums[mid + 1]) {
let isEven = (mid -start) % 2 == 0
if(isEven) {
start = mid + 2
} else {
end = mid - 1
}
} else {
return nums[mid]
}
}
};
Top comments (0)