All sorted rotated arrays have one thing in common that is there will be atleast one sorted half for sure This can be proved by taking 5 elements and all its possible rotations and then see how left,mid and right varies Post that we will come to the above mentioned conclusion Now using this technique one can easily solve any variant problem related to sorted rotated array
A sllightly faster way (but longer code) - Each time after finding nums[m], check its neighbour. If the value to the right is lower, it means it is the first element of the original array. If the value to the left is higher, it means it is the last element of the original array. If both of these conditions are not met, narrow the search by half. l, r = 0, len(nums) - 1 while l < r: mid = (l + r) // 2 # Since original array is ascending, # a lower right value means it is the first element if nums[mid+1] < nums[mid]: return nums[mid+1] # a higher left value means it is the last element elif nums[mid-1] > nums[mid]: return nums[mid] # Narrow the search by half if nums[mid] > nums[r]: l = mid + 1 else: r = mid - 1 return nums[l] # To handle single element array
First of all thank you so much for the videos! I am a big fan. Secondly, it's one of those questions that you need to memorize because I couldn't get it when I tried to do it by myself.
Hi there, in one of your videos you mentioned the order of types of ds we should follow and solve because they are prerequisite for others, why you don't do the same, for example start with 5 problem from the first one to ... 5 problem of last one(dyn programming was the last one, i remember), and in the end of solving each problem recommend 5 similar important problems for practice It would be really helpful if you do that instead of just randomly solving problem, inform us about what you think about this idea Thanks
another solution is : pushing the items into max-heap then loop through the heap values -> pop the root as long as the heap has more than one value left, once the heap has one value left, its the min value return it and done but its nLongn I guess
Master Data Structures & Algorithms For FREE at AlgoMap.io!
this was so good i tried looking at other explanations but it felt like it went against my intuition for solving the problem this was perfect
Really happy you enjoyed it!
That was a beautiful approach, so precise and simple. Excellent job sir. Thank you for sharing.
Very glad you enjoyed it!
All sorted rotated arrays have one thing in common that is there will be atleast one sorted half for sure
This can be proved by taking 5 elements and all its possible rotations and then see how left,mid and right varies
Post that we will come to the above mentioned conclusion
Now using this technique one can easily solve any variant problem related to sorted rotated array
A sllightly faster way (but longer code) - Each time after finding nums[m], check its neighbour. If the value to the right is lower, it means it is the first element of the original array. If the value to the left is higher, it means it is the last element of the original array. If both of these conditions are not met, narrow the search by half.
l, r = 0, len(nums) - 1
while l < r:
mid = (l + r) // 2
# Since original array is ascending,
# a lower right value means it is the first element
if nums[mid+1] < nums[mid]:
return nums[mid+1]
# a higher left value means it is the last element
elif nums[mid-1] > nums[mid]:
return nums[mid]
# Narrow the search by half
if nums[mid] > nums[r]:
l = mid + 1
else:
r = mid - 1
return nums[l] # To handle single element array
I think the explanation was very intuitive. Thank you!
you're the goat, thank you for this video!
simple and neat solution. Thank you.
First of all thank you so much for the videos! I am a big fan.
Secondly, it's one of those questions that you need to memorize because I couldn't get it when I tried to do it by myself.
That's so sweet! And yeah this one is definitely tricky lol
Very good explanation. Thank you
Hi there, in one of your videos you mentioned the order of types of ds we should follow and solve because they are prerequisite for others, why you don't do the same, for example start with 5 problem from the first one to ... 5 problem of last one(dyn programming was the last one, i remember), and in the end of solving each problem recommend 5 similar important problems for practice
It would be really helpful if you do that instead of just randomly solving problem, inform us about what you think about this idea
Thanks
class Solution(object):
def findMin(self, nums):
if nums:
nums.sort()
else:
return False
return nums[0]
nums = [4,5,6,7,0,1,2]
solution=Solution()
print(solution.findMin(nums))
You are defeating the purpose of the task by sorting it
It is a binary search problem.
Make a video for the find target when sorted arr is rotated problem too
luvd it mate
Super glad to hear it ☺️
Why is M = 6 when it's actually 7 in your example?
Sorry did I get something wrong here?
another solution is : pushing the items into max-heap
then loop through the heap values -> pop the root as long as the heap has more than one value left, once the heap has one value left, its the min value return it and done
but its nLongn I guess