Range Minimum Query via Sparse Table

Reported in interviews at Barclays Citadel Hudson River Trading Two Sigma

Problem statement

You are given an integer array $A$ of length $n$ (1-indexed: $A[1], A[2], \ldots, A[n]$). You need to build a data structure that, after preprocessing, can answer range minimum queries: given indices $l$ and $r$ with $1 \le l \le r \le n$, return $\min(A[l], A[l+1], \ldots, A[r])$ in $O(1)$ time per query.

Use the sparse table approach:

  1. Build a 2D table $\text{ST}[i][k]$ that stores the minimum value of the subarray of length $2^k$ starting at index $i$. Formally, $\text{ST}[i][k] = \min(A[i], A[i+1], \ldots, A[i + 2^k - 1])$.
  1. To answer a query $(l, r)$, decompose it into two (possibly overlapping) blocks of length $2^k$ that together cover $[l, r]$, and return the minimum of the two block minima.

Implement both the preprocessing and query functions. Your solution should use $O(n \log n)$ time and space for preprocessing, and $O(1)$ time per query.

Constraints:

  • $1 \le n \le 10^5$
  • $-10^9 \le A[i] \le 10^9$
  • Up to $10^6$ queries $(l, r)$ with $1 \le l \le r \le n$

Example 1:

  • Input: $A = [3, 1, 4, 1, 5, 9, 2, 6]$, query $(2, 7)$
  • Output: $1$
  • Explanation: $\min(1, 4, 1, 5, 9, 2) = 1$

Example 2:

  • Input: $A = [7]$, query $(1, 1)$
  • Output: $7$
  • Explanation: Single-element array, the minimum is the element itself.

Example 3:

  • Input: $A = [5, 5, 5, 5]$, query $(1, 4)$
  • Output: $5$
  • Explanation: All elements are tied; the minimum is $5$.

You must implement the function range_min(A, queries), where queries is a list of [l, r] pairs (1-based, inclusive). Return the list of range minima, one per query, in order.

Example

range_min([3, 1, 4, 1, 5, 9, 2, 6], [[2, 7]]) -> [1]

The single query asks for the minimum of A[2..7] (1-based) = min(1, 4, 1, 5, 9, 2) = 1, so the returned list is [1]. Note the answer is a list of results, even for one query.

Show hint

Which property of the minimum lets you combine two answers even if they describe overlapping stretches of the array?

Relevant roles: ML Engineer, AI Engineer, Forward Deployed Engineer and LLM Engineer.

Related free problems