2343. Query Kth Smallest Trimmed Number
Problem Description
In this LeetCode problem, we're given an array of strings called nums
, with each string representing a number with leading zeros if required so that all numbers are of the same length. Along with this array, we're given a 2D array of queries. Each query is a pair [k, trim]
. For each query, we need to do the following:
- Trim each number in the
nums
array to keep only the rightmosttrim
digits. This is equivalent to removing digits from the beginning (left side) of the string until we are left withtrim
number of digits. - Find the
k
th smallest number in this trimmed list. If two numbers are the same, the one whose index is smaller in the originalnums
array is considered the smaller one. - After the answer is determined for each individual query, we reset each number in the
nums
array to its original value before proceeding with the next query.
The result is an array of indices indicating the positions of the k
th smallest trimmed numbers in the original nums
array for each query.
Intuition
The given problem can be approached by looking at each query and processing the nums
array based on that query. This involves transforming the original array into a form where it can be sorted, and then picking the k
th smallest element.
Here's the intuitive breakdown of the solution:
- For each query, begin by trimming all the numbers in
nums
. This task involves taking the lasttrim
digits of each number. - After the array is trimmed, each number along with its original index must be kept together so that after sorting, we can refer back to where the number came from. Tuple pairs can be used for this, with the trimmed number first for sorting purposes, followed by the original index.
- We sort the collection of these pairs to arrange the trimmed numbers in ascending order along with their original indices. Sorting in Python is stable, which means that if two elements are equal, their order relative to each other will remain the same as it was in the input.
- Once the array is sorted, we simply pick the element that is at the
k-1
position (due to the 0-indexing) which corresponds to thek
th smallest number along with its index. - This index is added to the result list, which is returned at the end after processing all queries.
Utilizing the sort functionality of Python in this way allows us to address the problem in a straightforward manner.
Learn more about Divide and Conquer, Sorting and Heap (Priority Queue) patterns.
Solution Approach
The implementation follows directly from the intuitive approach that was discussed. Here's a step-by-step walkthrough using the provided Python solution:
-
Initializing an empty list named
ans
to store the indices of thek
th smallest trimmed numbers for each query. -
Looping through each
[k, trim]
pair in thequeries
list:- The key operation in the loop is to create a list of tuples for each number in
nums
. The tuple consists of the trimmed number (v[-trim:]
) and its original index (i
). This is facilitated by Python's list comprehension and slicing features. - For the trimming operation,
v[-trim:]
is used to get the substring ofv
from the-trim
position (counting from the right) to the end. This essentially gives us the rightmosttrim
digits of each number. - Along with the trimmed number, the original index is also stored in the tuple to keep track of its position in the original
nums
array.
- The key operation in the loop is to create a list of tuples for each number in
-
The list of tuples is then sorted. As mentioned earlier, Python's sorting is stable, so if two trimmed numbers are equal, their relative order will remain the same and thus the number from the lower index in the original list will be deemed smaller. The sorting algorithm typically used in Python is Timsort, which is efficient for the kind of partial orderings that appear often in practice.
-
After the list is sorted, the
k-1
indexed tuple in the sorted list gives us thek
th smallest number because Python uses 0-based indexing. From this tuple,[1]
is used to extract the second element, which is the original index of the trimmed number in thenums
array. -
The extracted index is appended to the
ans
list. -
This process is repeated for each query, and the original
nums
array remains unaltered as we only use substrings and do not modify the original array. -
After processing all queries, the
ans
list is returned, containing the indices of thek
th smallest trimmed number for each query.
The solution's time complexity is dominated by the sorting step inside each query loop. If n
is the length of nums
and m
is the length of queries
, the expected time complexity is O(m * n * log(n)), with additional space complexity of O(n) for the list of tuples created during each query.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Suppose nums
is ["102","473","251","814"]
and the queries array is [[2,1],[1,2]]
.
-
For the first query
[2,1]
, trim value is1
. We trim each element innums
to the last digit:102
becomes2
473
becomes3
251
becomes1
814
becomes4
The array of trimmed numbers paired with their indices is[('2', 0), ('3', 1), ('1', 2), ('4', 3)]
.
-
We then sort these pairs to get
[('1', 2), ('2', 0), ('3', 1), ('4', 3)]
. -
The second smallest number after trimming is at index
0
because the pair('2', 0)
is the second element. Thus, for the first query, the result is0
. -
For the next query
[1,2]
, the trim value is2
, so we don't actually trim since allnums
elements are already of length2
or smaller. -
The sorted array of numbers paired with their indices is
[('02', 0), ('14', 3), ('51', 2), ('73', 1)]
. -
The smallest number (after trimming to two digits, which in this case changes nothing) is at index
0
. So, for the second query, the result is0
.
As a result, after processing both queries, we get an answer array of [0, 0]
.
This walkthrough matches the steps provided in the solution approach:
- A list of tuples is created for each number and its index with the numbers trimmed to the correct size.
- The list of tuples is sorted based on the trimmed numbers.
- The index of the
k
th smallest trimmed number is then found and appended to the result list. - This process is repeated for each query without altering the original
nums
array.
Hence the final indices of the k
th smallest trimmed numbers for each query are determined and returned in a list.
Solution Implementation
1from typing import List
2
3class Solution:
4 def smallestTrimmedNumbers(self, numbers: List[str], queries: List[List[int]]) -> List[int]:
5 # Initialize an empty list to store the answer
6 answer = []
7
8 # Iterate through each query in the list of queries
9 for k, trim in queries:
10 # Create a sorted list of tuples where each tuple contains
11 # a trimmed number (last 'trim' characters) and its original index
12 trimmed_sorted_list = sorted((num[-trim:], index) for index, num in enumerate(numbers))
13
14 # From the sorted list, select the k-th smallest trimmed number
15 # (as sorting starts with 0, we use k-1 as the index)
16 # and append its original index to the answer list
17 answer.append(trimmed_sorted_list[k - 1][1])
18
19 # Return the list of original indices of the k-th smallest trimmed numbers
20 return answer
21
1import java.util.Arrays;
2
3class Solution {
4
5 public int[] smallestTrimmedNumbers(String[] nums, int[][] queries) {
6 // Get the number of strings in the nums array and the total number of queries.
7 int numOfStrings = nums.length;
8 int numOfQueries = queries.length;
9
10 // Create an array to store the answers for each query.
11 int[] answers = new int[numOfQueries];
12
13 // Initialize a 2D array to store both the trimmed string and its original index.
14 String[][] trimmedAndIndices = new String[numOfStrings][2];
15
16 // Iterate over each query
17 for (int i = 0; i < numOfQueries; ++i) {
18 // Extract the k-th value and the trim length from the current query.
19 int k = queries[i][0];
20 int trimLength = queries[i][1];
21
22 for (int j = 0; j < numOfStrings; ++j) {
23 // Trim each string in nums from the end by the given trim length and store the result along with the original index.
24 trimmedAndIndices[j] = new String[] {
25 nums[j].substring(nums[j].length() - trimLength),
26 String.valueOf(j)
27 };
28 }
29
30 // Sort the array of trimmed strings and indices.
31 Arrays.sort(trimmedAndIndices, (a, b) -> {
32 // Compare trimmed strings.
33 int comparison = a[0].compareTo(b[0]);
34 // If equal, compare their original indices.
35 return comparison == 0 ? Integer.compare(Integer.parseInt(a[1]), Integer.parseInt(b[1])) : comparison;
36 });
37
38 // Get the index of the k-th smallest trimmed string.
39 answers[i] = Integer.parseInt(trimmedAndIndices[k - 1][1]);
40 }
41
42 // Return the array of answers.
43 return answers;
44 }
45}
46
1#include <vector>
2#include <string>
3#include <algorithm>
4using namespace std;
5
6class Solution {
7public:
8 // Function to return the indices of the smallest trimmed numbers for each query
9 vector<int> smallestTrimmedNumbers(vector<string>& numbers, vector<vector<int>>& queries) {
10 int numOfNumbers = numbers.size(); // Total number of strings in the numbers vector
11 vector<pair<string, int>> trimmedNumbers(numOfNumbers); // Pair to hold trimmed strings and original indices
12 vector<int> answer; // Vector to hold the final results
13
14 // Iterate through each query
15 for (auto& query : queries) {
16 int k = query[0]; // kth smallest number to find after trimming
17 int trimLength = query[1]; // Length of the number to consider after trimming
18
19 // Prepare the trimmed numbers along with their original indices
20 for (int i = 0; i < numOfNumbers; ++i) {
21 // Trim the number keeping the last 'trimLength' digits and store the original index
22 trimmedNumbers[i] = {numbers[i].substr(numbers[i].size() - trimLength), i};
23 }
24
25 // Sort the trimmed numbers, (since we're using pairs, it sorts by the first element (trimmed string), and uses the second element (original index) for tie-breaking)
26 sort(trimmedNumbers.begin(), trimmedNumbers.end());
27
28 // Add the original index of the kth smallest trimmed number to the answer vector
29 answer.push_back(trimmedNumbers[k - 1].second);
30 }
31
32 // Return the final result after processing all queries
33 return answer;
34 }
35};
36
1// In TypeScript, we can simply use arrays and strings, and TypeScript has built-in types for these.
2
3// Function to return the indices of the smallest trimmed numbers for each query
4function smallestTrimmedNumbers(numbers: string[], queries: number[][]): number[] {
5 const numOfNumbers = numbers.length; // Total number of strings in the numbers array
6 const trimmedNumbers: { trimmed: string; originalIndex: number }[] = []; // Array to hold trimmed strings and original indices
7 const answer: number[] = []; // Array to hold the final results
8
9 // Iterate through each query
10 for (const query of queries) {
11 const k = query[0]; // kth smallest number to find after trimming
12 const trimLength = query[1]; // The number of characters to consider from the end of the string after trimming
13
14 // Prepare the trimmed numbers along with their original indices
15 for (let i = 0; i < numOfNumbers; ++i) {
16 // Trim the number, keeping the last 'trimLength' characters, and store along with the original index
17 trimmedNumbers[i] = {
18 trimmed: numbers[i].slice(-trimLength),
19 originalIndex: i
20 };
21 }
22
23 // Sort the trimmed numbers (the array gets sorted by the 'trimmed' property, and uses the 'originalIndex' for tie-breaking)
24 trimmedNumbers.sort((a, b) =>
25 a.trimmed !== b.trimmed
26 ? a.trimmed.localeCompare(b.trimmed)
27 : a.originalIndex - b.originalIndex
28 );
29
30 // Add the original index of the kth smallest trimmed number to the answer array
31 answer.push(trimmedNumbers[k - 1].originalIndex);
32 }
33
34 // Return the final result after processing all queries
35 return answer;
36}
37
Time and Space Complexity
Time Complexity
The time complexity of the solution consists of two main operations:
-
Trimming and sorting the strings: For each query, we trim the strings to the last
trim
characters and sort them. This operation has a complexity ofO(n * m * log(n))
, wheren
is the length ofnums
andm
is the length of the trimmed string. Them
factor comes from the time to create the substring for each number, andlog(n)
is for the sorting. -
The loop runs for each query, adding a factor of the number of queries
q
.
Thus, the total time complexity is O(q * n * m * log(n))
.
Space Complexity
Space complexity pertains to the extra space required by the algorithm. Hereās what it includes:
-
The trimmed and tuples list
t
, which has a sizeO(n)
for each query since we store the trimmed strings and their original indices. -
The answer list
ans
that holds one value for each query, giving it a size ofO(q)
.
Thus, the total space complexity would be O(n + q)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dnd svg Divide and Conquer The main idea of divide and conquer is to split the main problem into two smaller components assuming that each one of the components had already been solved recursively and then try to solve the bigger
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
Want a Structured Path to Master System Design Too? Donāt Miss This!