Search in rotated sorted array - Leetcode 33 - Python

0:00 - Conceptual
8:55 - Coding solution

#Coding #Programming #CodingInterview

Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[expansivegymnast]

This is lowkey one of the hardest problems I've done so far. Great video!

[wonderfulsnow]

You can use binary search to find the pivot index, and then another binary search in the appropriate part of the array.

[symbol]

This problem was difficult as hell because of how we need to setup so many conditions and move the pointers correctly depending on where we are currently with mid pointer, jeez. I hate this problem honestly.
Thank you for your solution, liked and commented for support.

[danielgareev]

For me this solution was a bit more intuitive:

l = 0
r = len(nums) - 1

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

if nums[mid] == target:
return mid

# left sorted portion
elif nums[mid] >= nums[l]:
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

[kevindebruyne]

One of the most annoying questions of Leetcode explained so easily! I hope I could develop the skill to implement this without getting confused again and again! Amazing work!

[iamsmitthakkar]

thanks for the solution. For those who gets confuse in the if conditions (just like me) in this solution, you can refer to below solution. It works

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 array
if nums[l] <= nums[mid]:
# make sure target is in between num[l] and nums[mid]
if target >= nums[l] and target < nums[mid]:
r = mid - 1
else:
l = mid + 1
# right sorted array
else:
# make sure target is in between num[mid] and nums[r]
if target > nums[mid] and target <= nums[r]:
l = mid + 1
else:
r = mid -1
return -1

[ThePacemaker]

First leetcode medium I was able to solve by myself without looking at the solution cause of your solution vid for Problem 153. I know it's just baby steps but it's sooo encouraging. Thank you so much man 😅

[tanvirahmed]

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.

[wfbpzuu]

That "or" is what got me. I figured out you could check for either condition, but not that you had to check both.

I got confused and assumed that knowing whether you were in the right/left sorted portion gave you some bounds guarantees, and you only had to check one of the conditionals.

Going to spend some time drawing this out to make sure it sunk. Thank you so much NeetCode!

[legspinismylife]

array problems make me feel like i have IQ below 80

[kryddan]

I think of it like this:

if mid > than R, everything left of mid is sorted
if mid < than R, everything right of mid is sorted

Check if target would fall into the range of the sorted part, and if so move the L or R pointer to binary search that segment. Otherwise move to the unsorted segment and repeat:

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

EDIT: I see that multiple people came up with this version already 👍

Another solution I came up with is using a modified version of binary search to locate the pivot index. Then check if the target falls into the right of left side of the pivot and use binary search on that segment.

def binary_search(nums, target, l, r):
while l <= r:
mid = (l + r) // 2
if nums[mid] == target:
return mid
if nums[mid] > target:
r -= 1
else:
l += 1
return -1


def find_pivot(nums, target):
l, r = 0, len(nums) - 1
if len(nums) == 1:
return 0 if nums[0] == target else -1
while nums[l] != nums[r]:
pivot = (l + r) // 2
if nums[pivot] > nums[r]:
if l == pivot:
break
l = pivot
else:
r = pivot
if nums[pivot] == target:
return pivot
if nums[pivot + 1] <= target <= nums[-1]:
return binary_search(nums, target, pivot + 1, len(nums) - 1)
else:
return binary_search(nums, target, 0, pivot - 1)

[legendarygaming]

very clearly explained. Thank you for this. I was also considering the right rotated array and was trying to find a generalised soln. guess that the question only demanded for the left roated array.

[free-palestine]

this has been one of the most solutions to wrap my head around for some reason

[sidazhong]

if nums[l] <= nums [m]:
if nums[l] <= target < nums[m]:
r = m-1
else:
l = m+1
else:
if nums[m] < target <= nums[r]:
l = m+1
else:
r = m-1

I think this way is easier to understand.

[vuminhnhat]

To reduce the if else condition in left and right sorted portion. I think, for each sorted portion, we can apply binary search directly. If you find target value, then return. If not find, we move left and right index respectively.

[ShivangiSingh-wcgk]

Amazing explanation, will donate when I get the job.

[rudya.hernandez]

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

[zenyujin_]

I think using the inequality signs like this makes it a lot more intuitive:
def search(self, nums, target):
L, R = 0, len(nums) - 1

while L <= R:
m = (L + R) // 2

if nums[m] == target:
return m

# If the left half is sorted
if nums[L] <= nums[m]:
# If target is in the sorted left half
if nums[L] <= target < nums[m]:
R = m - 1
else:
L = m + 1
# If the right half is sorted
else:
# If target is in the sorted right half
if nums[m] < target <= nums[R]:
L = m + 1
else:
R = m - 1

return -1

[rextlfung]

Great explanation! The visuals really helped. Somehow when I tried this problem I got stuck with "and" conditions but now it makes complete sense why it's "or"

[priyavardhanpatel]

I have spent more than 2 hours on this problem but couldnt solve it. You made it very clean and simple, thank you so much!!!