# Query Kth Smallest Trimmed Number
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/query-kth-smallest-trimmed-number)
Canonical: https://scaleengineer.com/dsa/problems/query-kth-smallest-trimmed-number
**Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer), [Sorting](https://scaleengineer.com/algorithms/sorting), [Radix Sort](https://scaleengineer.com/algorithms/radix-sort), [Quickselect](https://scaleengineer.com/algorithms/quickselect)
**Data structures:** Array, String, Heap (Priority Queue)
**Companies:** [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## Problem
You are given a **0-indexed** array of strings `nums`, where each string is of **equal length** and consists of only digits.

You are also given a **0-indexed** 2D integer array `queries` where `queries[i] = [ki, trimi]`. For each `queries[i]`, you need to:

* **Trim** each number in `nums` to its **rightmost** `trimi` digits.
* Determine the **index** of the `kith` smallest trimmed number in `nums`. If two trimmed numbers are equal, the number with the **lower** index is considered to be smaller.
* Reset each number in `nums` to its original length.

Return _an array_ `answer` _of the same length as_ `queries`, _where_ `answer[i]` _is the answer to the_ `ith` _query._

**Note**:

* To trim to the rightmost `x` digits means to keep removing the leftmost digit, until only `x` digits remain.
* Strings in `nums` may contain leading zeros.

**Example 1:**

**Input:** nums = ["102","473","251","814"], queries = [[1,1],[2,3],[4,2],[1,2]]
**Output:** [2,2,1,0]
**Explanation:**
1. After trimming to the last digit, nums = ["2","3","1","4"]. The smallest number is 1 at index 2.
2. Trimmed to the last 3 digits, nums is unchanged. The 2nd smallest number is 251 at index 2.
3. Trimmed to the last 2 digits, nums = ["02","73","51","14"]. The 4th smallest number is 73.
4. Trimmed to the last 2 digits, the smallest number is 2 at index 0.
   Note that the trimmed number "02" is evaluated as 2.

**Example 2:**

**Input:** nums = ["24","37","96","04"], queries = [[2,1],[2,2]]
**Output:** [3,0]
**Explanation:**
1. Trimmed to the last digit, nums = ["4","7","6","4"]. The 2nd smallest number is 4 at index 3.
   There are two occurrences of 4, but the one at index 0 is considered smaller than the one at index 3.
2. Trimmed to the last 2 digits, nums is unchanged. The 2nd smallest number is 24.

**Constraints:**

* `1 <= nums.length <= 100`
* `1 <= nums[i].length <= 100`
* `nums[i]` consists of only digits.
* All `nums[i].length` are **equal**.
* `1 <= queries.length <= 100`
* `queries[i].length == 2`
* `1 <= ki <= nums.length`
* `1 <= trimi <= nums[i].length`

**Follow up:** Could you use the **Radix Sort Algorithm** to solve this problem? What will be the complexity of that solution?

# Approaches
## Brute-Force Simulation per Query
This approach directly simulates the process described in the problem for each query. For every query `[k, trim]`, it creates a list of trimmed numbers along with their original indices, sorts this list based on the specified criteria, and then picks the k-th element to find its original index.
**Time:** O(Q * N * log(N) * M). Let `Q` be the number of queries, `N` be the number of strings, and `M` be the length of each string. For each of the `Q` queries, we iterate through `N` strings, and the `substring` operation takes O(M). This takes `O(N*M)`. Then, we sort `N` items. Comparing two trimmed strings of length `M` takes `O(M)`. Thus, sorting takes `O(N * log(N) * M)`. The total time per query is `O(N*M + N*log(N)*M)`, which simplifies to `O(N * log(N) * M)`. · **Space:** O(N * M). For each query, a temporary list is created to hold `N` pairs. Each pair contains a string of length `trim` (up to `M`) and an integer index. This list dominates the space usage.
**Pros:** Simple to understand and implement as it directly translates the problem statement into code.; Low space complexity if the temporary list is cleared after each query.
**Cons:** Inefficient due to repeated computations. The process of trimming and sorting is performed from scratch for every single query.; The time complexity is high, which might be too slow for larger constraints, although it passes for the given constraints.
### Explanation
The algorithm iterates through each of the `Q` queries. For a given query `[k, trim]`, it first creates an auxiliary list. This list is populated with pairs, each containing a trimmed string and its original index from the `nums` array. To get the trimmed string, we take the substring of the last `trim` characters from each number in `nums`. After populating the list with all `N` pairs, we sort it. The sorting logic is crucial: it first compares the trimmed string values lexicographically. If the strings are identical, it uses the original index as a tie-breaker, with the smaller index being considered smaller. Once the list is sorted, the `k`-th smallest element is at index `k-1`. We retrieve the original index from this element and record it as the answer for the current query. This entire process is repeated for all queries.
### Algorithm
- Initialize an `ans` array of the same size as `queries`.
- Iterate through each query `[k, trim]` in the `queries` array.
- For each query:
  - Create a temporary list of pairs, where each pair will store a `(trimmed_string, original_index)`.
  - Iterate through the `nums` array. For each string `nums[j]`, extract its rightmost `trim` characters.
  - Add the pair of the trimmed string and its original index `j` to the temporary list.
  - Sort this temporary list. The custom sorting logic should first compare the trimmed strings. If they are equal, it should then compare their original indices to handle the tie-breaker rule.
  - After sorting, the `k`-th smallest element is located at index `k-1`.
  - Retrieve the original index from this pair and store it in the `ans` array at the position corresponding to the current query.
- Return the `ans` array.

## Pre-computation using Radix Sort
This highly efficient approach avoids re-computation for each query by pre-calculating the sorted order of numbers for all possible trim lengths. It leverages the principles of Radix Sort, which is perfectly suited for this problem's structure of sorting based on rightmost digits. After a one-time pre-computation, any query can be answered in constant time.
**Time:** O(M * N + Q). The pre-computation phase consists of `M` passes of Counting Sort, each taking `O(N)` time (since the range of digits is a small constant). This results in `O(M * N)`. The query processing phase involves `Q` constant-time lookups, for a total of `O(Q)`. The overall complexity is dominated by the pre-computation. · **Space:** O(M * N). We need to store the sorted indices for each of the `M` possible trim lengths. Each stored array has `N` indices. The Counting Sort subroutine also requires `O(N)` auxiliary space.
**Pros:** Extremely fast, especially for a large number of queries, as it answers each query in constant time after the initial setup.; Represents the optimal solution for this problem, as suggested by the follow-up question.
**Cons:** Higher space complexity due to storing pre-computed results for all possible trim lengths.; The implementation is more complex than the brute-force approach, requiring knowledge of stable sorting algorithms like Counting Sort for optimal performance.
### Explanation
The core idea is that sorting by the last `d` digits can be achieved by stably sorting by the `d`-th digit from the right, building upon the sort order from the last `d-1` digits. This is the fundamental principle of Least Significant Digit (LSD) Radix Sort.

The algorithm first initializes an array `p` with the original indices `[0, 1, ..., N-1]`. It then iterates from `d = 1` to `M` (the length of the strings), where `d` represents the trim length. In each iteration, it performs one pass of Radix Sort by sorting the `p` array based on the `d`-th digit from the right. This sort must be **stable** to preserve the relative order of elements with equal digits, which is crucial for the correctness of Radix Sort. Using Counting Sort as the stable sorting subroutine is ideal, as the keys are single digits (0-9), achieving a linear time complexity `O(N)` for each pass. After each pass `d`, the now-sorted `p` array is stored. 

After this pre-computation phase, all queries can be answered quickly. For each query `[k, trim]`, we simply look up the pre-computed sorted index array for `trim` and take the element at index `k-1`.
### Algorithm
- Let `N = nums.length` and `M = nums[0].length()`.
- Create a map `precomputed` to store sorted indices for each trim length.
- Initialize an array `p` of size `N` with indices `[0, 1, ..., N-1]`.
- Iterate `d` from `1` to `M` (representing `trim = d`):
  - Let `digitIndex = M - d`.
  - Sort the array `p` stably based on the character at `nums[index].charAt(digitIndex)` for each `index` in `p`. This is one pass of Radix Sort.
  - For optimal `O(N)` performance per pass, use Counting Sort as the stable sorting algorithm.
  - After sorting, store a copy of the `p` array in the `precomputed` map with `d` as the key.
- Initialize an `ans` array of size `queries.length`.
- Iterate through the `queries` array. For each query `[k, trim]`:
  - Retrieve the sorted indices from `precomputed.get(trim)`.
  - The answer is the index at position `k-1` in the retrieved array.
- Return the `ans` array.

# Solutions
### Java

```java
class Solution {
public
  int[] smallestTrimmedNumbers(String[] nums, int[][] queries) {
    int n = nums.length;
    int m = queries.length;
    int[] ans = new int[m];
    String[][] t = new String[n][2];
    for (int i = 0; i < m; ++i) {
      int k = queries[i][0], trim = queries[i][1];
      for (int j = 0; j < n; ++j) {
        t[j] = new String[]{nums[j].substring(nums[j].length() - trim),
                            String.valueOf(j)};
      }
      Arrays.sort(
          t, (a, b)->{
            int x = a[0].compareTo(b[0]);
            return x == 0 ? Long.compare(Integer.valueOf(a[1]),
                                         Integer.valueOf(b[1]))
                          : x;
          });
      ans[i] = Integer.valueOf(t[k - 1][1]);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> smallestTrimmedNumbers(vector<string> &nums,
                                     vector<vector<int>> &queries) {
    int n = nums.size();
    vector<pair<string, int>> t(n);
    vector<int> ans;
    for (auto &q : queries) {
      int k = q[0], trim = q[1];
      for (int j = 0; j < n; ++j) {
        t[j] = {nums[j].substr(nums[j].size() - trim), j};
      }
      sort(t.begin(), t.end());
      ans.push_back(t[k - 1].second);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]: ans = [] for k, trim in queries: t = sorted((v[- trim:], i) for i, v in enumerate(nums)) ans . append(t[k - 1][1]) return ans

```