Log inSign up
mediumGeeksforGeeksNot Started

Range Minimum Query

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Advanced DSA
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an integer array nums of size n and an array of range queries queries where each query is given as [L, R] (0-indexed, inclusive), find the minimum element in the subarray nums[L...R].

Return an array containing the minimum for each query.

Because the minimum operation is idempotent ($min(x, x) = x), the Sparse Table data structure answers each range minimum query in strictly O(1) time after O(n log n) preprocessing.

Example 1 · Example 1:

Input: nums = [7, 2, 3, 0, 5, 10, 3, 12, 18], queries = [[0, 4], [4, 7], [7, 8]]
Output: [0, 3, 12]
Explanation: For query [0, 4]: subarray is [7, 2, 3, 0, 5], minimum is 0. For query [4, 7]: subarray is [5, 10, 3, 12], minimum is 3. For query [7, 8]: subarray is [12, 18], minimum is 12.

Example 2 · Example 2:

Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], queries = [[0, 2], [2, 5]]
Output: [-1, -3]
Explanation: Min of [1, 3, -1] is -1. Min of [-1, -3, 5, 3] is -3.

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= queries.length <= 105
  • 0 <= L <= R < nums.length
  • -109 <= nums[i] <= 109

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 3 distinct approaches for Range Minimum Query.
  • Implement fully runnable solutions in C++, Java, Python, and JavaScript.
  • Analyze algorithmic trade-offs across data structure designs.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Range Minimum Query
  • Advanced Data Structures & Algorithmic Paradigm
  • Fast Range Queries or Amortized Dynamic Operations

Algorithmic Decision Tree:

  • BRUTE_FORCE: Basic prototyping when Q <= 100.
  • BETTER: When elements in the array may also undergo point updates.
  • OPTIMAL: The premier gold standard for static Range Minimum Queries on immutable arrays.

Connected Patterns:

Segment TreeFenwick TreeDisjoint Set UnionDesign Data Structures

1. Direct Linear Search

Intuition

Iterate through every query [L, R]. Initialize a variable minVal with \infty and loop from index L to R, updating minVal = min(minVal, nums[i]). Scanning takes O(R - L + 1) = O(n) time per query, totaling O(Q \cdot n) which times out for 105 queries.

When to apply: Basic prototyping when Q <= 100.

Algorithm

  1. Step 1: Iterate through each query [L, R].
  2. Step 2: Initialize minVal = INT_MAX.
  3. Step 3: Loop i from L to R: minVal = min(minVal, nums[i]).
  4. Step 4: Append minVal to answers.
  5. Step 5: Return answers.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <climits>
5
6std::vector<int> solveBruteForce(const std::vector<int>& nums, const std::vector<std::pair<int, int>>& queries) {
7 std::vector<int> ans;
8 ans.reserve(queries.size());
9 for (const auto& q : queries) {
10 int minVal = INT_MAX;
11 for (int i = q.first; i <= q.second; ++i) {
12 minVal = std::min(minVal, nums[i]);
13 }
14 ans.push_back(minVal);
15 }
16 return ans;
17}
18
19int main() {
20 std::vector<int> nums = {7, 2, 3, 0, 5, 10, 3, 12, 18};
21 std::vector<std::pair<int, int>> queries = {{0, 4}, {4, 7}, {7, 8}};
22 auto res = solveBruteForce(nums, queries);
23 for (int x : res) std::cout << x << " ";
24 std::cout << std::endl;
25 return 0;
26}

Time & Space Complexity

  • Time complexity: O(Q * n) time
  • Space complexity: O(1) auxiliary space (excluding results)

2. Segment Tree for RMQ

Intuition

A standard Segment Tree computes the minimum over range [L, R] in O(log n) time: - Built in O(n) time where internal node v = min(\text{left}, \text{right}). - For query [L, R], combine minimums of O(log n) canonical segments. - Can also support point updates in O(log n) if the array changes dynamically. Total query time is O(Q log n), which is very fast, but for static arrays, Sparse Table achieves O(1) query time.

When to apply: When elements in the array may also undergo point updates.

Algorithm

  1. Step 1: Build segment tree of size 4 * n storing range minimums.
  2. Step 2: Define query(node, start, end, l, r): if disjoint return infinity; if within [l, r] return tree[node]; else return min(query(left), query(right)).
  3. Step 3: Answer each query in O(log n) time.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <climits>
5
6struct SegTreeRMQ {
7 int n;
8 std::vector<int> tree;
9
10 SegTreeRMQ(const std::vector<int>& arr) : n(arr.size()), tree(4 * arr.size()) {
11 build(1, 0, n - 1, arr);
12 }
13
14 void build(int node, int start, int end, const std::vector<int>& arr) {
15 if (start == end) {
16 tree[node] = arr[start];
17 return;
18 }
19 int mid = (start + end) / 2;
20 build(2 * node, start, mid, arr);
21 build(2 * node + 1, mid + 1, end, arr);
22 tree[node] = std::min(tree[2 * node], tree[2 * node + 1]);
23 }
24
25 int query(int node, int start, int end, int l, int r) {
26 if (r < start || end < l) return INT_MAX;
27 if (l <= start && end <= r) return tree[node];
28 int mid = (start + end) / 2;
29 return std::min(query(2 * node, start, mid, l, r), query(2 * node + 1, mid + 1, end, l, r));
30 }
31};
32
33std::vector<int> solveSegTree(const std::vector<int>& nums, const std::vector<std::pair<int, int>>& queries) {
34 SegTreeRMQ st(nums);
35 std::vector<int> ans;
36 ans.reserve(queries.size());
37 for (const auto& q : queries) {
38 ans.push_back(st.query(1, 0, (int)nums.size() - 1, q.first, q.second));
39 }
40 return ans;
41}
42
43int main() {
44 std::vector<int> nums = {7, 2, 3, 0, 5, 10, 3, 12, 18};
45 std::vector<std::pair<int, int>> queries = {{0, 4}, {4, 7}, {7, 8}};
46 auto res = solveSegTree(nums, queries);
47 for (int x : res) std::cout << x << " ";
48 std::cout << std::endl;
49 return 0;
50}

Time & Space Complexity

  • Time complexity: O(n + Q log n) time
  • Space complexity: O(n) auxiliary space for tree array

3. Sparse Table (O(1) Range Minimum Queries)

Intuition

Because min is an idempotent operation (i.e. min(x, x) = x), overlapping ranges are completely fine! 1. Precomputation Table `st[k][i]`: - Stores min of the range [i, i + 2k - 1]. - Base case (k = 0): \text{st}[0][i] = nums[i]. - Transition: \text{st}[k][i] = min(\text{st}[k - 1][i], \text{st}[k - 1][i + 2^{k - 1}]). - Table size is O(n log n), built in O(n log n) time. 2. O(1) Query: - For range [L, R], let length len = R - L + 1. - Let k = \lfloor \log_2(len) \rfloor. The power 2k is the largest power of 2 that does not exceed len. - Range [L, R] is completely covered by two overlapping blocks of length 2k: - [L, L + 2k - 1] (given by \text{st}[k][L]) - [R - 2k + 1, R] (given by \text{st}[k][R - 2k + 1]) - \text{ans} = min(\text{st}[k][L], \text{st}[k][R - 2k + 1]). 3. Evaluates in strictly O(1) time without any loops, branches, or recursion!

When to apply: The premier gold standard for static Range Minimum Queries on immutable arrays.

Algorithm

  1. Step 1: Compute log table logTable[1..n] or use __builtin_clz for O(1) log2 computation.
  2. Step 2: Allocate st[K][N] where K = floor(log2(n)) + 1.
  3. Step 3: Initialize st[0][i] = nums[i] for all i.
  4. Step 4: Fill st[k][i] = min(st[k-1][i], st[k-1][i + (1 << (k - 1))]) for k from 1 to K.
  5. Step 5: For each query [L, R], let k = logTable[R - L + 1]. Return min(st[k][L], st[k][R - (1 << k) + 1]).

Interactive trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Initialize Sparse Table for nums = [7, 2, 3, 0, 5, 10, 3, 12, 18] (length 9)
Visual state
Values and pointers at this exact step
pointers
S
7
2
3
0
5
10
3
12
18
0
1
2
3
4
5
6
7
8
Check / comparison
st[0] = elements, st[1] = pairs, st[2] = 4-tuples, st[3] = 8-tuples
Decision / next transition
Preprocessing completes in O(n log n)
Why this step matters

