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:
nums to its rightmost trimi digits.kith smallest trimmed number in nums. If two trimmed numbers are equal, the number with the lower index is considered to be smaller.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:
x digits means to keep removing the leftmost digit, until only x digits remain.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 <= 1001 <= nums[i].length <= 100nums[i] consists of only digits.nums[i].length are equal.1 <= queries.length <= 100queries[i].length == 21 <= ki <= nums.length1 <= 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?
The simple approach involves trimming the numbers based on each query and then sorting them to find the k-th smallest element. We will trim each number, pair it with its original index, sort the list of pairs, and select the k-th smallest element by considering the first k elements of the sorted list.
This C solution works by first trimming the numbers based on the given number of digits specified in each query, then sorting the resultant numbers while keeping track of their original positions. We use the qsort function for sorting the trimmed numbers with their original indices, ensuring any ties during sorting are resolved using the original indices.
C++
Java
Python
C#
JavaScript
Time Complexity: O(Q * N * log(N)), where Q is the number of queries, and N is the number of numbers in the input list.
Space Complexity: O(N), which is needed to store the trimmed numbers for comparison and the original indices.
For this approach, we leverage the Radix Sort when nums is restricted by the constraints given the uniformity and limited set size, specifically using the properties of counting sort, given that precision can be limited to 10 digits (0-9). We'll create buckets to sort the numbers efficiently for each trim and query.
In this C example, we use radix sort, which is a non-comparison-based sorting algorithm that groups numbers (or strings) based on digits. The solution applies a counting sort for each digit position, starting from the least significant digit. Although radix sort typically operates efficiently with integer representations, constraints on string lengths allow this adaptation.
C++
Java
Python
C#
JavaScript
Time Complexity: O(D * (N + B)), where D is the maximum number of digits in nums, N is the number of strings, and B is the maximum value within a single bucket.
Space Complexity: O(N), for storing temporary ordering.
| Approach | Complexity |
|---|---|
| Simple Sorting Approach | Time Complexity: O(Q * N * log(N)), where Q is the number of queries, and N is the number of numbers in the input list. |
| Optimized Bucket Sort Method | Time Complexity: O(D * (N + B)), where D is the maximum number of digits in nums, N is the number of strings, and B is the maximum value within a single bucket. |
Kth Largest Element in an Array - Quick Select - Leetcode 215 - Python • NeetCode • 331,616 views views
Watch 9 more video solutions →Practice Query Kth Smallest Trimmed Number with our built-in code editor and test cases.
Practice on FleetCode