Search in rotated sorted array - Leetcode 33 - Python

wtf, I cannot even solve these problems, how can I get into big tech

it's such a motivating problem for a newbie in algorithms 😅

So, a bit late to the party, but just repeating one of the top comments. I basically found the pivot, and then based on how large the target is, search in one of the two sorted subarrays.

I felt that this solution is much more intuitive than the one here. Though understanding how to find the minimum was a pain.

Thank you very much

for me if target in nums:
return nums.index(target)
else:
return -1 this is what i understand

For those struggling with this problem I suggest working on Leetcode 153 or watch his explanation for LC 153.
That problem basically gives u an idea how to do BS on rotated arrays and then solving this problem becomes easier.
I personally tried solving this problem by my own , failed and then changed if statements to satisfy the test cases which were failing and finally got it to pass all cases. I then watched this vid and the approach was the same. Below is my solution -

class Solution:
def search(self, nums: List[int], target: int) -> int:
l = 0
r = len(nums) - 1
while l<=r:
mid = (l+r) //2
if nums[mid] ==target:
return mid
if nums[l] <= target < nums[mid] or target <= nums[mid] <=nums[r] or nums[mid] < nums[l] <= target:
r = mid -1
else:
l = mid + 1
return -1

To anyone who is still confused, here's a solution which is easier to understand with comments:
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l <= r:
m = (l + r) // 2
if nums[m] == target:
return m
# left portion
elif nums[l] <= nums[m]:
# target is in left portion
if nums[l] <= target < nums[m]:
r = m-1
# can be in either, because there are still elements bigger and smaller than target in the array, but remove left side of m
else:
l = m+1
# right portion
else:
# sure target is in right portion
if nums[m] < target <= nums[r]:
l = m+1
# can be in either, because there are still elements bigger and smaller than target in the array, but remove right side of m
else:
r = m-1
return -1

I did different than you, I think that is a little more simple:

class Solution:
def search(self, nums: List[int], target: int) -> int:
left = nums[0]
right = len(nums) - 1

while left <= right:
middle = (left + right) // 2
if nums[middle] == target:
return middle
elif nums[left] <= target:
right = middle - 1
elif nums[right] >= target:
left = middle + 1
return -1

hard question with so many edge cases

This is one of the easiest problems using python, this is the solution that I used:
class Solution:
def search(self, nums: List[int], target: int) -> int:
try:
return nums.index(target)
except:
return -1

You can find the pivot using a binary search, then do another usual binary search except this time with transformed index based on the rotation. It's a O(2 * log n) solution which should be evaluate to O(log n).

class Solution {
public int search(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l < r) {
int m = (l + r) / 2;
if (nums[m] > nums[r]) {
l = m + 1;
} else {
r = m;
}
}

int k = l; // l, r, m are all equals
l = 0;
r = nums.length - 1;
while (l <= r) {
int m = (l + r) / 2;
int mRotated = (m + k) % nums.length; // transformation happens here
if (nums[mRotated] == target) {
return mRotated;
} else if (nums[mRotated] > target) {
r = m - 1;
} else {
l = m + 1;
}
}
return -1;
}
}

I had worked out this solution, but just couldn't break it down into code. The moment I saw the simple comments "left sorted portion" and "right sorted portion" it was cake. Thanks Neet

And how exactly are you supposed to come up with this approach in an interview ?
There ain't no way my 95IQ can come up with a solution to anything other than an LC easy problem.

thiis question is really difficult to understand. so many cases!

this question was legit rocket science smh

I hate this one

nice

Everything fails when case is [1,1,2,1,1,1,1,1,1,1] someone please help 😭

i found this solution to be more intuitive. This problem is exact same as the Min Rotated Sorted Array pronlem.

so for the Min Rotated Sorted Array problem, the solution is like this

def findMinRotatingElement(nums):
left = 0
right = len(nums) - 1
'''
logic is this: do the binary search, compare the mid value with the most right value
if mid is larger, meaning the min value is on the top half, update left = mid + 1
else the min value is on the bottom half, update right = mid

once l = r
we found the solution
'''
while left < right:
mid = (left + right) // 2
midValue = nums[mid]
if midValue > nums[right]:
left = mid + 1
elif midValue <= nums[right]: # this indicated that the mid value could also be the smallest value, so we need
# to include it as well. That 's why we dont do right = mid -1 but set right = mid to include it
right = mid
return nums[right]


