Query Kth Smallest Trimmed Number

Problem

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 nums to its rightmost trimi digits.
• Determine the index of the kith smallest trimmed number in nums. If two trimmed numbers are equal, the number with the lower index is considered to be smaller.
• Reset each number in nums to its original length.

Return an arrayanswer of the same length asqueries,whereanswer[i]is the answer to theith query.

Note :

• To trim to the rightmost x digits means to keep removing the leftmost digit, until only x digits remain.
• Strings in nums may contain leading zeros.

Examples

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.

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

Follow up: Could you use the Radix Sort Algorithm to solve this problem? What will be the complexity of that solution?

Solution

Method 1 – Sort by Trimmed Value

Intuition

For each query, we can trim all numbers, pair them with their original indices, sort, and pick the k-th smallest. Since the constraints are small, this is efficient enough.

Approach

1. For each query [k, trim], trim each number in nums to its rightmost trim digits.
2. Pair each trimmed number with its original index.
3. Sort the pairs by trimmed value (as string), breaking ties by index.
4. The answer is the index of the k-th smallest trimmed number.

Code

C++

class Solution {
public:
    vector<int> smallestTrimmedNumbers(vector<string>& nums, vector<vector<int>>& queries) {
        vector<int> ans;
        for (auto& q : queries) {
            int k = q[0], trim = q[1], n = nums.size();
            vector<pair<string, int>> arr;
            for (int i = 0; i < n; ++i) {
                arr.emplace_back(nums[i].substr(nums[i].size() - trim), i);
            }
            sort(arr.begin(), arr.end());
            ans.push_back(arr[k-1].second);
        }
        return ans;
    }
};

Go

func smallestTrimmedNumbers(nums []string, queries [][]int) []int {
    ans := make([]int, len(queries))
    for qi, q := range queries {
        k, trim := q[0], q[1]
        arr := make([]struct{ s string; i int }, len(nums))
        for i, num := range nums {
            arr[i] = struct{ s string; i int }{num[len(num)-trim:], i}
        }
        sort.Slice(arr, func(i, j int) bool {
            if arr[i].s == arr[j].s {
                return arr[i].i < arr[j].i
            }
            return arr[i].s < arr[j].s
        })
        ans[qi] = arr[k-1].i
    }
    return ans
}

Java

class Solution {
    public int[] smallestTrimmedNumbers(String[] nums, int[][] queries) {
        int[] ans = new int[queries.length];
        for (int q = 0; q < queries.length; ++q) {
            int k = queries[q][0], trim = queries[q][1];
            int n = nums.length;
            String[][] arr = new String[n][2];
            for (int i = 0; i < n; ++i) {
                arr[i][0] = nums[i].substring(nums[i].length() - trim);
                arr[i][1] = String.valueOf(i);
            }
            Arrays.sort(arr, (a, b) -> a[0].equals(b[0]) ? Integer.parseInt(a[1]) - Integer.parseInt(b[1]) : a[0].compareTo(b[0]));
            ans[q] = Integer.parseInt(arr[k-1][1]);
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun smallestTrimmedNumbers(nums: Array<String>, queries: Array<IntArray>): IntArray {
        return queries.map { (k, trim) ->
            nums.mapIndexed { i, s -> s.takeLast(trim) to i }
                .sortedWith(compareBy({ it.first }, { it.second }))
                [k-1].second
        }.toIntArray()
    }
}

Python

from typing import List
class Solution:
    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:
        ans = []
        for k, trim in queries:
            arr = [(num[-trim:], i) for i, num in enumerate(nums)]
            arr.sort()
            ans.append(arr[k-1][1])
        return ans

Rust

impl Solution {
    pub fn smallest_trimmed_numbers(nums: Vec<String>, queries: Vec<Vec<i32>>) -> Vec<i32> {
        let mut ans = vec![];
        for q in queries {
            let k = q[0] as usize;
            let trim = q[1] as usize;
            let mut arr: Vec<(String, usize)> = nums.iter().enumerate().map(|(i, s)| (s[s.len()-trim..].to_string(), i)).collect();
            arr.sort();
            ans.push(arr[k-1].1 as i32);
        }
        ans
    }
}

TypeScript

class Solution {
    smallestTrimmedNumbers(nums: string[], queries: number[][]): number[] {
        return queries.map(([k, trim]) => {
            const arr = nums.map((num, i) => [num.slice(-trim), i] as [string, number]);
            arr.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0].localeCompare(b[0]));
            return arr[k-1][1];
        });
    }
}

Complexity

• ⏰ Time complexity: O(Q * N log N * L), where Q is the number of queries, N is the number of numbers, and L is the max length of a number. Each query sorts N strings of length up to L.
• 🧺 Space complexity: O(N), for storing the trimmed numbers per query.