Query Kth Smallest Trimmed Number
MedPrompt
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
numsto its rightmosttrimidigits. - Determine the index of the
kithsmallest trimmed number innums. If two trimmed numbers are equal, the number with the lower index is considered to be smaller. - Reset each number in
numsto 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
xdigits means to keep removing the leftmost digit, until onlyxdigits remain. - Strings in
numsmay 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 <= 1001 <= nums[i].length <= 100nums[i]consists of only digits.- All
nums[i].lengthare equal. 1 <= queries.length <= 100queries[i].length == 21 <= ki <= nums.length1 <= 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
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize an
ansarray of the same size asqueries. - Iterate through each query
[k, trim]in thequeriesarray. - For each query:
- Create a temporary list of pairs, where each pair will store a
(trimmed_string, original_index). - Iterate through the
numsarray. For each stringnums[j], extract its rightmosttrimcharacters. - Add the pair of the trimmed string and its original index
jto 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 indexk-1. - Retrieve the original index from this pair and store it in the
ansarray at the position corresponding to the current query.
- Create a temporary list of pairs, where each pair will store a
- Return the
ansarray.
Walkthrough
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.
Complexity
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.
Trade-offs
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.
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.
Algorithm
- Let
N = nums.lengthandM = nums[0].length(). - Create a map
precomputedto store sorted indices for each trim length. - Initialize an array
pof sizeNwith indices[0, 1, ..., N-1]. - Iterate
dfrom1toM(representingtrim = d):- Let
digitIndex = M - d. - Sort the array
pstably based on the character atnums[index].charAt(digitIndex)for eachindexinp. 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
parray in theprecomputedmap withdas the key.
- Let
- Initialize an
ansarray of sizequeries.length. - Iterate through the
queriesarray. For each query[k, trim]:- Retrieve the sorted indices from
precomputed.get(trim). - The answer is the index at position
k-1in the retrieved array.
- Retrieve the sorted indices from
- Return the
ansarray.
Walkthrough
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.
Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.