Query Kth Smallest Trimmed Number
Real-world version: Kth Smallest Serial by Its TailThe statement here is our own: the same inputs, outputs and technique.
A batch of serials is given as nums, each a string of digits, and all of them the same length.
Each query queries[j] = [k, trim] asks you to keep only the rightmost trim digits of every serial, then find the k-th smallest of those trimmed serials, counting from 1. Trimmed serials are compared as text, so leading zeros count, and when two are equal the one whose original serial appears earlier in nums is treated as smaller.
Return an array answer where answer[j] is the position in nums of the serial the j-th query picks out. Queries are independent and never change nums.
Examples
Example 1
- Input
- nums = ["102", "473", "251", "814"], queries = [[1, 1], [2, 3], [4, 2], [1, 2]]
- Output
- [2, 2, 1, 0]
Keeping one digit gives "2", "3", "1", "4", whose smallest is at position 2. Keeping three digits leaves the serials whole, and the second smallest of those is at position 2 as well.
Example 2
- Input
- nums = ["119", "219", "319"], queries = [[1, 2], [2, 2], [3, 2]]
- Output
- [0, 1, 2]
Keeping two digits gives "19" for all three serials, so the tie is settled by the order they appear in.
Example 3
- Input
- nums = ["10", "01"], queries = [[1, 2], [2, 2]]
- Output
- [1, 0]
Compared as text, "01" comes before "10", so the first query picks position 1 and the second picks position 0.
Constraints
- 1 <= nums.length <= 100
- 1 <= nums[0].length <= 100
- nums[i] consists of digits only, and every serial has the same length
- 1 <= queries.length <= 100
- queries[j].length == 2
- 1 <= queries[j][0] <= 100
- 1 <= queries[j][1] <= 100
- Every query satisfies k <= nums.length and trim <= nums[0].length
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def kth_by_tail(nums: list[str], queries: list[list[int]]) -> list[int]:public int[] kthByTail(List<String> nums, int[][] queries)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 10 test cases: 10 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's