LeetCode 2343: Query Kth Smallest Trimmed Number

Problem Description

LeetCode Problem 2343

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:

After trimming to the last digit, nums = [“2”,“3”,“1”,“4”]. The smallest number is 1 at index 2.
Trimmed to the last 3 digits, nums is unchanged. The 2nd smallest number is 251 at index 2.
Trimmed to the last 2 digits, nums = [“02”,“73”,“51”,“14”]. The 4th smallest number is 73.
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:

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.
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?

Difficulty: Medium

Tags: array, string, divide and conquer, sorting, heap (priority queue), radix sort, quickselect

Rating: 42.06%

Solution Approaches

Approach 1: Simple Sorting (Initial Solution)

The first solution uses a straightforward approach:

def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:
    def query(k: int, t: int) -> int:
        trimmed = [(num[-t:], i) for i, num in enumerate(nums)]
        trimmed.sort(key=lambda x:(x[0], x[1]))
        _, i = trimmed[k-1]
        return i

    return [query(k, t) for k, t in queries]

How it works:

1. For each query (k, t):
   • Create pairs of (trimmed_number, original_index)
   • Sort these pairs considering both the trimmed number and original index
   • Return the index at position k-1

Time Complexity: O(Q * N * log N), where Q is number of queries and N is length of nums Space Complexity: O(N) for the trimmed array

Approach 2: Radix Sort Optimization

The optimized solution uses Radix Sort principles to improve efficiency:

def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:
    n = len(nums)
    m = len(nums[0])
    
    # Position mapping for different trim lengths
    pmap = {}  # {trim_length: [sorted_indices]}
    currp = list(range(n))

    for t in range(1, m+1):
        # Counting sort for current digit position
        count = [[] for _ in range(10)]
        
        for idx in currp:
            digit = int(nums[idx][m-t])
            count[digit].append(idx)
        
        # Flatten buckets to get new positions
        newp = []
        for bucket in count:
            newp.extend(bucket)
        
        pmap[t] = newp.copy()
        currp = newp

    return [pmap[trim][k-1] for k, trim in queries]

Key Optimizations:

1. Pre-computation: Instead of processing each query independently, we pre-compute sorted positions for all possible trim lengths.

2. Digit-by-Digit Sorting: We use counting sort (a stable sorting algorithm) for each digit position, moving from right to left.

3. Position Mapping: We maintain a mapping of sorted indices for each trim length, allowing O(1) lookup for queries.

How the Radix Sort Works Here:

1. For each trim length t (1 to m):

   • Process digits right-to-left
   • Use counting sort to maintain stability
   • Store the resulting order in position map

2. For queries:

   • Simply look up the pre-computed position at the required trim length
   • Return the k-1th index from that position array

Complexity Analysis:

• Time Complexity: $O(M * N + Q)$, where:

  • M is the length of each string
  • N is the number of strings
  • Q is the number of queries
  • The first part (M * N) is for pre-computation
  • Q is for processing queries

• Space Complexity: $O(M * N)$ for storing position mappings for each trim length