Find the min number in all contiguous subarrays of size L of a array of size n

Question

The minimum number in a subarray of size L. I have to find it for all the subarrays of the array. Is there any other way than scanning through all the subarrays individually?

I have one solution in mind:

a[n]//the array
minimum[n-l+1]//the array to store the minimum numbers

minpos=position_minimum_in_subarray(a,0,l-1);
minimum[0]=a[minpos];
for(i=1;i<=n-l-1;i++)
{
    if(minpos=i-1)
    {
        minpos=position_minimum_in_subarray(a,i,i+l-1);
    }
    else {
        if(a[minpos]>a[i+l-1]) minpos=i+l-1;
        minimum=a[minpos];
    }
}

Is there any better solution than this?

And what do you mean by min number? The minimal sum of `l` adjacent numbers in array `n`? — John Carter, Sep 08 '12 at 08:29

score 4 · Accepted Answer · answered Sep 08 '12 at 09:37

4

You can use a double ended queue(Q) .Find a way such that the smallest element always appears at the front of the Q and the size of Q never exceeds L. Thus you are always inserting and deleting elements at most once making the solution O(n). I feel this is enough hint to get you going.

answered Sep 08 '12 at 09:37

Wayne Rooney

1,587
3
17
23

My approach and implementation of this algorithm can be found here: http://stackoverflow.com/a/12239580/1088243 – Sajal Jain Sep 09 '12 at 12:11

Grisha Weintraub · Answer 2 · 2012-09-08T19:04:26.533

I think your solution is OK , but to work properly it should be something like :

a[n]//the array
minimum[n-l+1]//fixed

minpos=position_minimum_in_subarray(a,0,l-1);
minimum[0]=a[minpos];
for(i=1;i<=n-l-1;i++)
{
    if(minpos=i-1)        
        minpos=position_minimum_in_subarray(a,i,i+l-1);                   
    else if(a[minpos]>a[i+l-1]) //fixed
        minpos=i+l-1; //fixed

    minimum[i] = a[minpos];
}

// Complexity Analysis :

//Time - O(n^2) in worse case(array is sorted) we will run
         "position_minimum_in_subarray" on each iteration

//Space - O(1) - "minimum array" is required for store the result

If you want to improve your time complexity, you can do it with additional space. For example you can store each sub array in some self-balancing BST (e.g. red-black tree) and fetch minimum on each iteration :

for (int i= 0; i<n; i++) {
    bst.add(a[i]);

    if (bst.length == l) {
        minimum[i-l] = bst.min;
        bst.remove(a[i - l]);            
    }
  }

 //It's still not O(n) but close.

 //Complexity Analysis :

 //Time - O(n*log(l)) = O(n*log(n)) - insert/remove in self-balancing tree
                                      is proportional to the height of tree (log)

 //Space - O(l) = O(n)

The question has been edited with the fixes you suggested but is there a better solution. — wizgen, Sep 08 '12 at 10:59
What do you want to improve ? see complexity analysis in my answer. — Grisha Weintraub, Sep 08 '12 at 11:42
I'm not sure you can do it in `O(n)`. See my answer with `O(nlogn)` solution. — Grisha Weintraub, Sep 08 '12 at 19:05

score 1 · Answer 3 · answered Sep 13 '19 at 00:34

1

Scala version answer

def movingMin(windowSize: Int, array: Seq[Double]) = { 
    (1 to array.length - (windowSize - 1)).
        map{i => (array.take(i + (windowSize - 1)).takeRight(windowSize)).min}
}

answered Sep 13 '19 at 00:34

Miae Kim

1,713
19
21

Find the min number in all contiguous subarrays of size L of a array of size n

3 Answers3

Linked

Related