## 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!**