Query Kth Smallest Trimmed Number
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
ki^thsmallest 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 i^th query.
Note:
- To trim to the rightmost
xdigits means to keep removing the leftmost digit, until onlyxdigits remain. - Strings in
numsmay contain leading zeros.
Follow up: Could you use the Radix Sort Algorithm to solve this problem? What will be the complexity of that solution?
Example 1
Input
nums = ["102","473","251","814"], queries = [[1,1],[2,3],[4,2],[1,2]]Output
[2,2,1,0]After applying each trim and selecting the requested order statistic with index tie-breaking, the answer indices are 2, 2, 1, and 0.
Example 2
Input
nums = ["24","37","96","04"], queries = [[2,1],[2,2]]Output
[3,0]For the first query, the second smallest trimmed value is the 4 at index 3 after tie-breaking by lower index, and for the second query the second smallest full number is at index 0.
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