C++ program to find Minimum of each subarrays in Linear Time.














































C++ program to find Minimum of each subarrays in Linear Time.



Finding Minimum in linear time

Problem description : Given an array of n elements and a variable m, where m <= n, We need to find the smallest elements in each of the subarray of length .

Naive Approach - 

Naive approach says that iterate over each of the subarray and find the least element of it.

Algorithm for Naive-Approach :

  1. for i = 0 to i < n + m + 1:
    1. minimum = infinity
    2. for j = 0 to j = m:
      1. if minimum > arr[j]:
        1. minimum = arr[i]
    3. print minimum
The above algorithm prints minimum of each subarray of length m in the given array arr.
But, the solution is not optimized and complexity of the algorithm is , Can we optimize this?

C++ implementation of Naive Approach:

#include<bits/stdc++.h>
using namespace std;
void FindingMinimumOfSubarrays(){
    // Input data
    int n, m; 
    cin >> n >> m;
    int arr[n];
    for(int i= 0; i< n;i++)
        cin >> arr[i];

    // Main algorithm
    for(int i = 0; i < n-m+1; i++){
        int minimum = INT_MAX;
        for(int j = i; j < m; j++){
            minimum = min(arr[j], minimum);
        }
        cout << minimum << " ";
    }
    cout << endl;
}
// Driver Function
int main(){
    FindingMinimumOfSubarrays();
    return 0;
}

Better Approach with O(n) complexity :

We will solve this problem using sliding window Algorithm, We will take the help of queue data structure and each time calculate the minimum in the given queue. But, we will not be using queue but, try to use two stack implementation of queue.
We will be using modified version of stack. which store not only the element but also the minimum element before it,

stack<pair<int, int>> s1, s2;

The first field in this stack we will store the element itself and in the second field, we will store the minimum element occurs before it. which help us extract the minimum element in constant time on an average (O(1)).

But, question is why two stack?

The first stack is for insertion purpose, and second for deletion purpose, which to simulate the functionality of a queue. 

If the second stack is empty during deletion, we pop each element from the s1 and push in s2 maintaining the property of minimum element in the second field of the stacks (which is necessary). As you can see we will be performing this type of pushing and poping very less number of types, the overall time complexity remains O(n).

Below is the implementation of the approach.



#include<bits/stdc++.h>
using namespace std;

void FindingMinimumOfSubarrays() {

    // Input data
	int n, m; 
	cin >> n >> m;
	int arr[n];
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	stack<pair<int, int>> s1, s2;

    // Storing first m elements in s1
	int i = 0;
	while (i < m) {
		int mini = s1.empty() ? arr[i] : min(arr[i], s1.top().second);
		s1.push({arr[i], mini});
		i++;
	}

    // Printing the minimum of first five elements.
    cout << s1.top().second << " ";

    // Loop to iterate other subarrays of size m
	while (i < n) {
		int minimum = 0;

        // If s2 is empty, we trasfer elements from s1 to s2
        // obviously this will reverse the order of elements in s1,
        // But, the condition of minimum elements in second field of
        // stacks must hold.
		if (s2.empty()) {
			while (!s1.empty()) {
				int element = s1.top().first;
				int mini = s2.empty() ? element : min(s2.top().second, element);
				s2.push({element, mini});
				s1.pop();
			}
		}

        // Removing element from s2, to store next element in s1.
		s2.pop();
		int temp = s1.empty() ? arr[i] : min(arr[i], s1.top().second);
        s1.push({arr[i], temp});

		// Condition to find minimum in the subarray of length m
		if (s1.empty() || s2.empty())
			minimum = s1.empty() ? s2.top().second : s1.top().second;
		else
			minimum = min(s1.top().second, s2.top().second);

        // Print the minimum of this subarray.
		cout << minimum << " ";
		i++;
	}
	cout << endl;
}
int main() {
	FindingMinimumOfSubarrays();

	return 0;
}

Sample Input :

5 3

3 2 4 7 4

Sample Output:

2 2 4

Practice Problem :


More Articles of Nikhil Kumar:

Name Views Likes
C++ program to find Minimum of each subarrays in Linear Time. 71 0
C++ Algorithm to find Path matrix of a graph. 99 0
Implement BODMAS using C++. 213 0
Shell Sort. 240 0
3n+1 Problem Solution using C++. 104 0

Comments