Skip to content
Katabench
Try free

Sum of Subarray Minimums

Hard About 35 min Free, no account needed

Add the minimum of every contiguous subarray - by counting, not enumerating.

The brief

Given an array of positive integers arr, return the sum of min(b) over every contiguous subarray b.

The performance bar

The obvious approach runs a running-minimum from every start, O(n2), five billion steps on the hidden 100,000-element test, so it's too slow. You need O(n), which means finding the total without scanning every subarray. Watch how you handle equal values so ties are counted exactly once.

Starter code

C#
using System;

public class Solution
{
    // TODO: return the sum of the minimum of every contiguous subarray.
    public long SumSubarrayMins(int[] arr)
    {
        throw new NotImplementedException();
    }
}

How it is graded

Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.

C# coding challenges →

What it practices

Monotonic stack
Keep a stack in sorted order to answer next-greater and span questions in one pass.
Math and number theory
Replace enumeration with a formula: GCD, modular arithmetic, digit math and closed-form counting.

Do these first

Related katas