1
# Runtime: 1276 ms (Top 58.39%) | Memory: 15.2 MB (Top 22.81%)
2
from collections import defaultdict
3

4

5
class Solution:
6
    def smallestTrimmedNumbers(
7
        self, nums: List[str], queries: List[List[int]]
8
    ) -> List[int]:
9
        sl = len(nums[0])
10
        len_to_sorted = defaultdict(list)
11
        ans = [0] * len(queries)
12

13
        for i, (k_smallest, trim_len) in enumerate(queries):
14
            if trim_len not in len_to_sorted:
15
                # have to trim
16
                for ni, num in enumerate(nums):
17
                    len_to_sorted[trim_len].append((int(num[sl - trim_len :]), ni))
18

19
                len_to_sorted[trim_len] = sorted(len_to_sorted[trim_len])
20
            ans[i] = len_to_sorted[trim_len][k_smallest - 1][1]
21

22
        return ans