I remember doing this question earlier but the way you taught I am confident I can now easily solve problems like these in interviews with a clear and intuitive explanation. Understood, thanks!
I just saw the question explanation and did the brute force and binary search approach all by myself just because of your previous videos explanation. Thank you so much for this wonderful and guided course.
@@nostalgiccringeallhailchel3881 I did aggressive cows at last. Not good progress at all because of college exams🥲 Just revising old linked list questions I did in past.
for those who are solving in leetcode the TotalH should be long long and also the CalculatetotalHours should also be long long type otherwise it will throw an error ..... hope it is helpful
@@tusharkhatri2921 you can make the condition in the calculation of hour .When the time taken exceeds h, you immediately return that val and prevent the overflow
Thank you, Striver. Loved the intuition on "binary search on answers" and on how to pick low or high as final answer. One quick suggestion: The python code provided in the solution is INCORRECT because ceil computation needs to be float.
STRIVERS TIP always find out the range ie low and high for applying the binary search bcz it could even work for larger ranges but will be efficient for the lowest high or the highest low. TIP 2 the pointers high and low always end up at opposite polarity of the condition ie for ex here POINTER low from being the speed in which eating in time isnt possible end up to possible minimum so without using the ANS directly use the POINTERS
hey striver, I feel that there is some problem with the leetcode question. for the testcase [805306368, 805306368, 805306368] and h = 1000000000, the expected answer is k=3 when we use an ans variable to store the desired value of mid, the code gives output = 1 which is incorrect, however, when we simply return the low, the testcase passes. I am not able to understand what is happening here. If this is a case of an overflow, I have already substitued long long. Pls help.
For all those who are getting confused in time complexity Let the max element in the array be M 1. TC wrt Brute force approach : N *M (haa pata hai, i am not using big O sign.. but smjh jaao tum log) Reason (Skip if already understood) : a) inner summation loop calc : N times b) Outer loop will go till max elmt in arr that is M times 2. TC wrt optimal : N*log M Reason : Since instead of doing linear search in outer loop we used BS, so M was replaced by log M Note : N^2 >> N logN >> N >> logN CLEARING YOUR CONFUSION STARIGHTWAY : Would not be it O(N) instead of N logM ...Read note above... N logM is bigger than log N so will not consider it {Jo log aalas kar rahe hai itna bada para padhne me, kripya DSA kr rhe hai to yaha bhi mehnat kr lijiye}
I solved this problem but I cant get over 1 doubt? Why are we setting low to 1? Won't it be better if we set low as the minimum number of bananas among all the piles?
No . We will set low 1 only . We need k to be minimum. Consider any case -- Take h=sum of all the elements of the array piles Then in such cases the minimum value of k will be 1.
Should we not consider the + O(n) time to find the max element in the time complexity? Though i does not add to the over all complexity since we take the high value, still asking
two doubts for optimal approach :( 1. when we are finding total time then it will iterate for each element thus making complexity as Nlog(max element) which i guess is not better than log(Max element) 2. you did it for sorted array, but if it is unsorted then how will we be sure to reject one half of the array
Could you also please explain.Find K close elements with binary search.I've seen in some of the binary search approaches.Few of the solutions are with right=mid or left=mid.
The typecasted leet-code code: #include #include #include class Solution { private: int maxEl(vector& piles) { int maxi = INT_MIN; for (int i = 0; i < piles.size(); i++) { maxi = max(maxi, piles[i]); } return maxi; } long long totEl(vector& piles, int mid) { long long totH = 0; int n = piles.size(); for (int i = 0; i < n; i++) { totH += (piles[i] + mid - 1) / mid; // Updated calculation } return totH; } public: int minEatingSpeed(vector& piles, int h) { int low = 1; long long high = maxEl(piles); int ans = INT_MAX; while (low
One doubt: what if h = 5 and piles = [30,11,23,4,20]here if we take k greater than 30 then also we'll get the answer. Then how can we apply that brute force where we are taking range of k to be [1, greatest_element] in that array?
public int findHours(int[] arr, int bananaCount) { int totalHrs = 0; for (int i = 0; i < arr.length; i++) { totalHrs += Math.ceil((double) arr[i] / bananaCount); } return totalHrs; } Cast to double, because ceil here needs floating-point number.
i got a q same like this in uber where hours were same but here it is a car and we need to find min kwperh so that the cars can get charged . but right now i am in my third year and gave uber in the beginning of the year and i didnt have any idea abt this. thank go i am on a strict plan of action now hope i will be able to solve q next time in OA
Hey striver, i am getting 1 test case wrong in this question, don't know why i still tried with your own code , but it is not working, nearly 3 problems have been in this way, any one please respond....
can we do this by finding sum of elements in array and getting the ceil value by dividing it with number of hours which takes o(N) time complexity which is better than binary search.
9:54 at this while calculating time complexity of linear approach func will run for n times .but inside it ceil function will be used jiski time complexity log n hoti h so vo consider nahi krenge?
give this man the best teacher award in the world
In DSA sure is this best For development check chai aur code once
Great tip! Whenever there is a possible range of answers then we can apply binary search.. Thanks a lot Striver!
I remember doing this question earlier but the way you taught I am confident I can now easily solve problems like these in interviews with a clear and intuitive explanation. Understood, thanks!
same
never thought we could even solve this by binary search mind-blowing
Thanks Striver, always struggled to understand the reason behind the answer being always the low value, now it's clear as crystal, all thanks to you❤❤
I just saw the question explanation and did the brute force and binary search approach all by myself just because of your previous videos explanation. Thank you so much for this wonderful and guided course.
Bro please post the solution of code
@@Rider66778 ** Brute Force :
class Solution {
public:
int minEatingSpeed(vector& piles, int h) {
int maxHours = -1 , k = 0 ;
for(int i = 0 ; i < piles.size() ; i++)
if(piles[i] > maxHours)
maxHours = piles[i] ;
for(int i = 1 ; i
how far have you progressed in 3 weeks bro pls update
@@nostalgiccringeallhailchel3881 I did aggressive cows at last. Not good progress at all because of college exams🥲
Just revising old linked list questions I did in past.
@@thenikhildaiya. Which topic is aggressive cows in?
for those who are solving in leetcode the TotalH should be long long and also the CalculatetotalHours should also be long long type otherwise it will throw an error .....
hope it is helpful
it was throwing run time error earlier. i thought i must be missing some edge case . after this change it got submitted. thanks to you buddy
Why to calculate total hours just check if it any instance the req time crosses h... Return false
When I was submitting my code, I encountered the same problem, Thanks buddy.
Bro on LeetCode not working after 121 test cases.
@@tusharkhatri2921 you can make the condition in the calculation of hour .When the time taken exceeds h, you immediately return that val and prevent the overflow
I have earlier solved the question but intuition of yours is truly amazing... Great Content 🔥🔥
Thank you, Striver. Loved the intuition on "binary search on answers" and on how to pick low or high as final answer.
One quick suggestion:
The python code provided in the solution is INCORRECT because ceil computation needs to be float.
this was asked in an interview I came up with this solution without solving this before.. :)
thanks to your intuition I could do this question on my own using the same approach that you explained in this video without any help! kudos
The wait is finally over.... Thanks a ton striver❤
Hi Raj,
Both the BF and Optimal solutions will have an additional TC of O(n) to find the maximum element from the array.
yes
I see Koko is on a high carb diet😀😅
😂
🤣🤣
Gay
lmao but tbh koko is a monkey i think thats why he is eating bananas!
@@dumpster-jackson wtf
Great video! Just wanted to add one thing, in the question's Constraints it's given that n
just include the overflow condition in finding the hrs in the loop only if totalH >H break;
Thanks!
Thankyou you so much finally able to understand the approach and logics for solving DSA!!
Done on 12 Jan 2025 at 21:27
Place : Study Room 2 , Hostel 5 , IIT Bombay
which year?
STRIVERS TIP always find out the range ie low and high for applying the binary search bcz it could even work for larger ranges but will be efficient for the lowest high or the highest low.
TIP 2 the pointers high and low always end up at opposite polarity of the condition ie for ex here POINTER low from being the speed in which eating in time isnt possible end up to possible minimum
so without using the ANS directly use the POINTERS
use long long to calculateTotalHours instead of int to avoid overflow
I have no doubts after watching ur videos.
finally found when to return the low and when to return the value high
Understood! Wonderful explanation as always, thank you very very much for your effort!!
i have solved this question with the same approach and solution
If anyone was getting runtime error of integer overflow do change the datatype of totalhours to double or long long
logic is same as finding first occurance THANK YOU
Thanks a lot Striver!
hey striver, I feel that there is some problem with the leetcode question. for the testcase [805306368, 805306368, 805306368] and h = 1000000000, the expected answer is k=3
when we use an ans variable to store the desired value of mid, the code gives output = 1 which is incorrect, however, when we simply return the low, the testcase passes.
I am not able to understand what is happening here. If this is a case of an overflow, I have already substitued long long. Pls help.
bool check(vector& piles,int h,int k){
long long ans=0;
for(int i=0;ih)return false;
}
//cout
@@thegame587 Thanks a lot buddy for replying, it's working now. I had figured the overflow problem :)
@@aniketgupta8064 you can also make the func dataype, totalH datatype to long, this can also works
@@jayant-baid thanks 👍
@@jayant-baid thank you bro i stuck in this problem for more than hour and you save me from it 😊😊
Understood
Please do upload videos consistently 😊
For all those who are getting confused in time complexity
Let the max element in the array be M
1. TC wrt Brute force approach : N *M (haa pata hai, i am not using big O sign.. but smjh jaao tum log)
Reason (Skip if already understood) : a) inner summation loop calc : N times
b) Outer loop will go till max elmt in arr that is M times
2. TC wrt optimal : N*log M
Reason : Since instead of doing linear search in outer loop we used BS, so M was replaced by log M
Note : N^2 >> N logN >> N >> logN
CLEARING YOUR CONFUSION STARIGHTWAY : Would not be it O(N) instead of N logM ...Read note above...
N logM is bigger than log N so will not consider it
{Jo log aalas kar rahe hai itna bada para padhne me, kripya DSA kr rhe hai to yaha bhi mehnat kr lijiye}
Rather than using ceil we can use "sum = sum + (v[i] - 1)/ mid + 1;"
It's more optimal
what's the logic behind the (v[i]-1) ??
Can you explain the logic?
Mtlb kuch bhi 😂.
Great explanation Striver
understood
Thank you striver for such an amazing explanation..
I solved this problem but I cant get over 1 doubt? Why are we setting low to 1? Won't it be better if we set low as the minimum number of bananas among all the piles?
No .
We will set low 1 only .
We need k to be minimum.
Consider any case --
Take h=sum of all the elements of the array piles
Then in such cases the minimum value of k will be 1.
Thank you striver....Understood everything🙂...keep up the good work
fr?
while finding maximum element in an unsorted array it takes O(n) time so ultimately the time complexity of this question is O(n).
O(n*log(max) >>> O(n) :)
Thanks so much!! I was able to solve it without watching the video !!
Thank you Striver
Should we not consider the + O(n) time to find the max element in the time complexity? Though i does not add to the over all complexity since we take the high value, still asking
You are just incredible ❤️🎉🎉
Instead of taking low = 1, we can consider
let low = Math.ceil(sum(piles) / h), high = Math.max(...piles);
We can do this .
But idk why type casting of piles[i] using float gives error .
Can u tell me
@ What error?
Understood, Thanks striver for this amazing video.
two doubts for optimal approach :(
1. when we are finding total time then it will iterate for each element thus making complexity as Nlog(max element) which i guess is not better than log(Max element)
2. you did it for sorted array, but if it is unsorted then how will we be sure to reject one half of the array
Which approach is having t.c O(log max).
Secondly which sorted array you are taking about. Piles ?
That will work whether the piles is sorted or not
Really amazing explanation 👏
Understood Man You damn it!!!
Got asked this question today!
🔴Leetcode Solution:-
class Solution {
private:
int maxi(vector arr){
int ans = INT_MIN;
for(int i=0; i
Could you also please explain.Find K close elements with binary search.I've seen in some of the binary search approaches.Few of the solutions are with right=mid or left=mid.
The typecasted leet-code code:
#include
#include
#include
class Solution {
private:
int maxEl(vector& piles) {
int maxi = INT_MIN;
for (int i = 0; i < piles.size(); i++) {
maxi = max(maxi, piles[i]);
}
return maxi;
}
long long totEl(vector& piles, int mid) {
long long totH = 0;
int n = piles.size();
for (int i = 0; i < n; i++) {
totH += (piles[i] + mid - 1) / mid; // Updated calculation
}
return totH;
}
public:
int minEatingSpeed(vector& piles, int h) {
int low = 1;
long long high = maxEl(piles);
int ans = INT_MAX;
while (low
Understood Very Well!
Someone please give a advice like how can u build a logic, how to revice sometimes I just go all blank even in some easy question what should I do ??.
Dada tumi best❤❤❤
to clear all the test cases . class
Solution {
public:
int findmaxelement(vector& piles){
int maximum = INT_MIN;
int n = piles.size();
for (int i=0; i
Can't we use float for type cast
When using float 123 testcase is not passing .
But after I did double all testcase passed . What's the logic now
One doubt:
what if h = 5 and piles = [30,11,23,4,20]here if we take k greater than 30 then also we'll get the answer. Then how can we apply that brute force where we are taking range of k to be [1, greatest_element] in that array?
@striver thanks for explanation
public int findHours(int[] arr, int bananaCount) {
int totalHrs = 0;
for (int i = 0; i < arr.length; i++) {
totalHrs += Math.ceil((double) arr[i] / bananaCount);
}
return totalHrs;
}
Cast to double, because ceil here needs floating-point number.
Koko for real is gonna shit the whole next day ! AWESOME VID STRIVER
it is actually similar to finding the smallest divisor than threshold question literally
16:50 Low opposite polarity
To reduce runtime one can use instead of ceil
ans += (piles[i]+k-1)/k;
very helpful explaination
thank youu striver
Really Amazing👏👏👏
Should we not add the O(n) to time complexity to find the max element in the array
Best explanation 🔥
A typical De-Shaw intern OA question
was waiting for this
Best explaination😍
Understood✅🔥🔥
nice explaination
so if an array is not sorted, can this logic still work, please tell
Yes it will work fine with the same code because our initial search space is [1, max(piles)] not the piles array
i was doing this wrong for three hours and what i was doing wrong was only not applying double🙂
i got a q same like this in uber where hours were same but here it is a car and we need to find min kwperh so that the cars can get charged
. but right now i am in my third year and gave uber in the beginning of the year and i didnt have any idea abt this. thank go i am on a strict plan of action now hope i will be able to solve q next time in OA
Understood, thank you.
Sir plz make videos on linked list and string part from A to Z dsa sheet
Understood!
bro the array is already sorted so we know that the maximum element will be at the end... why are you writing function to calculate maximum?
the array may or may not be sorted so you need a helper function to find the max
Hey striver, i am getting 1 test case wrong in this question, don't know why
i still tried with your own code , but it is not working, nearly 3 problems have been in this way,
any one please respond....
why i feel like i am watching these videos again
Understood😁
Nice explanation ❤
can we do this by finding sum of elements in array and getting the ceil value by dividing it with number of hours which takes o(N) time complexity which is better than binary search.
understood 😇
Solved this without watching the video myself
why do you return low, you didn't explained that part
Good explanation understood
24/01/25 Uber She++ question 🤩
Why does it not work if I take the minimum eating speed as the minimum of the array ?
Following this series. Really helpfull 💪💪
9:54 at this while calculating time complexity of linear approach func will run for n times .but inside it ceil function will be used jiski time complexity log n hoti h so vo consider nahi krenge?
But bro time complexity of ceil function is O(1)
( Sqrt function has time complexity generally O(1) .
)
Max=n-1 ?cause it is sorted?
Was Waiting for the same
Thank You
By what time, will the whole A2Z course will be completed?
Understood ❤
Finding max will add O(n) to the time complexity.won't it?
The TC will be O(n) or what?
understood!!!
Kb tk playlist complete hogi?
how can we come to know that the given question is bs on answers.