Watch 10 video solutions for Query Kth Smallest Trimmed Number, a medium level problem involving Array, String, Divide and Conquer. This walkthrough by Prakhar Agrawal has 1,131 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
nums to its rightmost trimi digits.kith smallest trimmed number in nums. If two trimmed numbers are equal, the number with the lower index is considered to be smaller.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:
x digits means to keep removing the leftmost digit, until only x digits remain.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 <= 1001 <= nums[i].length <= 100nums[i] consists of only digits.nums[i].length are 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?
Problem Overview: You are given an array of equal-length numeric strings. Each query asks you to trim every number to its last trim digits, then return the index of the k-th smallest trimmed value. If two trimmed numbers are equal, the smaller original index wins. Each query works independently, so the challenge is efficiently comparing many trimmed substrings.
Approach 1: Simple Sorting Approach (O(q · n log n) time, O(n) space)
The direct approach processes every query independently. For a query [k, trim], iterate through the array and extract the last trim digits from each string using substring operations. Store pairs of (trimmed_value, index). Sort this list lexicographically by the trimmed value, and break ties using the index. The answer for the query is the index at position k-1 after sorting.
This method relies on standard sorting and works well when the number of queries or numbers is small. The downside is repeated work: the same trims may be recomputed many times. If there are q queries and n numbers, sorting for each query leads to O(q · n log n) time. Still, the logic is straightforward and easy to implement in any language.
Approach 2: Optimized Bucket Sort Method (Radix Style) (O(m · n) time, O(n) space)
A faster solution observes that trimming always keeps the suffix of the number. Instead of recomputing trims for every query, process digits from right to left using a radix-style technique. Maintain an ordered list of indices representing numbers sorted by their last t digits. For each additional digit position, perform a stable bucket/counting sort based on the next digit to the left.
Because digits range from 0–9, each step distributes indices into 10 buckets, preserving previous order. After processing t digits, the list represents numbers sorted by their last t digits. Store this ordering so queries asking for that trim length can directly access the k-1 position. This technique is essentially a specialized radix sort applied to numeric strings.
The preprocessing runs for at most the number length m, and each pass processes all n numbers, giving O(m · n) time. Query answers become constant time lookups. The idea combines properties of arrays and stable bucket sorting to avoid repeated comparisons.
Recommended for interviews: Start by describing the simple sorting approach. It demonstrates understanding of trimming logic, lexicographic comparison, and tie-breaking with indices. Then explain the radix-style bucket optimization. Interviewers typically expect the optimized idea because it avoids redundant sorting and shows familiarity with digit-based sorting techniques.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simple Sorting | O(q · n log n) | O(n) | Best for quick implementation or when constraints are small |
| Bucket Sort (Radix Style) | O(m · n) | O(n) | Preferred for large inputs or many queries; avoids repeated sorting |