Till ranges

Given an integer array days and an array of queries queries, return one sum per query in the original query order. Each query [l, r] asks for the sum from index l through index r, inclusive. Indices start at zero and satisfy 0 ≤ l ≤ r < len(days). Values may be negative. If there are no queries, return an empty array.

Example:

till_ranges([2, 8, 3, 5], [[0, 1], [1, 3]])  →  [10, 16]

Indices 0–1: 2+8=10. Indices 1–3: 8+3+5=16.

till_ranges([5], [[0, 0]])  →  [5]

A query covering one element is just that number.

Pattern: prefix_sum - build prefix once; each query is prefix[r+1] - prefix[l]

Need a hint?

Reveal one step at a time. Stop when you have enough to keep going.

1 · What to notice

If you know the sum before a fragment and the sum through its end, how can you remove everything before the fragment?

2 · Walk through an example

For days = [2, 8, 3, 5], store prefix = [0, 2, 10, 13, 18]. prefix[i] is the sum of the first i elements. Query [1, 3] gives prefix[4] − prefix[1] = 18 − 2 = 16. The end is inclusive, so use r + 1. The initial zero handles l = 0 without a special case.

3 · Pseudocode and self-check

Language-independent pseudocode. Indices start at 0; ← means assignment. Ranges with an upper bound exclude that bound.

prefix ← [0]
FOR EACH value IN days:
    APPEND LAST(prefix) + value TO prefix
result ← []
FOR EACH (left, right) IN queries:
    APPEND prefix[right + 1] - prefix[left] TO result
RETURN result

Check your reasoning

[l, l] returns days[l]. Empty queries → []. Negative numbers do not change the subtraction rule. Time O(n + q), auxiliary space O(n).

Python TypeScript Go Rust Pro Java Pro Swift Pro

Till ranges

Cookies and analytics