Subarray counting basics
Stack questions like Sum of Subarray Minimums never list subarrays: they count them. Pick a chapter: how many
elements lie between indices i and j, how many subarrays fit between them, and how many
of those include one index k. The window on arr is the part being counted, its label the
count; greyed cells are left out.
The three counts
- Elements from i to j:
j − i + 1with both ends,j − iwith one,j − i − 1with neither. - Subarrays of n elements:
n + (n − 1) + … + 1 = n × (n + 1) / 2. - Subarrays including k, strictly between i and j:
(k − i) × (j − k); usei = -1orj = arr.lengthwhen there is no wall on that side.