but for this problem, it 's the exact same thing but with one extra step. From the previous solution, we have the index of the rotation element, basically look up that element at that index and compare with target, if they are equal, return the index, if not return -1 ""

so essentially it 's like this


def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]:
left = left + 1
else:
right = mid
if nums[left] == target:
return left
else:
return -1

My head hurts🤯How this seemingly easy problem becomes so complex, I hate leet code mannnnnnn. TY for making it easier, I kept failing test cases because I didn't identify I needed to be looking at whether I was at left sorted or right sorted portion ugggghhhhhh

what is that software you used to explain the algorithm ?

I feel like this solution makes slightly more sense:

left = 0
right = len(nums) - 1
while left <= right:
middle = (left + right) // 2
if target == nums[middle]:
return middle

# target is in left side
if target >= nums[left] and target <= nums[middle]:
right = middle - 1

# target is in right side
else:
left = middle + 1
return -1

I was able to solve this problem without looking at the solution, only by updating my code seeing which test cases were failing. If test cases weren't visible, would not have been able to solve it. It was tricky as anything.

yea this is just a lot of case work, easy to miss smtg

this is easy to understand but hard to write running code without bugs

i knew the methods but so many things we were testing and it tripped me off

My algo centers around doing normal binary search. So first it searches for the sorted portion of the array and then it does normal binary search. It's easier to know your cases that way, here they are:
A left is sorted and midpoint falls in left
B right is sorted and midpoint falls in right
C the whole array is sorted
D left is sorted but midpoint falls in right
E right is sorted but the midpoint falls in left

The first 3 cases are super easy. The portion of the array you want the midpoint in is sorted, so you can run normal binary search. How to deal with the last 2? Simple, you update l and r. Here's how that works:

* left is sorted but midpoint falls in right: l = m + 1, loop again
* right is sorted but midpoint falls in left: r = m - 1, loop again

By looping again, at some point you'll hit one of the first 3 cases and just do a normal binary search. Here's the code.

I came up with this after 20 minutes. It was my second attempt. In my first attempt I had a different way of structuring my cases, but after 45 min. I realized it was fruitless so I restarted the problem.

The code looks like a lot, but normalBinarySearch is super quick to type. The functions were super quick to type. The destructuring was super quick and putting out the cases was super quick. The only part I found difficult were what to do with case D and E that took up my brain space for a bit.

var search = function(nums, target) {
let l = 0
let r = nums.length - 1
while (l <= r) {
let m = Math.trunc( (l+r)/2 )
const [isLeftSorted, isRightSorted] = isSorted(nums[l], nums[m], nums[r])
const [fallsInLeft, fallsInRight] = midpointFallsIn(nums[l], nums[m], nums[r], target)
if (isLeftSorted && isRightSorted) {
return normalBinarySearch(nums, target, l, r)
}
else if (isLeftSorted && fallsInLeft) {
return normalBinarySearch(nums, target, l, m)
}
else if (isRightSorted && fallsInRight) {
return normalBinarySearch(nums, target, m, r)
}
else if (isLeftSorted) { //go right
l = m + 1
}
else if (isRightSorted) { //go left
r = m - 1
}
}
return -1
};

function isSorted(left, mid, right) {
return [left <= mid, mid <= right]
}

function midpointFallsIn(left, mid, right, target) {
return [left <= target && target <= mid, mid <= target && target <= right]
}

function normalBinarySearch(nums, target, l, r) {
while (l <= r) {
let m = Math.trunc( (l+r)/2 )
if (nums[m] === target) return m
else if (nums[m] < target) l = m + 1
else if (nums[m] > target) r = m - 1
}
return -1
}

thanks, you always have the best explanation

The visualization did wonders to help me tackle this problem. I didn't even have to look at the actual implementation to solve it after looking at it!

this was asked to me in the first round of an interview

I found the left/right sorted portions explanation a bit hard to digest. One other of seeing things that convinced me better is as follows:
if nums[l] <= nums[mid] is True ==> the sub array from l to mid is sorted.
else => the other sub array from mid to r is sorted.
Indeed, we can only have one unsorted subarray which includes the pivot.
Once we think of subarrays as sorted or unsorted, the idea is to check if target is within the sorted subarray if it is, move the left/right to mid to seach within the sorted portion. If target is outside the sorted portion. Keep searching in the unsorted portion by splitting it into a sorted and unsorted parts and repeating the process.

