Brute Force Intuition 💹
Now, for the brute force, we will form all possible subarrays of size ‘K’ and calculate MIN_V and SUM_V for each of them using a for loop and maintain a ‘MAX_V’ variable which will store the maximum possible value of (MIN_V * SUM_V). Now you must have got intuition. We are leaving the coding part to you as we will discuss a much more critical method, i.e., Sliding Window.
Sliding Window Approach ✅
In this approach, we will maintain a Sliding Window of size 'K' and keep track of MIN_V and SUM_V for every subarray of size 'K.' Now to know how to calculate the sum by sliding window technique, you can refer here, whereas we will calculate MIN_V using a set data structure. The required answer is the maximum value of MIN_V * SUM_V over all K-sized windows.
C++ Implementation 📌
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
// Function to maximize the product of min value of subarray and sum of subarray over all subarrays of length K.
int maximizeMinValAndSumVal(vector<int> &arr, int k)
{
// Set is used to calculate the minimum value among all K-sized subarrays.
set<int> minVSet;
// Stores the sum of the current window
int sumV = 0;
int i = 0;
// Calculating the sum of the first subwindow of size 'K'
while (i < k)
{
minVSet.insert(arr[i]);
sumV = sumV + arr[i];
i++;
}
// Minimum value in the subarray.
int minV = (*minVSet.begin());
// Initializing the result.
int maxV = sumV * minV;
i = k;
while (i < arr.size())
{
// Here, we are adding the current value and removing the (i-K)th value from the overall sum.
sumV += (arr[i] - arr[i - k]);
// Updating the set.
minVSet.erase(minVSet.find(arr[i - k]));
minVSet.insert(arr[i]);
// Updating the minimum value.
minV = (*minVSet.begin());
// Updating the value of 'MAX_V'.
maxV = max(maxV, sumV * minV);
i++;
}
// Return Answer.
return maxV;
}
// Driver Code
int main()
{
int n;
cin >> n;
vector<int> arr(n, 0);
// Taking input.
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
arr[i] = x;
}
int k;
cin >> k;
cout << maximizeMinValAndSumVal(arr, k);
return 0;
}
Input
4
1 2 3 4
2
Output
21
Time Complexity ⏳
O(N * log(K)), where ‘N’ is the length of the array and ‘K’ is the size of the window.
Reason: Here, we are using a set data structure that takes logarithmic time for insertion, search, and deletion. As we are inserting a total of K elements thus, the time taken by it would be O(K * log(K)). Also, we are looping through the array once, and within that, we are searching and deleting the element in the set, which will cost us O(N * log(K)) time. Thus the overall time complexity is
O(K * log(K)) + O(N * log(K)) ~ O(N * log(K)).
Space Complexity 💾
O(N), where ‘N’ is the array's length.
Reason: Since we are using a set.
Check out this problem - Subarray With 0 Sum
Frequently Asked Questions
What is the prerequisite to using the Sliding window technique?
The Sliding Window technique can be used in a specific scenario where the size of the computation window remains constant throughout the entire nested loop. Then and only then can the time complexity be reduced.
How to use Sliding Window Technique?
The following is an example of how to use the sliding window technique in general:
- Determine the required window size.
- Calculate the result for the first window, starting from the beginning of the data structure.
- Then, using a loop, move the window by one and compute the result window-by-window.
What is a sliding window?
As the name implies, this technique entails extracting a subset of data from an array or string and expanding or contracting that subset to meet specific criteria, resulting in a sliding effect.
Which problems involve the sliding window technique?
The sliding window technique is helpful with arrays/lists. It usually solves the more complex O(n^2) or O(n^3) problem with much lesser time complexity. The time complexity of such problems can be reduced to O(n) using the 'sliding window' technique.
Are there any other Data Structures and Algorithms content in Coding Ninjas Studio?
Coding Ninjas Studio allows you to practice coding and answer frequently asked interview questions. The more you practice at Coding Ninjas Studio, the more likely you will acquire a job at our dream company.
Conclusion🔚
We saw how we could solve the problem and maximize the product of the min value of subarray and sum of subarray over all subarrays of length K by Naive and efficient methods, namely Sliding Window. To learn more about Arrays, visit Arrays | Learn & Practice from Coding Ninjas Studio
I hope you would have gained a better understanding of these topics now!
Recommended problems -
Are you planning to ace the interviews with reputed product-based companies like Amazon, Google, Microsoft, and more?
Attempt our Online Mock Test Series on Coding Ninjas Studio now!
Till then,
Happy Coding!
38+ registered 