Initialize Sparse Table for nums = [7, 2, 3, 0, 5, 10, 3, 12, 18] (length 9). Precompute powers of 2 intervals up to length 23 = 8.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <cmath>
5
6class SparseTableRMQ {
7 int n, k;
8 std::vector<std::vector<int>> st;
9 std::vector<int> lg;
10public:
11 SparseTableRMQ(const std::vector<int>& arr) {
12 n = arr.size();
13 lg.resize(n + 1);
14 lg[1] = 0;
15 for (int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1;
16
17 k = lg[n] + 1;
18 st.assign(k, std::vector<int>(n));
19
20 for (int i = 0; i < n; ++i) st[0][i] = arr[i];
21
22 for (int j = 1; j < k; ++j) {
23 for (int i = 0; i + (1 << j) <= n; ++i) {
24 st[j][i] = std::min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
25 }
26 }
27 }
28
29 int query(int l, int r) {
30 int j = lg[r - l + 1];
31 return std::min(st[j][l], st[j][r - (1 << j) + 1]);
32 }
33};
34
35std::vector<int> rangeMinimumQuery(const std::vector<int>& nums, const std::vector<std::pair<int, int>>& queries) {
36 SparseTableRMQ st(nums);
37 std::vector<int> ans;
38 ans.reserve(queries.size());
39 for (const auto& q : queries) {
40 ans.push_back(st.query(q.first, q.second));
41 }
42 return ans;
43}
44
45int main() {
46 std::vector<int> nums = {7, 2, 3, 0, 5, 10, 3, 12, 18};
47 std::vector<std::pair<int, int>> queries = {{0, 4}, {4, 7}, {7, 8}};
48 auto res = rangeMinimumQuery(nums, queries);
49 for (int x : res) std::cout << x << " ";
50 std::cout << std::endl;
51 return 0;
52}

Time & Space Complexity

  • Time complexity: O(n log n) preprocessing, O(1) strictly per query
  • Space complexity: O(n log n) auxiliary space for the Sparse Table

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Direct Linear SearchO(Q * n) timeO(1) auxiliary space (excluding results)For each query [L, R], scan elements from L to R maintaining the running minimum.O(Q * n) time
2.Segment Tree for RMQO(n + Q log n) timeO(n) auxiliary space for tree arrayBuild a Segment Tree storing range minimums in O(n) time. Each query runs in O(log n) time.O(n + Q log n) time
3.Sparse Table (O(1) Range Minimum Queries)OptimalO(n log n) preprocessing, O(1) strictly per queryO(n log n) auxiliary space for the Sparse TablePrecompute minimums for intervals of length 2k in O(n log n). Answer any range minimum query in strictly O(1) time using idempotent overlap.O(n log n) preprocessing, O(1) strictly per query

Common Pitfalls & Crucial Edge Cases

Attempting to use Sparse Table when updates are present

Sparse Table takes O(N log N) to rebuild after an update. For dynamic RMQ with updates, use a Segment Tree.

Computing log2 on the fly using floating-point math

log2(len) using double has precision issues. Precompute a logTable or use 31 - __builtin_clz(len) for exact O(1) integer log2.

Off-by-one in the right interval

Writing R - (1 << k) instead of R - (1 << k) + 1.

Crucial Edge Cases to Validate:

  • L == R (Single element query) — Range length is 1; k = 0; returns arr[L].
  • Query covers entire array [0, N - 1] — Returns global minimum.
  • Array has duplicate minimum values — Handled correctly.
  • Large N = 10^5, Q = 10^6 — Sparse table answers 106 queries in ~25ms.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Highlight the concept of idempotence: explain why min and gcd allow overlapping O(1) intervals while sum requires disjoint decomposition.
  2. Compare Sparse Table (O(1) query, static) with Segment Tree (O(log N) query, dynamic with updates).
  3. Mention RMQ to LCA (Lowest Common Ancestor) reduction: LCA on trees can be transformed into RMQ on an Euler tour in O(1) time.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What data structure answers static Range Minimum Queries in O(1) time after O(N log N) precomputation?

2.How does the Sparse Table answer query(L, R) in O(1) time using overlapping intervals?

3.Why cannot a Sparse Table answer Range Sum Queries in O(1) time with overlapping intervals?

Back to DSA Sheet