My solution: find the pivot and do binary search on both arrays (left from pivot and right from pivot)

class Solution:
@staticmethod
def binary_search(nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
first_true_index = -1
while left <= right:
mid = (left + right) // 2
if nums[mid] >= target:
if nums[mid] == target:
first_true_index = mid
right = mid - 1
else:
left = mid + 1
return first_true_index

def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
first_true_index = -1
while left <= right:
mid = (left + right) // 2
if nums[mid] <= nums[-1]:
first_true_index = mid
right = mid -1
else:
left = mid + 1
result_1 = self.binary_search(nums[:first_true_index], target)
result_2 = self.binary_search(nums[first_true_index:], target)
if result_1 != -1:
return result_1
if result_2 != -1:
return len(nums[:first_true_index]) + result_2
return -1

This is totally unclear and wrong in many test cases. You are not checking whether middle is pivot or not. This major flaw can be seen when your method fails if you have array rotated as [6,1, 2, 3, 4, 5] and you have to search for 1. The 2nd thing which is wrong is the middle value cannot be 6. It has to be 7.

Most interviewer's consider the complexity as O(n) if we use len() of python. How can we deal with such situations as most of your solutions has used len()?

This statement being true doesn't mean you are on the left part: "nums[L] <= nums[mid]" It just means the "fault line" isn't between L and mid. You could very well be way over to the right when that evaluates to true. Why is everyone saying this explanation is clear? It seems like he got a working solution by accident despite not understanding it.

finding pivot using binary search in O(log n) then performing another binary search O(log n) to find the key will be little easier but little time intensive but still better than O(n)

I struggled with this problem for 3+ years and tried to memorize the solution as I was always got confused when thinking many different options. This is the best explanation.

Could also find the pivot in log(n) and then have two sorted array which could be used to do simple binary search which is still log(n)

Is NeetCode supposed to rhyme with LeetCode?

This question should be marked Double Hard

TO find the target belows what I did.
First I found if list is rotated or not, If last element < first element. List is rotated an no matter what permutation you choose it will remain this way
[4,5,6,7,0,1,2]
If its rotated We divide the array into 2 logical sorted arrays, How.
Take a pointer at last element and start finding minimum element from last pointer. IN above case 0 is minimum at index 4.
So 2 lists are 0: 4 < 0 element is not included here and 4:6(len of array - 1).

Now we first do Binary search on first, if not found second and then return -1 or answer.

If array is not rotated at all we just apply binary search directly.

the way this solution is described and written is so counterintuitive, why not just adjust pointer based on where target is instead of where it's not lolll

This is a deceptively complex problem. Normally, they say if you're writing a lot of complex nested logic, it means you're doing too much or something wrong.

Turns out in this case, this problem is the exception. The solution isn't as intuitive or elegant as one would expect, but it's necessary and not too difficult.

Goes to show you, any correct soluton you can achieve at first is your best answer, then you can work your way to reduce the complexity later if it's possible.

@Neetcode
it must and condition and not or .

Here is the correct solution :
class Solution:
def search(self, nums: List[int], target: int) -> int:
# we can run a single loop to locate the target but that is not needed here,
# we need something in O(log N)

leftPt = 0
rightPt = len(nums) - 1

while leftPt <= rightPt:

middlePt = (leftPt + rightPt) // 2

if nums[middlePt] == target:
return middlePt

# first find out where is middlePt at
if nums[leftPt] <= nums[middlePt]:
# middlePt is at left part of the array
if target < nums[middlePt] and target >= nums[leftPt]:
rightPt = middlePt - 1
else:
leftPt = middlePt + 1

else:
# middlePt is at right part of the array
if target > nums[middlePt] and target <= nums[rightPt]:
leftPt = middlePt + 1
else:
rightPt = middlePt - 1
return -1

I started watching your videos for Blind 75. This was the first one I made without watching any video. Your video optimizes what I did, though. Great job!

Much easier to understand solution (updated conditions):

class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1

while l <= r:
mid = (l + r) // 2

if target == nums[mid]:
return mid

# left sorted portion
if nums[l] <= nums[mid]:
if nums[l] <= target < nums[mid]:
r = mid - 1
else:
l = mid + 1
# right sorted portion
else:
if nums[mid] < target <= nums[r]:
l = mid + 1
else:
r = mid - 1

return -1