We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum and Minimum Sums of at Most Size K Subarrays

Number: 3725

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an integer array nums and a positive integer k, consider every contiguous subarray of nums with size at most k. For each subarray, determine its minimum and maximum elements and then add these two values. Return the total sum over all such subarrays.

Key Insights

  • We need to sum, for every subarray of length L (1 ≤ L ≤ k), the quantity (minimum + maximum).
  • Instead of iterating over every subarray (which is O(n·k) in the worst-case), we can “flip” the problem.
  • Compute for each element how many subarrays (with length ≤ k) it serves as the minimum and similarly as the maximum.
  • Use standard monotonic stack techniques to compute, for each index, its “span” to the left and right where it remains the minimum/maximum.
  • The key twist is to count only those subarrays that satisfy the length constraint. For an element at index i with left span L and right span R, subarrays in which it is the extreme element are formed by choosing l (from 1 up to L) positions to the left and r (from 1 up to R) to the right, but with l + r – 1 ≤ k.
  • With a little arithmetic we can sum over valid pairs (l, r) in O(1) per element.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

We first compute for each element its left and right spans where it remains the minimum (for the min part) and similarly for maximum (for the max part) using monotonic stacks. For minimum computations, we use a stack to get the index of the previous element that is strictly less and the next element that is less than or equal; for maximum we use “previous greater” and “next greater or equal”.

Then, using these spans, for an element with left span L and right span R the total number of subarrays (without length constraint) in which it is the minimum (or maximum) is L * R. Here, however, we need only those subarrays of length at most k.
A subarray “covering” the element can be thought of as choosing l positions (1 ≤ l ≤ L) to the left (including the element itself) and r positions (1 ≤ r ≤ R) to the right so that the subarray size is l + r – 1. The constraint l + r – 1 ≤ k can be rewritten as r ≤ k + 1 – l. Thus for each possible l (up to min(L, k)), the number of valid r is min(R, k + 1 – l) (when k + 1 – l is positive). We sum these contributions per element in O(1) time using simple arithmetic after splitting the range appropriately into two parts.

Finally, the overall answer is the sum over all elements of:
  (element’s value) * (number of subarrays where it is maximum) + (element’s value) * (number of subarrays where it is minimum).

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java. Each solution uses monotonic stacks to compute the spans and then counts the valid subarrays efficiently, with inline comments explaining each step.

def count_subarrays(span_left, span_right, k):
    # Only consider l from 1 to effective L = min(span_left, k)
    L_effective = min(span_left, k)
    count = 0
    # For l in 1...L_effective, valid r = min(span_right, k+1 - l) if k+1 - l > 0
    # Instead of iterating l one by one, we break the range into two parts.
    # Define L1 as the largest l such that (k+1 - l) >= span_right, i.e. l <= k+1 - span_right.
    L1 = min(L_effective, max(0, k + 1 - span_right))
    # For l = 1 to L1, we can take all r up to span_right.
    count += span_right * L1
    # For l = L1+1 to L_effective, valid r is (k + 1 - l)
    if L_effective > L1:
        # Sum (k+1 - l) for l from L1+1 to L_effective.
        num_terms = L_effective - L1
        # Sum of arithmetic sequence: (first + last)*num_terms//2
        first = k + 1 - (L1 + 1)
        last = k + 1 - L_effective
        count += (first + last) * num_terms // 2
    return count

def total_sum(nums, k):
    n = len(nums)
    # Compute spans for minimum using monotonic increasing stack.
    left_min = [0] * n
    right_min = [0] * n
    stack = []
    for i in range(n):
        # Find previous element that is strictly smaller.
        while stack and nums[stack[-1]] > nums[i]:
            stack.pop()
        left_min[i] = i - stack[-1] if stack else i + 1
        stack.append(i)
    stack = []
    for i in range(n-1, -1, -1):
        # Next less or equal element.
        while stack and nums[stack[-1]] >= nums[i]:
            stack.pop()
        right_min[i] = stack[-1] - i if stack else n - i
        stack.append(i)
    
    # Compute spans for maximum using monotonic decreasing stack.
    left_max = [0] * n
    right_max = [0] * n
    stack = []
    for i in range(n):
        # Previous element strictly greater.
        while stack and nums[stack[-1]] < nums[i]:
            stack.pop()
        left_max[i] = i - stack[-1] if stack else i + 1
        stack.append(i)
    stack = []
    for i in range(n-1, -1, -1):
        # Next greater or equal element.
        while stack and nums[stack[-1]] <= nums[i]:
            stack.pop()
        right_max[i] = stack[-1] - i if stack else n - i
        stack.append(i)
    
    total = 0
    for i in range(n):
        count_min = count_subarrays(left_min[i], right_min[i], k)
        count_max = count_subarrays(left_max[i], right_max[i], k)
        total += nums[i] * (count_min + count_max)
    return total

# Example usage:
print(total_sum([1,2,3], 2))   # Expected output: 20
print(total_sum([1,-3,1], 2))  # Expected output: -6
← Back to All Questions