Log inSign up
hardGeeksforGeeksNot Started

K-th Smallest Number in a Range

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 queries where each query is given as [L, R, k] (0-indexed range, 1-based k), find the k-th smallest number in the subarray nums[L...R].

Return an array containing the answer for each query.

This is a classic range query problem solvable using Persistent Segment Trees (Chairman Tree) in O(log n) per query.

Example 1 · Example 1:

Input: nums = [3, 2, 5, 8, 4, 3, 7, 2, 9], queries = [[1, 4, 2], [0, 4, 3], [2, 6, 1]]
Output: [4, 4, 3]
Explanation: For query [1, 4, 2]: subarray is nums[1..4] = [2, 5, 8, 4]. Sorted: [2, 4, 5, 8]. The 2nd smallest is 4. For query [0, 4, 3]: subarray is nums[0..4] = [3, 2, 5, 8, 4]. Sorted: [2, 3, 4, 5, 8]. The 3rd smallest is 4. For query [2, 6, 1]: subarray is nums[2..6] = [5, 8, 4, 3, 7]. Sorted: [3, 4, 5, 7, 8]. The 1st smallest is 3.

Example 2 · Example 2:

Input: nums = [10, 20, 30, 40, 50], queries = [[0, 4, 5], [1, 3, 2]]
Output: [50, 30]
Explanation: Subarray [0..4] 5th smallest is 50. Subarray [1..3] = [20, 30, 40], 2nd smallest is 30.

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= queries.length <= 105
  • 0 <= L <= R < nums.length
  • 1 <= k <= R - L + 1
  • -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 K-th Smallest Number in a Range.
  • 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:

  • K-th Smallest Number in a Range
  • Advanced Data Structures & Algorithmic Paradigm
  • Fast Range Queries or Amortized Dynamic Operations

Algorithmic Decision Tree:

  • BRUTE_FORCE: When total number of queries is very small (Q <= 50).
  • BETTER: When Persistent Segment Trees are difficult to allocate due to memory or language limitations.
  • OPTIMAL: The theoretical and practical optimal gold standard for Range K-th Smallest queries.

Connected Patterns:

Segment TreeFenwick TreeDisjoint Set UnionDesign Data Structures

1. Subarray Copy and QuickSelect / Sorting

Intuition

For every incoming query: 1. Slice the subarray nums[L..R]. 2. Sort the slice or use QuickSelect (nth_element) to locate the k-th smallest element. 3. Append to output. For Q queries each covering up to N elements, overall runtime is O(Q \cdot (R - L + 1) log (R - L + 1)), leading to TLE for large inputs.

When to apply: When total number of queries is very small (Q <= 50).

