Stacks & QueuesProblem 35 of 38
Sum of minimum and maximum elements of all subarrays of size k
Problem Statement
Given an array of integers and a positive integer k, find the sum of minimum and maximum elements of all contiguous subarrays (windows) of size k.
Example:
Input: arr = [2, 5, -1, 7, -3, -1, -2], k = 4
Windows:
[2, 5, -1, 7] → min = -1, max = 7, sum = 6
[5, -1, 7, -3] → min = -3, max = 7, sum = 4
[-1, 7, -3, -1] → min = -3, max = 7, sum = 4
[7, -3, -1, -2] → min = -3, max = 7, sum = 4
Output: 6 + 4 + 4 + 4 = 18
Approach 1: Brute Force
Intuition
For each window, scan all k elements to find the minimum and maximum. Add their sum to the result.
Algorithm
- For each window starting at index i:
- Find minimum element in window
- Find maximum element in window
- Add min + max to total sum
- Return total sum
java
public class SumMinMax {
public static int sumMinMaxBruteForce(int[] arr, int k) {
int n = arr.length;
int totalSum = 0;
for (int i = 0; i <= n - k; i++) {
int minVal = Integer.MAX_VALUE;
int maxVal = Integer.MIN_VALUE;
for (int j = i; j < i + k; j++) {
minVal = Math.min(minVal, arr[j]);
maxVal = Math.max(maxVal, arr[j]);
}
totalSum += minVal + maxVal;
}
return totalSum;
}
public static void main(String[] args) {
int[] arr = {2, 5, -1, 7, -3, -1, -2};
int k = 4;
System.out.println("Sum of min and max: " + sumMinMaxBruteForce(arr, k)); // 18
}
}Complexity Analysis
- Time Complexity: O(n*k) - for each window, scan k elements
- Space Complexity: O(1) - only using variables
Approach 2: Optimal (Two Deques)
Intuition
Use two deques: one to track maximum elements (monotonic decreasing) and one to track minimum elements (monotonic increasing). Each deque maintains indices of potential max/min candidates.
Algorithm
- Use maxDeque: maintains decreasing order (front has max)
- Use minDeque: maintains increasing order (front has min)
- For each element:
- Remove indices outside window from front
- Remove smaller elements from maxDeque back (they can't be max)
- Remove larger elements from minDeque back (they can't be min)
- Add current index
- Add front values to result after first window
java
import java.util.*;
public class SumMinMax {
public static int sumMinMax(int[] arr, int k) {
int n = arr.length;
Deque<Integer> maxDq = new ArrayDeque<>(); // Decreasing
Deque<Integer> minDq = new ArrayDeque<>(); // Increasing
int totalSum = 0;
for (int i = 0; i < n; i++) {
// Remove elements outside window from front
while (!maxDq.isEmpty() && maxDq.peekFirst() <= i - k) {
maxDq.pollFirst();
}
while (!minDq.isEmpty() && minDq.peekFirst() <= i - k) {
minDq.pollFirst();
}
// Remove smaller elements from maxDq
while (!maxDq.isEmpty() && arr[maxDq.peekLast()] <= arr[i]) {
maxDq.pollLast();
}
// Remove larger elements from minDq
while (!minDq.isEmpty() && arr[minDq.peekLast()] >= arr[i]) {
minDq.pollLast();
}
// Add current index
maxDq.addLast(i);
minDq.addLast(i);
// Add to sum after first window is complete
if (i >= k - 1) {
totalSum += arr[maxDq.peekFirst()] + arr[minDq.peekFirst()];
}
}
return totalSum;
}
public static void main(String[] args) {
int[] arr = {2, 5, -1, 7, -3, -1, -2};
int k = 4;
System.out.println("Sum of min and max: " + sumMinMax(arr, k)); // 18
}
}Complexity Analysis
- Time Complexity: O(n) - each element added/removed from deque at most once
- Space Complexity: O(k) - each deque holds at most k elements
Approach 3: Finding Min and Max Separately
Intuition
Find minimum of all windows first, then maximum of all windows. Sum them up. This is essentially the same as approach 2 but more modular.
Algorithm
- Find all window minimums using monotonic increasing deque
- Find all window maximums using monotonic decreasing deque
- Sum the arrays
java
import java.util.*;
public class SumMinMax {
public static List<Integer> getWindowMin(int[] arr, int k) {
int n = arr.length;
Deque<Integer> dq = new ArrayDeque<>();
List<Integer> result = new ArrayList<>();
for (int i = 0; i < n; i++) {
while (!dq.isEmpty() && dq.peekFirst() <= i - k) {
dq.pollFirst();
}
while (!dq.isEmpty() && arr[dq.peekLast()] >= arr[i]) {
dq.pollLast();
}
dq.addLast(i);
if (i >= k - 1) {
result.add(arr[dq.peekFirst()]);
}
}
return result;
}
public static List<Integer> getWindowMax(int[] arr, int k) {
int n = arr.length;
Deque<Integer> dq = new ArrayDeque<>();
List<Integer> result = new ArrayList<>();
for (int i = 0; i < n; i++) {
while (!dq.isEmpty() && dq.peekFirst() <= i - k) {
dq.pollFirst();
}
while (!dq.isEmpty() && arr[dq.peekLast()] <= arr[i]) {
dq.pollLast();
}
dq.addLast(i);
if (i >= k - 1) {
result.add(arr[dq.peekFirst()]);
}
}
return result;
}
public static int sumMinMax(int[] arr, int k) {
List<Integer> mins = getWindowMin(arr, k);
List<Integer> maxs = getWindowMax(arr, k);
int totalSum = 0;
for (int i = 0; i < mins.size(); i++) {
totalSum += mins.get(i) + maxs.get(i);
}
return totalSum;
}
public static void main(String[] args) {
int[] arr = {2, 5, -1, 7, -3, -1, -2};
int k = 4;
System.out.println("Window minimums: " + getWindowMin(arr, k));
System.out.println("Window maximums: " + getWindowMax(arr, k));
System.out.println("Sum of min and max: " + sumMinMax(arr, k));
}
}Complexity Analysis
- Time Complexity: O(n) - two passes, each O(n)
- Space Complexity: O(k) for deques + O(n-k+1) for results
Key Takeaways
- Monotonic Deque: Key technique for sliding window min/max problems
- Two Deques: One for max (decreasing), one for min (increasing)
- Index Storage: Store indices to handle window boundaries
- Amortized O(1): Each element enters and exits deque at most once
- Related Problems: Sliding Window Maximum (LeetCode 239), Stock Span
- This pattern is fundamental for many sliding window optimization problems