This is one of the first problems I’ve seen that I have not liked the answer that Neetcode gave (at least in his solution video - he does offer several approaches on his site). In his answer, we essentially have to handle 6 different cases for every search iteration. It’s like this compound of logic, where we use comparisons of the left side of the window with the middle and the middle with the target to see which way we should “travel” with our next window/middle calculation depending on which side of the “pivot point” we determine we are.
class Solution {
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
search(nums, target) {
let l = 0, r = nums.length - 1;
while (l <= r) {
const mid = Math.floor((l + r) / 2);
if (target === nums[mid]) {
return mid;
}
if (nums[l] <= nums[mid]) {
if (target > nums[mid] || target < nums[l]) {
l = mid + 1;
} else {
r = mid - 1;
}
} else {
if (target < nums[mid] || target > nums[r]) {
r = mid - 1;
} else {
l = mid + 1;
}
}
}
return -1;
}
}Watching Neetcode, I can see that it clearly makes sense to him, but to me it’s just so much index fiddling and abstract window logic that I know that it would take a me a really long time to be able to do this under pressure, and I probably would achieve that mostly through memorization. So hats off to him for really being able to grok it in the moment, while explaining it.
In the comments, a few people mentioned the strategy of breaking down the problem by first finding the pivot point, and immediately this felt like the more reasonable way to do this problem. It also is what I intuitively thought of first, but my brain has grown weary from leetcode and I reached out to see what others were doing before testing that potentially faulty hypothesis (I know - I might have taken my philosophy of “learn from others with more experience and conserve my own problem-solving energy” a little too far).
Although this problem chunking approach requires writing three separate functions, only one of those functions is challenging AND novel - findPivot
function findPivot(nums: number[]): number {
let left = 0;
let right = nums.length - 1;
if (nums[left] <= nums[right]) return 0;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] > nums[mid + 1]) return mid + 1;
if (nums[mid - 1] > nums[mid]) return mid;
if (nums[left] <= nums[mid]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return 0; // Default case (shouldn't reach here)
}
// Standard binary search on a sorted array
function binarySearch(nums: number[], target: number, start: number, end: number): number {
while (start <= end) {
const mid = Math.floor((start + end) / 2);
if (nums[mid] === target) return mid;
if (nums[mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return -1;
}
// Main function to search in rotated array
function search(nums: number[], target: number): number {
if (nums.length === 0) return -1;
// Find the pivot point
const pivot = findPivot(nums);
if (pivot > 0 && target >= nums[0]) return binarySearch(nums, target, 0, pivot - 1);
return binarySearch(nums, target, pivot, nums.length - 1);
}At the very least, the findPivot function feels like a great encapsulation of navigating a rotated array.
Despite disagreeing with his recommended implementation within the context of coding interviews, I still am taking a page out of Neetcode’s book - I decided to record my exploration and understanding of this findPivot function and its edge cases so I could grok it a bit better. I found the process of explaining my code on paper really helpful: