Maximum and Minimum Sums of at Most Size K Subarrays

Maximum and Minimum Sums of at Most Size K Subarrays - 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.

A subarray is a contiguous non-empty sequence of elements within an array.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,3,2], k = 2

› Output: 21

💡 Note: All subarrays: [1] (1+1=2), [3] (3+3=6), [2] (2+2=4), [1,3] (1+3=4), [3,2] (2+3=5). Total: 2+6+4+4+5=21

Example 2 — Single Element

$ Input: nums = [5], k = 1

› Output: 10

💡 Note: Only one subarray [5] with min=5, max=5, so sum = 5+5 = 10

Example 3 — Larger k

$ Input: nums = [2,1,4], k = 3

› Output: 36

💡 Note: All subarrays: [2](4), [1](2), [4](8), [2,1](3), [1,4](5), [2,1,4](6). Total: 4+2+8+3+5+6+8=36

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ k ≤ nums.length
-10⁴ ≤ nums[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,3,2] with k=2

Process

Generate all subarrays of length 1 to k, find their min+max

Output

Sum of all min+max values = 21

Key Takeaway

🎯 Key Insight: Use monotonic deques to efficiently track running minimum and maximum in sliding windows

Asked in

G Google 12 a Amazon 8 M Microsoft 6

The key insight is to use monotonic deques to efficiently track minimum and maximum elements in sliding windows. The optimal approach uses deques to maintain min/max in O(1) amortized time per element. Time: O(nk), Space: O(k).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized with Monotonic Stack	O(nk)	O(k)	Use monotonic deques to efficiently track min/max for sliding windows
Brute Force	O(n²k)	O(1)	Generate all subarrays of size 1 to k and find min/max for each

Optimized with Monotonic Stack — Algorithm Steps

For each starting position, use deques to track min/max
Slide the window and update deques incrementally
Sum min/max from deques for each valid subarray

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Deques

Create min deque (increasing) and max deque (decreasing)

Expand Window

Add elements while maintaining deque properties

Track Min/Max

Front of deques always contains current min/max

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long solution(int* nums, int numsSize, int k) {
    long long totalSum = 0;
    
    for (int i = 0; i < numsSize; i++) {
        int minDeque[1000], maxDeque[1000];
        int minFront = 0, minRear = 0;
        int maxFront = 0, maxRear = 0;
        
        int maxJ = (i + k < numsSize) ? i + k : numsSize;
        
        for (int j = i; j < maxJ; j++) {
            // Maintain minDeque (increasing order)
            while (minRear > minFront && nums[minDeque[minRear-1]] >= nums[j]) {
                minRear--;
            }
            minDeque[minRear++] = j;
            
            // Maintain maxDeque (decreasing order)
            while (maxRear > maxFront && nums[maxDeque[maxRear-1]] <= nums[j]) {
                maxRear--;
            }
            maxDeque[maxRear++] = j;
            
            // Add current subarray's min + max
            totalSum += nums[minDeque[minFront]] + nums[maxDeque[maxFront]];
        }
    }
    
    return totalSum;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[100];
    int numsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '[' && token[0] != ']') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int k;
    scanf("%d", &k);
    
    long long result = solution(nums, numsSize, k);
    printf("%lld\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(nk)

For each of n starting positions, we expand window up to k elements with amortized O(1) deque operations

✓ Linear Growth

Space Complexity

O(k)

Deques store at most k elements for tracking min/max in current window

✓ Linear Space

12.5K Views

Medium Frequency

~35 min Avg. Time

428 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized with Monotonic Stack — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler