Query Kth Smallest Trimmed Number

Medium

Asked by:

9 views

Topics:

ArraysStrings

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. 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 i^th 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 2^nd smallest number is 251 at index 2.
3. Trimmed to the last 2 digits, nums = ["02","73","51","14"]. The 4^th 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 2^nd 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 2^nd 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 <= k_i <= nums.length
1 <= trim_i <= nums[i].length

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the length of the `nums` array and the `queries` array, and the maximum length of each string in `nums` and the values of `k` and `trim` in `queries`?
Are the strings in `nums` guaranteed to be valid representations of non-negative integers, and can they have leading zeros?
If for a specific query [k, trim], after trimming there are duplicate numbers, how should the k-th smallest be determined in terms of original index?
Is `k` guaranteed to be a valid value within the range of the number of trimmed numbers (i.e., is `k` always less than or equal to the number of elements in `nums`)?
What should I return if `nums` is empty or `queries` is empty?

Brute Force Solution

Approach

To find the Kth smallest trimmed number, we will consider each query one at a time. For each query, we'll trim all the numbers as requested, and then sort the trimmed numbers along with their original positions to identify the Kth smallest.

Here's how the algorithm would work step-by-step:

For each query we receive, create a working copy of the list of numbers.
For each number in the working copy, trim the required number of digits from the right side.
Remember the original position of each trimmed number in the original list.
Now, sort the trimmed numbers from smallest to largest, keeping track of their original positions. If two trimmed numbers are the same, sort them by their original positions.
After sorting, identify the number that is in the Kth position. K is given in the query.
The original position associated with that Kth number is the answer to the query.
Repeat this process for each query.

Code Implementation

def solve_queries(numbers, queries):
    results = []

    for query in queries:
        kth_smallest = query[0]
        trim_amount = query[1]

        trimmed_numbers_with_indices = []

        # Create a working copy and trim each number
        for original_index, number in enumerate(numbers):
            number_string = str(number)

            # Trim the number from the right
            if trim_amount >= len(number_string):
                trimmed_number = ""
            else:
                trimmed_number = number_string[len(number_string) - trim_amount:]

            trimmed_numbers_with_indices.append((trimmed_number, original_index))

        # Sort the trimmed numbers based on value and original index
        trimmed_numbers_with_indices.sort(key=lambda x: (x[0], x[1]))

        # The index in numbers to return is at kth_smallest - 1 in sorted list
        results.append(trimmed_numbers_with_indices[kth_smallest - 1][1])

    return results

Big(O) Analysis

Time Complexity

O(queries * n log n) – The solution iterates through each query in the queries array. For each query, it trims n numbers, which takes O(n) time. Then, it sorts these n trimmed numbers, which takes O(n log n) time using an efficient sorting algorithm. Since this sorting process is repeated for each query, and the trimming is included in the sorting, the overall time complexity is O(queries * n log n), where queries is the number of queries and n is the number of elements in the input array nums.

Space Complexity

O(N) – For each query, the algorithm creates a working copy of the input list of numbers, which has size N. Additionally, when sorting the trimmed numbers along with their original positions, another data structure (like a list of tuples) of size N is used to store this information. Therefore, the auxiliary space required is proportional to the number of input numbers. The sorting algorithm itself might use some extra space, but that would be dominated by storing trimmed numbers and indices.

Optimal Solution

Approach

To efficiently find the kth smallest trimmed number, we'll cleverly use sorting. We'll focus on just the part of the numbers we care about, and then sort based on those trimmed values, keeping track of the original order of the numbers.

Here's how the algorithm would work step-by-step:

For each query, extract the last 'trim' digits from each number.
Combine each trimmed number with its original position or index in the initial list.
Sort the trimmed numbers. When trimmed numbers are identical, sort by their original positions to maintain initial order.
Find the number at the kth position in the sorted list of trimmed numbers.
The original position/index of that number is the answer to the query.

Code Implementation

def query_kth_smallest_trimmed_number(numbers, queries):
    result = []
    for kth_smallest, trim in queries:
        trimmed_numbers_with_index = []
        for index, number in enumerate(numbers):
            trimmed_numbers_with_index.append((number[-trim:].zfill(trim), index))

        # Sort the trimmed numbers and keep track of their original index.
        trimmed_numbers_with_index.sort()

        # The index is the answer.
        result.append(numbers.index(numbers[trimmed_numbers_with_index[kth_smallest - 1][1]])) 

    return result

Big(O) Analysis

Time Complexity

O(m * (n log n)) – For each of the m queries, we iterate through the n numbers to extract the trimmed substring. This takes O(m*n) time. Then, we sort the trimmed numbers along with their original indices. Sorting n elements takes O(n log n) time. Since we do this for each of the m queries, the total time complexity for the sorting part is O(m * n log n). Combining the extraction and sorting time gives O(m*n + m*n log n). Since n log n grows faster than n, the overall time complexity is O(m * (n log n)).

Space Complexity

O(N) – For each query, a list of trimmed numbers paired with their original indices is created, which has a size proportional to the number of numbers in the input, N. This list is then sorted in place or copied for sorting, but either way, auxiliary space of O(N) is used to store the trimmed number/index pairs. Therefore, the auxiliary space complexity is O(N), where N is the number of input numbers.

Edge Cases

Case	How to Handle
Empty nums array	Return an empty array since there are no numbers to process and thus no kth smallest trimmed number can be found.
Empty queries array	Return an empty array since there are no queries to process.
trim is 0	Trimming to 0 digits means an empty string, handle lexicographical comparisons correctly based on implementation (likely treat as smallest).
trim is larger than the length of some strings in nums	The trimmed string should be the entire string in `nums` if trim is larger than length of any element.
k is larger than the size of nums	This is invalid input, return an error or appropriate default value, e.g., an empty list or raise an exception as required by the problem statement.
nums contains strings of varying lengths	The trimming process must handle strings of different lengths without causing errors when applying trim.
Large nums array and large trim values leading to potential integer overflow in sorting or indexing	Use appropriate data types (e.g., long) to prevent integer overflow during sorting or indexing operations.
k is 1 (finding the minimum)	Ensure the algorithm correctly identifies the minimum element after trimming.

Empty nums array

How to Handle:

Return an empty array since there are no numbers to process and thus no kth smallest trimmed number can be found.

Empty queries array

How to Handle:

Return an empty array since there are no queries to process.

trim is 0

How to Handle:

Trimming to 0 digits means an empty string, handle lexicographical comparisons correctly based on implementation (likely treat as smallest).

trim is larger than the length of some strings in nums

How to Handle:

The trimmed string should be the entire string in `nums` if trim is larger than length of any element.

k is larger than the size of nums

How to Handle:

This is invalid input, return an error or appropriate default value, e.g., an empty list or raise an exception as required by the problem statement.

nums contains strings of varying lengths

How to Handle:

The trimming process must handle strings of different lengths without causing errors when applying trim.

Large nums array and large trim values leading to potential integer overflow in sorting or indexing

How to Handle:

Use appropriate data types (e.g., long) to prevent integer overflow during sorting or indexing operations.

k is 1 (finding the minimum)

How to Handle:

Ensure the algorithm correctly identifies the minimum element after trimming.