Maximum Subarray Min-Product - Practice Coding Problems

Maximum Subarray Min-Product - Problem

The min-product of an array is equal to the minimum value in the array multiplied by the array's sum.

For example, the array [3,2,5] (minimum value is 2) has a min-product of 2 * (3+2+5) = 2 * 10 = 20.

Given an array of integers nums, return the maximum min-product of any non-empty subarray of nums. Since the answer may be large, return it modulo 10⁹ + 7.

Note that the min-product should be maximized before performing the modulo operation. Testcases are generated such that the maximum min-product without modulo will fit in a 64-bit signed integer.

A subarray is a contiguous part of an array.

Input & Output

Example 1 — Basic Case

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

› Output: 14

💡 Note: The subarray [2,3,2] has minimum 2 and sum 7, giving min-product = 2 × 7 = 14, which is maximum among all subarrays.

Example 2 — Single Element

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

› Output: 18

💡 Note: The subarray [2,3,3] has minimum 2 and sum 8, giving min-product = 2 × 8 = 16. But [3,3] has min-product = 3 × 6 = 18.

Example 3 — Large Numbers

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

› Output: 60

💡 Note: The subarray [5,6,4] has minimum 4 and sum 15, giving min-product = 4 × 15 = 60, which is the maximum.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁷

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array [1,2,3,2] with different elements

Find Subarrays

Consider all possible contiguous subarrays

Calculate Min-Products

For each subarray: min-product = minimum × sum

Key Takeaway

🎯 Key Insight: For each element as the minimum, find the largest possible subarray containing it using monotonic stack

Asked in

G Google 25 a Amazon 18 M Microsoft 15 A Apple 12

The key insight is to find the largest subarray where each element serves as the minimum. The optimal approach uses a monotonic stack to efficiently find left and right boundaries for each element in O(n) time, combined with prefix sums for fast range queries. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Monotonic Stack (Optimal)	O(n)	O(n)	Use monotonic stack to find optimal subarrays for each element as minimum
Prefix Sum Optimization	O(n²)	O(n)	Use prefix sums to quickly calculate subarray sums
Brute Force - Check All Subarrays	O(n³)	O(1)	Check every possible subarray and calculate its min-product

Monotonic Stack (Optimal) — Algorithm Steps

Use stack to find left and right boundaries for each element
Calculate prefix sums for range queries
For each element as minimum, find its optimal subarray

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Boundaries

Use stack to find left/right bounds for each element

Calculate Range Sum

For each element as min, get sum of its optimal range

Maximum Product

Track the largest min-product across all elements

Code -

solution.c — C

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

int solution(int* nums, int numsSize) {
    const int MOD = 1000000007;
    
    // Build prefix sum array
    long long* prefix = (long long*)calloc(numsSize + 1, sizeof(long long));
    for (int i = 0; i < numsSize; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    
    // Find left boundaries (first smaller element to the left)
    int* left = (int*)malloc(numsSize * sizeof(int));
    int* stack = (int*)malloc(numsSize * sizeof(int));
    int stackSize = 0;
    
    for (int i = 0; i < numsSize; i++) {
        while (stackSize > 0 && nums[stack[stackSize - 1]] >= nums[i]) {
            stackSize--;
        }
        left[i] = stackSize > 0 ? stack[stackSize - 1] : -1;
        stack[stackSize++] = i;
    }
    
    // Find right boundaries (first smaller element to the right)
    int* right = (int*)malloc(numsSize * sizeof(int));
    stackSize = 0;
    
    for (int i = numsSize - 1; i >= 0; i--) {
        while (stackSize > 0 && nums[stack[stackSize - 1]] > nums[i]) {
            stackSize--;
        }
        right[i] = stackSize > 0 ? stack[stackSize - 1] : numsSize;
        stack[stackSize++] = i;
    }
    
    long long maxProduct = 0;
    for (int i = 0; i < numsSize; i++) {
        // For nums[i] as minimum, the valid range is (left[i], right[i])
        int l = left[i] + 1;
        int r = right[i] - 1;
        long long subarraySum = prefix[r + 1] - prefix[l];
        long long minProduct = (long long) nums[i] * subarraySum;
        if (minProduct > maxProduct) {
            maxProduct = minProduct;
        }
    }
    
    free(prefix);
    free(left);
    free(right);
    free(stack);
    
    return maxProduct % MOD;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    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 result = solution(nums, numsSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass with stack operations, each element pushed/popped once

✓ Linear Growth

Space Complexity

O(n)

Stack for boundaries and prefix sum array

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~25 min Avg. Time

982 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

Monotonic Stack (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler