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: 27

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

Constraints

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

Visualization

Tap to expand

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

✓ Greedy

⏱️ Time: N/A Space: N/A

Brute Force

⏱️ Time: O(n²k) Space: O(1)

For each possible starting position and each possible length from 1 to k, generate the subarray and find its minimum and maximum elements. Add both to the result sum.

Optimized with Monotonic Stack

⏱️ Time: O(nk) Space: O(k)

Instead of recalculating min/max for every subarray, use monotonic deques that maintain the minimum and maximum elements in each sliding window efficiently.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

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

long long solution(int* nums, int n, int k) {
    long long totalSum = 0;
    
    // Generate all subarrays of length 1 to k
    for (int len = 1; len <= k; len++) {
        for (int i = 0; i <= n - len; i++) {
            int maxVal = INT_MIN;
            int minVal = INT_MAX;
            
            // Find max and min in current subarray
            for (int j = i; j < i + len; j++) {
                if (nums[j] > maxVal) maxVal = nums[j];
                if (nums[j] < minVal) minVal = nums[j];
            }
            
            totalSum += maxVal + minVal;
        }
    }
    
    return totalSum;
}

int parseArray(char* input, int** nums) {
    // Find the array part (first line)
    char* arrayStart = strchr(input, '[');
    if (!arrayStart) return 0;
    
    // Count elements
    int count = 0;
    char* temp = arrayStart + 1;
    if (*temp != ']') {
        count = 1;
        while (*temp && *temp != ']') {
            if (*temp == ',') count++;
            temp++;
        }
    }
    
    if (count == 0) return 0;
    
    *nums = (int*)malloc(count * sizeof(int));
    
    // Parse elements
    char* ptr = arrayStart + 1; // Skip '['
    for (int i = 0; i < count; i++) {
        while (*ptr == ' ') ptr++; // Skip spaces
        (*nums)[i] = atoi(ptr);
        
        // Move to next number or end
        if (*ptr == '-') ptr++; // Skip negative sign
        while (*ptr >= '0' && *ptr <= '9') ptr++; // Skip digits
        while (*ptr == ' ' || *ptr == ',') ptr++; // Skip spaces and comma
    }
    
    return count;
}

int main() {
    char input[10000];
    char kInput[100];
    
    fgets(input, sizeof(input), stdin);
    fgets(kInput, sizeof(kInput), stdin);
    
    int* nums;
    int n = parseArray(input, &nums);
    int k = atoi(kInput);
    
    printf("%lld\n", solution(nums, n, k));
    
    free(nums);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

✓ Linear Growth

Space Complexity

✓ 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