 # Minimum Value

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 ??

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 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! :)

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…

yeah, the obvious solution !! thanks for your response though i’m glad 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. 1 Like

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