#2343
Query Kth Smallest Trimmed Number
specialist · 975 · lc medium +32 · verified · 47.2% accepted · 345 likes · top 32%
Description
You are given a 0-indexed array of equal-length digit strings nums and a 0-indexed 2D integer array queries where queries[i] = [ki, trimi]. For each query i:
- Trim every string in nums to its rightmost trimi digits.
- Find the index of the kith smallest trimmed number (ties broken by lower original index).
- Restore all strings before handling the next query.
Return an array answer where answer[i] is the result of the ith query.
Note:
- Trimming keeps only the rightmost digits.
- Strings in nums may have 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.
Code
1
2
3