Maximum of Minimum of every sub array P-2.

In the part 1 we have discussed about the approach where we find the next smaller element array and previous smaller element array. Back then we have ended our discussion on why the hell we have found those arrays. Well even today I could not find myself why we have found those arrays. I have seen the video two to three times then i could understand the need of those arrays. I will talk w.r.t code below

class Solution
{
? ? //Function to find maximum of minimums of every window size.
? ? static int[] maxOfMin(int[] arr, int n)?
? ? {
? ? ? ? // Your code here
? ? ? ? if(n==1) return arr;
? ? ? ? int [] r8 = new int[n];
? ? ? ? int [] left = new int[n];
? ? ? ? Stack<Integer> st = new Stack<>();
? ? ? ? for(int i = 0; i < n; i++){
? ? ? ? ? ? r8[i] = n;
? ? ? ? ? ? left[i] = -1;
? ? ? ? }
? ? ? ? for(int i = 0; i < n; i++){
? ? ? ? ? ? while(!st.isEmpty() && arr[st.peek()]>arr[i]){
? ? ? ? ? ? ? ? r8[st.pop()] = i;
? ? ? ? ? ? }
? ? ? ? ? ? st.push(i);
? ? ? ? }
? ? ? ? st.clear();
? ? ? ? for(int i = n-1; i >=0; i--){
? ? ? ? ? ? while(!st.isEmpty() && arr[st.peek()]>arr[i]){
? ? ? ? ? ? ? ? left[st.pop()] = i;
? ? ? ? ? ? }
? ? ? ? ? ? st.push(i);
? ? ? ? }
? ? ? ? int [] ans = new int[n];
? ? ? ? for(int i = 0; i < n; i++){
? ? ? ? ? ? ans[i] = 0;
? ? ? ? }
? ? ? ? int k = 0;
? ? ? ? for(int i = 0; i < n; i++){
? ? ? ? ? ? int interval = r8[i] - left[i] - 1;
? ? ? ? ? ? ans[interval-1] = Math.max(ans[interval-1],arr[i]);
? ? ? ? }
? ? ? ? for(int i = n-2; i>=0; i--){
? ? ? ? ? ? ans[i] = Math.max(ans[i],ans[i+1]);
? ? ? ? }
? ? ? ? return ans;
? ? }
}?        

Once we have found the the left and right arrays, we need to find the interval of length where this element is smaller. This length will be the index position where this has to fitted! No one gets this idea but once you take an example and try out the above code i am sure you will be surprised how it actually turns out in your favour. Now once this are placed we will be left with some empty slots and our final job is to fill it. How do we do that? we do that by taking maximum of that position and the next adjacent position. To be frank there are too many understandable concepts here.. ??I am sure if we look into this problem some other time then it would make more sense. But we need to learn as much as we understand and keep practising..That's all we can do!

As a part of today's thought I also want to talk the problem Dam of Candies. Here when you go through the problem description, we need to move the pointers ahead only if the other pointer points at a better solution. so we move ahead thinking that we might come across a better value. This might sound very obvious but always a great point to keep in mind. I ll also provide the code snippet so you could get a better view.

class Solution
{?
	static int maxCandy(int height[], int n)?
	{?
	? ? // Your code goes here
	? ? if(n==1) return 0;
	? ? int p1 = 0;
	? ? int p2 = n-1;
	? ? int area = 0;
	? ? while(p1<p2){
	? ? ? ? int len = Math.abs(p2-p1-1);
	? ? ? ? int ht = Math.min(height[p1],height[p2]);
	? ? ? ? area = Math.max(area,len*ht);
	? ? ? ? if(height[p1]>height[p2]){
	? ? ? ? ? ? p2--;
	? ? ? ? }
	? ? ? ? else if(height[p1]<height[p2]){
	? ? ? ? ? ? p1++;
	? ? ? ? }
	? ? ? ? else{
	? ? ? ? ? ? p1++;
	? ? ? ? ? ? p2--;
	? ? ? ? }
	? ? ? ??
	? ? }
	? ? return area;
	}
}?