Algorithm for maximum value in range of sub array windows

Question

I have an array of numbers and a variable k. Find all sub-arrays of size k, get the minimum value in that sub-array of size k. Then find the maximum of all the minimum values.

Example:

Array : [2, 5, 4, 6, 8], k = 3.

Possible sub-array of size k are:

[2,5,4] => minimum = 2
[5,4,6] => minimum = 4
[4,6,8] => minimum = 4

Maximum of all minimums [2,2,4] is 4

So output is 4.

This is a working program for this task which i am trying to understand.

public static int process(int k, List<Integer> arr) {
    int n = arr.size();
    int[] array1 = new int[n];
    array1[0] = arr.get(0);
    int[] array2 = new int[n];
    array2[n - 1] = arr.get(n - 1);

    for (int i = 1; i < n; i++) {
        if (i % k == 0)
            array1[i] = arr.get(i);
        else
            array1[i] = Math.min(array1[i - 1], arr.get(i));

        int j = n - i - 1;
        if ((j + 1) % k == 0)
            array2[j] = arr.get(j);
        else
            array2[j] = Math.min(array2[j + 1], arr.get(j));
    }
    List<Integer> minimaList = new ArrayList<>();

    for (int i = 0; i < n - k + 1; i++) {
        minimaList.add(Math.min(array1[i + k - 1], array2[i]));
    }

    return Collections.max(minimaList);
}

I understand that array1 is used to store the minimum value in the range window of k. Then what is the use of array2 and then how the logic minimaList.add(Math.min(array1[i + k - 1], array2[i])); helps to find the minimum in k window sub-array.

Also if array1 holds all minimum values in k window then can't we just return the maximum value present in array1 as result?

Shailesh Suryawanshi · Accepted Answer · 2021-07-20 16:27:56Z

1

Problem Array:= [2, 5, 4, 6, 8], k = 3.
divide the problem array in Windows of lenght k=3 => 
windows
    index[0-2] => [2,5,4] 
    index[3-4] => [6,8] // This is from index 3 to end of the problem list

SubArrays
    index[0-2] =>[2,5,4]
    index[1-3] =>[5,4,6]
    index[2-4] =>[4,6,8]

minimum from left in windows
    > for window [2,5,4] ==>[2,2,2] 
    > for window [6,8] ==> [6,6]
    > arr1 = minimum from left for window [2,5,4] + minimum from left for window [6,8]
    > arr1 = [2,2,2] + [6,6] = [2,2,2,6,6]
    > every element at a particular index will be the smaller from all the elements to the left till the start of window index. 
    > rightMost element will the smallest element in the window. As the solution bubbled from leftMost element.  
    > [2,2,2] => 2 is smallest, [6,6] => 6 is smallest.


minimum from right in windows => [2,4,4] [6,8] => Arr2 = [2,4,4,6,8]
    > for window [2,5,4] ==>[2,4,4] 
    > for window [6,8] ==> [6,8]
    > arr2 = minimum from right for window [2,5,4] + minimum from right for window [6,8]
    > arr1 = [2,4,4,6,8]
    => every element at a particular index will be the smaller from all the elements to the right till the end of index.
    => leftMost element will the smallest element in the window. As the solution bubbled from rightMost element.  
    => [2,4,4] => 2 is smallest, [6,8] => 6 is smallest.

consider i = index on list 

minimum in the window=  min(arr2[i],arr1[i+sizeOfWindow-1])

iterateTill = (size of problemList - sizeOfWindow - 1) = 5-3-1 = 2

Loop form 0 -> (iterateTill) 
    0 => min(arr2[0],arr1[0+3-1]) => min(arr2[0],arr1[2]) => min(2,2) => 2
    1 => min(arr2[1],arr1[1+3-1]) => min(arr2[1],arr1[3]) => min(4,6) => 4
    2 => min(arr2[2],arr1[2+3-1]) => min(arr2[2],arr1[4]) => min(4,8) => 4

** How This Works **

