Query Kth Smallest Trimmed Number

Problem Description

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] = [k_i, trim_i]. For each queries[i], you need to trim each number in nums to its rightmost trim_i digits, determine the index of the k_i-th smallest trimmed number in nums, and reset each number in nums to its original length. Return an array answer of the same length as queries, where answer[i] is the answer to the i-th query.

Key Insights

• Each query requires trimming the numbers to their rightmost digits, which involves slicing strings.
• Sorting is needed to find the k-th smallest trimmed number, considering both the trimmed value and the original index for tie-breaking.
• After processing each query, we must ensure the original array remains unchanged for subsequent queries.

Space and Time Complexity

Time Complexity: O(q * n log n), where q is the number of queries and n is the length of nums. Space Complexity: O(n), for storing trimmed numbers and their indices.

Solution

To solve the problem, we will:

1. Iterate through each query and trim the numbers in nums based on the specified trim_i.
2. Use a list of tuples to store the trimmed number along with its original index for sorting.
3. Sort this list by the trimmed number first, and by the original index second.
4. Retrieve the index of the k-th smallest trimmed number from the sorted list.
5. Reset the numbers in nums back to their original values before the next query.

This approach uses sorting to ensure the correct order of trimmed numbers and leverages tuples for maintaining both the trimmed value and the original index.

Code Solutions