Minimum Value

general
,
1

Hello fellow codesters,
I need a lil help from you guys
I’d like to find the Minimum Value for every set of a constant number of values in an array !!
like,
i need to find the minimum for every 5 values in an array of size 10,

input array :
1 2 3 4 5 6 7 8 9 10
o/p array :
1 2 3 4 5 6

Explanation :
Min of (1,2,3,4,5) = 1
Min of (2,3,4,5,6) = 2
Min of (3,4,5,6,7) = 3
Min of (4,5,6,7,8) = 4
Min of (5,6,7,8,9) = 5
Min of (6,7,8,9,10) = 6
Is it possible to achieve the result in O(n) time ??

2

hi @mecodesta ,

Well, i don’t think this is an o(n) solution and is the most basic one, but this could take you to the correct direction :slight_smile:

A basic c++ approach: 

#include<iostream>
using namespace std;
int main()
{
   int n;
   cin>>n;
   int a[n];
   for(int i=0;i<n;i++)
       cin>>a[i]; //INPUT

   int mini=100000;  //HOLDS THE MIN FOR SUBARRAYS.
   int count=0;  //TAKES CARE OF THE 5 IN YOUR PROBLEM AS YOU NEED TO FIND MIN OF 5 INDICES
   for(int i=0;i<=n;i++)
   {
       if(count==5)//THIS MEANS YOU HAVE EXAMINED 5 NUMBERS THEN PRINT MIN OF THOSE 5
       {
          cout<<mini<<" "<<endl;
          count=0;// FOR NEXT 5 COUNT IS INTIALIZED TO 0
          i=i-4;// TAKE THE INDEX BACK TO ONE NEXT TO PREVIOUS(SEE YOUR OWN EXAMPLE)
          mini=1000000;
       }
      mini=min(a[i],mini);
      count++; //INCREMENT EACH TIME
    }
return 0;
}


Sample case:


    Input:
    10
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    Output:
    1
    2
    3
    4
    5
    6

```

So this, i would say is the most basic code one can give you. Now depending upon constarints and problem statement various optimisations could be used, like,
  • segment trees(query on each range of 5 elements using a loop)
  • similarly, RMQ
  • Or, some kind of heap
Hope this helps! :)
3

I could go for Sparse Table or Segment Trees, assuming my N is 500000 , and total no of queries varying from 1 to N/2 … which one would be efficient if at all…

4

yeah, the obvious solution !! thanks for your response though :slight_smile: i’m glad :slight_smile:

5

I think segment tree would be a much much better way to implement this as sparse table may lead to a huge amount of space wastage! Don’t know if there’s a better approach though. :slight_smile:

1 Like
6

i have DP approach of time complexity O(n) and Space Complexity O(n.
i answered this question on stackoverflow…
see this… code plus explanation is there

http://stackoverflow.com/questions/8031939/finding-maximum-for-every-window-of-size-k-in-an-array/17249084#17249084