There are two conditions here. 
            1. The subarray is completely in the divided window  
                > eg subarray[0-2] falls completely in the window[0-2]
                > arr1[0-2] -> arr1[2] will be the smallest. 
                > arr2[0-2] -> arr2[0] will be the smallest. 
                > minSubArray= min(arr2[0],arr1[2]) = min(2,2) = 2
                => Since the index 0-2 falls in the same window. Therefore rightmost in arr1 == leftMost in arr2. 

            2. The subarray is spanned in two divided windows.
                eg subarray[1-3] and subarray[2-5]

                Subarray[1-3]
                > min(subarray[1-3]) => min(subarray(1-2),subarray(3,3))
                > arr2[1] is smaller than all the elements to the right till the end of window. 
                > arr2[1] = min[problem[1],problem[2]]
                similarly, 
                > arr1[3] = min[problem[3],problem[3]] // start of the window[3-4]
                > min(subarray[1-3]) = min(arr2[1],arr1[3]) = min(4,6) => 4

               Similarly for subarray [2-5]
                > min(subarray[2-4]) => min(subarray(2,2),subarray(3,4))
                > arr2[2] = min[problem[2],problem[2]]
                similarly, 
                > arr1[4] = min[problem[3],problem[4]] // start of the window[3-4]
                > min(subarray[2-4]) = min(arr2[2],arr1[4]) = min(4,6) => 4

            3. The final collection.max will return the maximum value from the minimal list, considering the minimum of all the subarrays is saved in minimaListlist.

I have tried to refactor code with proper names, Please have a look this might help you understand more. The naming in the code is very poor.

     public static int process(int sizeOfSubArray, List<Integer> problemList) {
            int sizeOfProblemList = problemList.size();
            int[] minimumFromLeftInWindow = new int[sizeOfProblemList];

            // LeftMost element index 0, will be the smallest element from the start to the index of leftmost element. 
            minimumFromLeftInWindow[0] = problemList.get(0);
    
            int[] minimumFromRightInWindow = new int[sizeOfProblemList];
            
            // RightMost element will be smallest element from right to the end of the list.  
            minimumFromRightInWindow[sizeOfProblemList - 1] = problemList.get(sizeOfProblemList - 1);
    
            for (int i = 1; i < sizeOfProblemList; i++) {
                if (i % sizeOfSubArray == 0)
                    minimumFromLeftInWindow[i] = problemList.get(i);
                else
                    minimumFromLeftInWindow[i] = Math.min(minimumFromLeftInWindow[i - 1], problemList.get(i));
               
                // Moving from end of the list to start. That is from right end to left end. 
                int j = sizeOfProblemList - i - 1;
                if ((j + 1) % sizeOfSubArray == 0)
                    // if the index is of rightMostElement element in window 
                    minimumFromRightInWindow[j] = problemList.get(j);
                else
                    // take the minimum of element to the right of this index and element at this index
                    // considering the element to the right have bubbled up the minimum element from right. 
                    minimumFromRightInWindow[j] = Math.min(minimumFromRightInWindow[j + 1], problemList.get(j));
            }
            List<Integer> minimaList = new ArrayList<>();
          
            for (int i = 0; i < sizeOfProblemList - sizeOfSubArray + 1; i++) {
                minimaList.add(Math.min(minimumFromLeftInWindow[i + sizeOfSubArray - 1], minimumFromRightInWindow[i]));
            }
    
            return Collections.max(minimaList);
        }

edited Jul 20, 2021 at 16:27

answered Jul 20, 2021 at 11:13

Shailesh Suryawanshi

1,2808 silver badges13 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Shailesh Suryawanshi Over a year ago

Please help me with formatting the answer.

Learner Over a year ago

Can you please explain how the right is obtained? minimum from right in windows => [2,4,4] [6,8] => Arr2 = [2,4,4,6,8]

Shailesh Suryawanshi Over a year ago

Consider window [2,5,4] => you will move from end of the window to the first. Consider their indexes such that [0,1,2]. Now start from index 2 to 1. And store minimum in arr2. This is exactly what we are doing for arr1. We are moving from left end to the right end and pushing the minimum till now in arr1.

Shailesh Suryawanshi Over a year ago

I have added comments in the code. I hope this helps.

Learner Over a year ago

I am trying to understand the explanation arr1 bubled up min value from right also arr1 bubled up min value from left so you mean same array is used for left and right both ways? Why the second array arr2 appears only in case 2 of your explanation? arr2 bubled up min value from left till this index

|

Collectives™ on Stack Overflow

Algorithm for maximum value in range of sub array windows

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related