Algorithm

  1. Step 1: Iterate through each query [L, R, k].
  2. Step 2: Copy nums[L..R] into a temporary vector.
  3. Step 3: Sort the temporary vector in ascending order.
  4. Step 4: Record element at index k - 1 into results.
  5. Step 5: Return all query results.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5std::vector<int> solveBruteForce(const std::vector<int>& nums, const std::vector<std::vector<int>>& queries) {
6 std::vector<int> res;
7 res.reserve(queries.size());
8 for (const auto& q : queries) {
9 int l = q[0], r = q[1], k = q[2];
10 std::vector<int> sub(nums.begin() + l, nums.begin() + r + 1);
11 std::sort(sub.begin(), sub.end());
12 res.push_back(sub[k - 1]);
13 }
14 return res;
15}
16
17int main() {
18 std::vector<int> nums = {3, 2, 5, 8, 4, 3, 7, 2, 9};
19 std::vector<std::vector<int>> queries = {{1, 4, 2}, {0, 4, 3}, {2, 6, 1}};
20 auto ans = solveBruteForce(nums, queries);
21 for (int x : ans) std::cout << x << " ";
22 std::cout << std::endl;
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(Q * M log M) where M is average range length (R - L + 1)
  • Space complexity: O(M) temporary storage per query

2. Merge Sort Tree + Binary Search on Answer

Intuition

Construct a Segment Tree where node [L, R] stores all elements in subarray nums[L..R] sorted in ascending order (built in O(n log n) time). To answer query [L, R, k]: 1. Binary search the value X over the range [min(\text{nums}), max(\text{nums})]. 2. For each midpoint X, query the segment tree for the number of elements in range [L, R] that are <= X. At each relevant segment tree node, use std::upper_bound in O(log n). 3. Because the tree traversal visits O(log n) nodes, counting takes O(log2 n). 4. Combined with binary search over values, answering one query takes O(log(\text{range}) \cdot log2 n).

When to apply: When Persistent Segment Trees are difficult to allocate due to memory or language limitations.

Algorithm

  1. Step 1: Build Merge Sort Tree where each node contains sorted elements of its segment.
  2. Step 2: For query [L, R, k], binary search answer in [minVal, maxVal].
  3. Step 3: Mid value is tested by querying count of items <= mid in range [L, R].
  4. Step 4: If count >= k, shrink upper bound; else expand lower bound.
  5. Step 5: Return binary searched value.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5struct MergeSortTree {
6 int n;
7 std::vector<std::vector<int>> tree;
8 MergeSortTree(const std::vector<int>& arr) : n(arr.size()), tree(4 * arr.size()) {
9 build(1, 0, n - 1, arr);
10 }
11
12 void build(int node, int start, int end, const std::vector<int>& arr) {
13 if (start == end) {
14 tree[node] = {arr[start]};
15 return;
16 }
17 int mid = (start + end) / 2;
18 build(2 * node, start, mid, arr);
19 build(2 * node + 1, mid + 1, end, arr);
20 std::merge(tree[2 * node].begin(), tree[2 * node].end(),
21 tree[2 * node + 1].begin(), tree[2 * node + 1].end(),
22 std::back_inserter(tree[node]));
23 }
24
25 int countLE(int node, int start, int end, int l, int r, int x) {
26 if (r < start || end < l) return 0;
27 if (l <= start && end <= r) {
28 return std::upper_bound(tree[node].begin(), tree[node].end(), x) - tree[node].begin();
29 }
30 int mid = (start + end) / 2;
31 return countLE(2 * node, start, mid, l, r, x) + countLE(2 * node + 1, mid + 1, end, l, r, x);
32 }
33};
34
35std::vector<int> solveMergeSortTree(const std::vector<int>& nums, const std::vector<std::vector<int>>& queries) {
36 MergeSortTree mst(nums);
37 std::vector<int> sortedVals = nums;
38 std::sort(sortedVals.begin(), sortedVals.end());
39 sortedVals.erase(std::unique(sortedVals.begin(), sortedVals.end()), sortedVals.end());
40
41 std::vector<int> ans;
42 ans.reserve(queries.size());
43
44 for (const auto& q : queries) {
45 int l = q[0], r = q[1], k = q[2];
46 int low = 0, high = (int)sortedVals.size() - 1;
47 int best = sortedVals[high];
48
49 while (low <= high) {
50 int mid = low + (high - low) / 2;
51 int val = sortedVals[mid];
52 if (mst.countLE(1, 0, (int)nums.size() - 1, l, r, val) >= k) {
53 best = val;
54 high = mid - 1;
55 } else {
56 low = mid + 1;
57 }
58 }
59 ans.push_back(best);
60 }
61 return ans;
62}
63
64int main() {
65 std::vector<int> nums = {3, 2, 5, 8, 4, 3, 7, 2, 9};
66 std::vector<std::vector<int>> queries = {{1, 4, 2}, {0, 4, 3}, {2, 6, 1}};
67 auto ans = solveMergeSortTree(nums, queries);
68 for (int x : ans) std::cout << x << " ";
69 std::cout << std::endl;
70 return 0;
71}

Time & Space Complexity

  • Time complexity: O(n log n + Q * log(range) * log^2 n) time
  • Space complexity: O(n log n) auxiliary space for the Merge Sort Tree

3. Persistent Segment Tree (Chairman Tree)

Intuition

The state-of-the-art optimal algorithm for static range k-th smallest queries is the Persistent Segment Tree (Chairman Tree): 1. Coordinate Compression: Map unique elements of nums to ranks 1 \dots M, storing the mapping so we can retrieve the original value in O(1). 2. Persistence Over Prefixes: - Version 0: empty segment tree over range [1, M]. - Version i: insert element \text{rank}(nums[i]) into version i - 1. - Persistence creates at most \lceil \log_2 M \rceil new nodes per version, sharing all unaffected nodes. 3. Querying Range [L, R]: - The state of the range [L, R] is the difference between root R and root L - 1: $\Delta(\text{node}) = \text{root}_R.\text{left}.count - \text{root}_{L-1}.\text{left}.count - If \Delta(\text{left}) >= k, the k-th smallest element lies in the left child. Recurse left! - Otherwise, the k-th smallest element lies in the right child. Recurse right with k - \Delta(\text{left})! 4. Direct tree descent finds the exact value in strictly O(log n) steps. 5. Overall runtime is O((n + q) log n) with O(n log n)$ space.

When to apply: The theoretical and practical optimal gold standard for Range K-th Smallest queries.

Algorithm

  1. Step 1: Coordinate compress nums: sort unique values and map to ranks 1..M.
  2. Step 2: Define Node with count, leftChild, rightChild. Base root = buildEmpty(1, M).
  3. Step 3: For i = 0 to n - 1, root[i + 1] = insert(root[i], 1, M, rank(nums[i])).
  4. Step 4: For query [L, R, k], query(root[L], root[R + 1], 1, M, k).
  5. Step 5: If leftCount >= k, traverse left child; else traverse right child with k - leftCount.
  6. Step 6: Map resulting leaf rank back to original integer and return answer.

Interactive trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Unique values in nums = [2, 3, 4, 5, 7, 8, 9] (7 distinct values)
Visual state
Values and pointers at this exact step
pointers
S
2
3
4
5
7
8
9
0
1
2
3
4
5
6
Check / comparison
Initial root[0] built with 0 counts
Decision / next transition
m = 7 distinct ranks
Why this step matters

Unique values in nums = [2, 3, 4, 5, 7, 8, 9] (7 distinct values). Build version 0 (empty).

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5struct Node {
6 int count;
7 int left, right;
8};
9
10class PersistentSegTree {
11 int n, m;
12 std::vector<Node> tree;
13 std::vector<int> roots;
14
15 int buildEmpty(int l, int r) {
16 int id = tree.size();
17 tree.push_back({0, 0, 0});
18 if (l == r) return id;
19 int mid = (l + r) / 2;
20 int leftChild = buildEmpty(l, mid);
21 int rightChild = buildEmpty(mid + 1, r);
22 tree[id].left = leftChild;
23 tree[id].right = rightChild;
24 return id;
25 }
26
27 int insert(int prevId, int l, int r, int val) {
28 int id = tree.size();
29 tree.push_back(tree[prevId]);
30 tree[id].count++;
31 if (l == r) return id;
32 int mid = (l + r) / 2;
33 if (val <= mid) {
34 tree[id].left = insert(tree[prevId].left, l, mid, val);
35 } else {
36 tree[id].right = insert(tree[prevId].right, mid + 1, r, val);
37 }
38 return id;
39 }
40
41public:
42 std::vector<int> sortedVals;
43
44 PersistentSegTree(const std::vector<int>& arr) {
45 n = arr.size();
46 sortedVals = arr;
47 std::sort(sortedVals.begin(), sortedVals.end());
48 sortedVals.erase(std::unique(sortedVals.begin(), sortedVals.end()), sortedVals.end());
49 m = sortedVals.size();
50
51 tree.reserve(n * 20);
52 roots.resize(n + 1);
53 roots[0] = buildEmpty(1, m);
54
55 for (int i = 0; i < n; ++i) {
56 int rk = std::lower_bound(sortedVals.begin(), sortedVals.end(), arr[i]) - sortedVals.begin() + 1;
57 roots[i + 1] = insert(roots[i], 1, m, rk);
58 }
59 }
60
61 int queryKth(int leftRoot, int rightRoot, int l, int r, int k) {
62 if (l == r) return sortedVals[l - 1];
63 int countLeft = tree[tree[rightRoot].left].count - tree[tree[leftRoot].left].count;
64 int mid = (l + r) / 2;
65 if (countLeft >= k) {
66 return queryKth(tree[leftRoot].left, tree[rightRoot].left, l, mid, k);
67 } else {
68 return queryKth(tree[leftRoot].right, tree[rightRoot].right, mid + 1, r, k - countLeft);
69 }
70 }
71
72 int query(int l, int r, int k) {
73 return queryKth(roots[l], roots[r + 1], 1, m, k);
74 }
75};
76
77std::vector<int> solvePersistent(const std::vector<int>& nums, const std::vector<std::vector<int>>& queries) {
78 PersistentSegTree pst(nums);
79 std::vector<int> ans;
80 ans.reserve(queries.size());
81 for (const auto& q : queries) {
82 ans.push_back(pst.query(q[0], q[1], q[2]));
83 }
84 return ans;
85}
86
87int main() {
88 std::vector<int> nums = {3, 2, 5, 8, 4, 3, 7, 2, 9};
89 std::vector<std::vector<int>> queries = {{1, 4, 2}, {0, 4, 3}, {2, 6, 1}};
90 auto ans = solvePersistent(nums, queries);
91 for (int x : ans) std::cout << x << " ";
92 std::cout << std::endl;
93 return 0;
94}

Time & Space Complexity

  • Time complexity: O((n + q) log n) total time; O(log n) per query
  • Space complexity: O(n log n) auxiliary space for persistent tree nodes

Approach Comparison Matrix

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

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Subarray Copy and QuickSelect / SortingO(Q * M log M) where M is average range length (R - L + 1)O(M) temporary storage per queryFor each query [L, R, k], extract the subarray nums[L..R] and sort it to find the element at index k - 1.O(Q * M log M) where M is average range length (R - L + 1)
2.Merge Sort Tree + Binary Search on AnswerO(n log n + Q * log(range) * log^2 n) timeO(n log n) auxiliary space for the Merge Sort TreeBuild a segment tree where each node stores a sorted vector of elements. For each query, binary search the value in [min, max] and count elements <= mid in O(log3 n).O(n log n + Q * log(range) * log2 n) time
3.Persistent Segment Tree (Chairman Tree)OptimalO((n + q) log n) total time; O(log n) per queryO(n log n) auxiliary space for persistent tree nodesBuild a Persistent Segment Tree where version i stores frequency of prefix nums[0..i]. Range [L, R] is obtained by (version R - version L-1), answering queries in O(log n).O((n + q) log n) total time; O(log n) per query

Common Pitfalls & Crucial Edge Cases

Cloning the entire segment tree on each version

Takes O(N2) memory and exceeds memory limits. Only clone the O(log N) nodes on the path from root to leaf.

Forgetting version 0

Version 0 is the empty tree; query [L, R] subtracts roots[L - 1] from roots[R] (or roots[L] for 1-based indexing).

Unsorted value mapping

Coordinate compression must preserve strictly ascending order so ranks correspond to actual relative values.

Crucial Edge Cases to Validate:

  • k = 1 (Range minimum) — Returns the smallest number in [L, R].
  • k = R - L + 1 (Range maximum) — Returns the largest number in [L, R].
  • Subarray contains duplicate values — Handled cleanly by node frequency counts.
  • Negative numbers — Handled via coordinate compression of values.

Interview Tips & Best Practices

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

  1. Draw the path copying diagram for persistent trees: show how version i shares the untouched branches of version i - 1.
  2. Mention that this is known as the 'Chairman Tree' in competitive programming literature.
  3. Explain the fallback alternative: Merge Sort Tree + Binary Search on answer in O(log3 N) time.

Quick Comprehension Check

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

1.What advanced data structure answers K-th smallest queries on an arbitrary subarray [L, R] in O(log N) time?

2.How does walking down the Persistent Segment Tree find the K-th smallest element?

3.What is the time complexity to build a Persistent Segment Tree over N elements?

Back to DSA Sheet