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.

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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 <= 80000
  • 1 <= k <= nums.length
  • -10^6 <= nums[i] <= 10^6

Examples

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

  1. 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.
  2. Return the total sum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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.