Maximum and Minimum Sums of at Most Size K Subarrays
HardUpdated: Aug 2, 2025
Practice on:
Problem
You are given an integer array nums and a positive integer k. Return the sum of the maximum and minimum elements of all subarrays with at most k elements.
Examples
Example 1
Input: nums = [1,2,3], k = 2
Output: 20
Explanation:
The subarrays of `nums` with at most 2 elements are:
**Subarray** | Minimum | Maximum | Sum
---|---|---|---
`[1]` | 1 | 1 | 2
`[2]` | 2 | 2 | 4
`[3]` | 3 | 3 | 6
`[1, 2]` | 1 | 2 | 3
`[2, 3]` | 2 | 3 | 5
**Final Total** | | | 20
The output would be 20.
Example 2
Input: nums = [1,-3,1], k = 2
Output: -6
Explanation:
The subarrays of `nums` with at most 2 elements are:
**Subarray** | Minimum | Maximum | Sum
---|---|---|---
`[1]` | 1 | 1 | 2
`[-3]` | -3 | -3 | -6
`[1]` | 1 | 1 | 2
`[1, -3]` | -3 | 1 | -2
`[-3, 1]` | -3 | 1 | -2
**Final Total** | | | -6
The output would be -6.
Constraints
1 <= nums.length <= 800001 <= k <= nums.length-10^6 <= nums[i] <= 10^6
Solution
Method 1 – Monotonic Queue (Sliding Window for Min/Max)
Intuition
For each subarray of length at most k, we want to efficiently find the minimum and maximum. We can use two monotonic queues (deques): one for minimums and one for maximums, to maintain the current window's min and max in O(1) time per step. We slide a window of size up to k over the array and sum the min and max for all possible subarrays.
Approach
- For each possible window size from 1 to k:
- Use two deques to maintain the min and max for the current window.
- Slide the window over the array, updating the deques and summing the min and max for each subarray.
- Return the total sum.
Code
C++
class Solution {
public:
long long sumOfMaxAndMin(vector<int>& nums, int k) {
int n = nums.size();
long long ans = 0;
for (int len = 1; len <= k; ++len) {
deque<int> minq, maxq;
for (int i = 0; i < n; ++i) {
while (!minq.empty() && minq.front() <= i - len) minq.pop_front();
while (!maxq.empty() && maxq.front() <= i - len) maxq.pop_front();
while (!minq.empty() && nums[minq.back()] >= nums[i]) minq.pop_back();
while (!maxq.empty() && nums[maxq.back()] <= nums[i]) maxq.pop_back();
minq.push_back(i);
maxq.push_back(i);
if (i >= len - 1) {
ans += nums[minq.front()] + nums[maxq.front()];
}
}
}
return ans;
}
};
Go
func sumOfMaxAndMin(nums []int, k int) int64 {
n := len(nums)
var ans int64
for l := 1; l <= k; l++ {
minq, maxq := []int{}, []int{}
for i := 0; i < n; i++ {
for len(minq) > 0 && minq[0] <= i-l {
minq = minq[1:]
}
for len(maxq) > 0 && maxq[0] <= i-l {
maxq = maxq[1:]
}
for len(minq) > 0 && nums[minq[len(minq)-1]] >= nums[i] {
minq = minq[:len(minq)-1]
}
for len(maxq) > 0 && nums[maxq[len(maxq)-1]] <= nums[i] {
maxq = maxq[:len(maxq)-1]
}
minq = append(minq, i)
maxq = append(maxq, i)
if i >= l-1 {
ans += int64(nums[minq[0]] + nums[maxq[0]])
}
}
}
return ans
}
Java
class Solution {
public long sumOfMaxAndMin(int[] nums, int k) {
int n = nums.length;
long ans = 0;
for (int len = 1; len <= k; ++len) {
Deque<Integer> minq = new ArrayDeque<>(), maxq = new ArrayDeque<>();
for (int i = 0; i < n; ++i) {
while (!minq.isEmpty() && minq.peekFirst() <= i - len) minq.pollFirst();
while (!maxq.isEmpty() && maxq.peekFirst() <= i - len) maxq.pollFirst();
while (!minq.isEmpty() && nums[minq.peekLast()] >= nums[i]) minq.pollLast();
while (!maxq.isEmpty() && nums[maxq.peekLast()] <= nums[i]) maxq.pollLast();
minq.addLast(i);
maxq.addLast(i);
if (i >= len - 1) {
ans += nums[minq.peekFirst()] + nums[maxq.peekFirst()];
}
}
}
return ans;
}
}
Kotlin
class Solution {
fun sumOfMaxAndMin(nums: IntArray, k: Int): Long {
val n = nums.size
var ans = 0L
for (len in 1..k) {
val minq = ArrayDeque<Int>()
val maxq = ArrayDeque<Int>()
for (i in 0 until n) {
while (minq.isNotEmpty() && minq.first() <= i - len) minq.removeFirst()
while (maxq.isNotEmpty() && maxq.first() <= i - len) maxq.removeFirst()
while (minq.isNotEmpty() && nums[minq.last()] >= nums[i]) minq.removeLast()
while (maxq.isNotEmpty() && nums[maxq.last()] <= nums[i]) maxq.removeLast()
minq.addLast(i)
maxq.addLast(i)
if (i >= len - 1) {
ans += nums[minq.first()] + nums[maxq.first()]
}
}
}
return ans
}
}
Python
class Solution:
def sumOfMaxAndMin(self, nums: list[int], k: int) -> int:
from collections import deque
n = len(nums)
ans = 0
for l in range(1, k+1):
minq, maxq = deque(), deque()
for i in range(n):
while minq and minq[0] <= i-l:
minq.popleft()
while maxq and maxq[0] <= i-l:
maxq.popleft()
while minq and nums[minq[-1]] >= nums[i]:
minq.pop()
while maxq and nums[maxq[-1]] <= nums[i]:
maxq.pop()
minq.append(i)
maxq.append(i)
if i >= l-1:
ans += nums[minq[0]] + nums[maxq[0]]
return ans
Rust
impl Solution {
pub fn sum_of_max_and_min(nums: Vec<i32>, k: i32) -> i64 {
let n = nums.len();
let mut ans = 0i64;
for len in 1..=k as usize {
let mut minq = std::collections::VecDeque::new();
let mut maxq = std::collections::VecDeque::new();
for i in 0..n {
while minq.front().map_or(false, |&idx| idx <= i-len) { minq.pop_front(); }
while maxq.front().map_or(false, |&idx| idx <= i-len) { maxq.pop_front(); }
while minq.back().map_or(false, |&idx| nums[idx] >= nums[i]) { minq.pop_back(); }
while maxq.back().map_or(false, |&idx| nums[idx] <= nums[i]) { maxq.pop_back(); }
minq.push_back(i);
maxq.push_back(i);
if i+1 >= len {
ans += nums[*minq.front().unwrap()] as i64 + nums[*maxq.front().unwrap()] as i64;
}
}
}
ans
}
}
TypeScript
class Solution {
sumOfMaxAndMin(nums: number[], k: number): number {
const n = nums.length;
let ans = 0;
for (let len = 1; len <= k; ++len) {
const minq: number[] = [], maxq: number[] = [];
for (let i = 0; i < n; ++i) {
while (minq.length && minq[0] <= i - len) minq.shift();
while (maxq.length && maxq[0] <= i - len) maxq.shift();
while (minq.length && nums[minq[minq.length-1]] >= nums[i]) minq.pop();
while (maxq.length && nums[maxq[maxq.length-1]] <= nums[i]) maxq.pop();
minq.push(i);
maxq.push(i);
if (i >= len - 1) {
ans += nums[minq[0]] + nums[maxq[0]];
}
}
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n * k), since for each window size up to k, we process each element once. - 🧺 Space complexity:
O(k), for the deques used in each window.