Module 6 · Stacks and Queues · Sum of Subarray Ranges

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.

Chapter

The three counts

  1. Elements from i to j: j − i + 1 with both ends, j − i with one, j − i − 1 with neither.
  2. Subarrays of n elements: n + (n − 1) + … + 1 = n × (n + 1) / 2.
  3. Subarrays including k, strictly between i and j: (k − i) × (j − k); use i = -1 or j = arr.length when there is no wall on that side.