I solved it right now, but it's pretty tough for a medium. I don't have time to make a video so I'll link my submission and try to explain the algorithm. 1. Initialize your result array with the minimum integer value. 2. Use an increasing stack to find the indexes of the previous lesser and next lesser elements for each element in the input array. Calculate the distance from the previous lesser to the next lesser, and that's what length subarray the value at the current index you're processing is a minimum value of. 3. Update the max value in your result array for that length. (Initially I tried updating all the lengths that are greater or equal to the length, but the algorithm becomes n^2 if you do that.) You'll repeat step 2 & 3 for every element in the input array. 4. This last part was tricky for me but the intuition is that it's similar to a prefix sum. Say 100 is the max value for subarray length of 2 and you have that in your result array. But also in your result array for length 1 you only have 50. Well that doesn't make sense because if 100 is the max value for subarrays of length 2, it must also be the max value for subarrays of length 1. So to finish the "prefix sum" on the result array, I loop from the end to the beginning doing result[i] = Math.max( result[i], result[i + 1] ); leetcode.com/submissions/detail/724992785/ If you have trouble at any step I would print out your result array in your code and compare it to my solution in another tab or something.
tremendously helpful, thank you!
Thanks man!
you must be using your sharingan to be this good!!! Thanks man!!
Just trying to awaken my susanoo xD
Hey @Kacy Codes , how was your Amazon interview?
Hey Kacy,
Plesae Please Please make LC 1950. Maximum-of-minimum-values-in-all-subarrays
I solved it right now, but it's pretty tough for a medium. I don't have time to make a video so I'll link my submission and try to explain the algorithm.
1. Initialize your result array with the minimum integer value.
2. Use an increasing stack to find the indexes of the previous lesser and next lesser elements for each element in the input array. Calculate the distance from the previous lesser to the next lesser, and that's what length subarray the value at the current index you're processing is a minimum value of.
3. Update the max value in your result array for that length. (Initially I tried updating all the lengths that are greater or equal to the length, but the algorithm becomes n^2 if you do that.)
You'll repeat step 2 & 3 for every element in the input array.
4. This last part was tricky for me but the intuition is that it's similar to a prefix sum. Say 100 is the max value for subarray length of 2 and you have that in your result array. But also in your result array for length 1 you only have 50. Well that doesn't make sense because if 100 is the max value for subarrays of length 2, it must also be the max value for subarrays of length 1. So to finish the "prefix sum" on the result array, I loop from the end to the beginning doing result[i] = Math.max( result[i], result[i + 1] );
leetcode.com/submissions/detail/724992785/
If you have trouble at any step I would print out your result array in your code and compare it to my solution in another tab or something.
@@KacyCodes Great. I have no words to thank you😊. Will look into it.