{x}
blog image

Query Kth Smallest Trimmed Number

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 array answer of the same length as queries, where answer[i] is the answer to the ith 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.

 

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 Explanation: 2343. Query Kth Smallest Trimmed Number

This problem requires finding the k-th smallest trimmed number from a list of strings for multiple queries. Each query specifies the number of trailing digits to keep (trim) and the desired k-th smallest number (k).

Approach: Simulation and Sorting

The most straightforward approach involves simulating the trimming process for each query and then sorting the trimmed numbers to find the k-th smallest. This method prioritizes simplicity and readability.

Algorithm:

  1. Iterate through Queries: For each query [k, trim] in queries:
  2. Trim Numbers: Create a temporary array of pairs, where each pair contains the trimmed version of a number from nums and its original index. The trimming is done using string slicing: nums[i][-trim:] (Python) or nums[i].substring(nums[i].length() - trim) (Java, C++).
  3. Sort Pairs: Sort the pairs lexicographically. If two trimmed numbers are equal, the pair with the smaller original index comes first. This ensures that the ordering is consistent with the problem's requirements. We use a custom comparator function for sorting (Java, C++) or a lambda function (Python, Go).
  4. Retrieve Result: The k-th smallest trimmed number's index is at position k-1 in the sorted array. Append this index to the ans array.
  5. Return Result: Return the ans array containing the indices of the k-th smallest trimmed numbers for all queries.

Time and Space Complexity Analysis

  • Time Complexity: The dominant factor is the sorting step within the loop. Sorting n numbers takes O(n log n) time, where n is the length of nums. Since we do this for each of the m queries, the overall time complexity is O(m * n * log n). Note that string slicing or substring extraction takes O(s) time in the worst case, where 's' is the length of the strings in nums. This adds a factor of s, making the time complexity O(m * n * log n * s). However, in practice, s is often considered a constant or relatively small compared to n and m.
  • Space Complexity: The temporary array t (or equivalent) used to store the trimmed numbers and indices has size O(n). The ans array has size O(m). Therefore, the overall space complexity is O(n + m).

Code Examples

The code examples provided in various languages implement the simulation and sorting approach. They illustrate the algorithm's steps efficiently. The custom comparator functions (or lambda expressions) correctly handle the tie-breaking condition based on original indices.

Alternative Approach: Radix Sort (Follow-up)

The follow-up question suggests using Radix Sort. Radix Sort can sort integers in linear time, O(n), if the number of digits is bounded. Adapting this to strings requires careful consideration of the trimming and comparison aspects, making implementation more involved but potentially improving the time complexity to O(m * n * s) if the number of digits in the trimmed strings is considered a constant or small. However, the constant factors involved in Radix Sort can make it less efficient than comparison-based sorts (like merge sort or quicksort) for smaller input sizes. For this problem, given the constraints, the simple sorting approach with O(m * n log n) is likely faster in practice unless n and m are extremely large.