# Leetcode 2343

class Solution {
    public int[] smallestTrimmedNumbers(String[] nums, int[][] queries) {
        int digits = nums[0].length();
        int n = nums.length;
        
        // Prepare for query answers.
        int[] ans = new int[queries.length];
        Map<Integer, List<Integer>> trimToIndex = new HashMap<>();
        for (int i = 0; i < queries.length; i++) {
            int trim = queries[i][1];
            if (!trimToIndex.containsKey(trim)) {
                trimToIndex.put(trim, new ArrayList<Integer>());
            }
            trimToIndex.get(trim).add(i);
        }
        
        // Prepare for the first pass.
        List<List<Integer>> curBuckets = new ArrayList<>(10);
        List<List<Integer>> nextBuckets = new ArrayList<>(10);
        initList(curBuckets, 1);
        initList(nextBuckets, 10);
        for (int i = 0; i < n; i++) {
            curBuckets.get(0).add(i);
        }
        
        for (int i = 1; i <= digits; i++) {
            for (List<Integer> curBucket : curBuckets) {
                for (int index : curBucket) {
                    String num = nums[index];
                    int d = num.charAt(digits - i) - '0';
                    nextBuckets.get(d).add(index);
                }
            }
            // See if there's any queries asking for this trimming size.
            if (trimToIndex.containsKey(i)) {
                for (int qIndex : trimToIndex.get(i)) {
                    int kth = queries[qIndex][0];
                    ans[qIndex] = findKth(nextBuckets, kth - 1);
                }
            }
            curBuckets = nextBuckets;
            nextBuckets = new ArrayList<>(10);
            initList(nextBuckets, 10);
        }
        return ans;
    }
    
    private void initList(List<List<Integer>> in, int size) {
        for (int i = 0; i < size; i++) {
            in.add(new ArrayList<>());
        }
    }
    
    private int findKth(List<List<Integer>> buckets, int kth) {
        int count = 0;
        for (List<Integer> b : buckets) {
            if (kth < count + b.size()) {
                return b.get(kth - count);
            }
            count += b.size();
        }
        return 0;
    }
}