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 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
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.
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
- Largest Rectangle in Histogram Hard Free The biggest rectangle that fits under the bars.
- Shortest Subarray With Sum at Least K Hard Free Find the shortest target-reaching interval when negative values break the usual window.
- Multiply Numeric Strings Medium Free Schoolbook multiplication of numbers thousands of digits long.
- Modular Exponentiation Medium Free Raise to a power of 10^18 - one squaring at a time.