2343. Query Kth Smallest Trimmed Number

MediumArrayStringDivide and ConquerQuickselectRadix SortSortingHeap (Priority Queue)
Leetcode Link

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:

  1. Trim each number in the nums array to keep only the rightmost trim digits. This is equivalent to removing digits from the beginning (left side) of the string until we are left with trim number of digits.
  2. Find the kth smallest number in this trimmed list. If two numbers are the same, the one whose index is smaller in the original nums array is considered the smaller one.
  3. 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 kth 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 kth smallest element.

Here's the intuitive breakdown of the solution:

  1. For each query, begin by trimming all the numbers in nums. This task involves taking the last trim digits of each number.
  2. 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.
  3. 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.
  4. 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 the kth smallest number along with its index.
  5. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

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:

  1. Initializing an empty list named ans to store the indices of the kth smallest trimmed numbers for each query.

  2. Looping through each [k, trim] pair in the queries 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 of v from the -trim position (counting from the right) to the end. This essentially gives us the rightmost trim 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.

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

  4. After the list is sorted, the k-1 indexed tuple in the sorted list gives us the kth 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 the nums array.

  5. The extracted index is appended to the ans list.

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

  7. After processing all queries, the ans list is returned, containing the indices of the kth 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following array represent a max heap?

Example 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]].

  1. For the first query [2,1], trim value is 1. We trim each element in nums to the last digit:

    • 102 becomes 2
    • 473 becomes 3
    • 251 becomes 1
    • 814 becomes 4 The array of trimmed numbers paired with their indices is [('2', 0), ('3', 1), ('1', 2), ('4', 3)].

  2. We then sort these pairs to get [('1', 2), ('2', 0), ('3', 1), ('4', 3)].

  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 is 0.

  4. For the next query [1,2], the trim value is 2, so we don't actually trim since all nums elements are already of length 2 or smaller.

  5. The sorted array of numbers paired with their indices is [('02', 0), ('14', 3), ('51', 2), ('73', 1)].

  6. 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 is 0.

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:

  1. A list of tuples is created for each number and its index with the numbers trimmed to the correct size.
  2. The list of tuples is sorted based on the trimmed numbers.
  3. The index of the kth smallest trimmed number is then found and appended to the result list.
  4. This process is repeated for each query without altering the original nums array.

Hence the final indices of the kth 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
Not Sure What to Study? Take the 2-min Quiz๏ผš

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Time and Space Complexity

Time Complexity

The time complexity of the solution consists of two main operations:

  1. 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 of O(n * m * log(n)), where n is the length of nums and m is the length of the trimmed string. The m factor comes from the time to create the substring for each number, and log(n) is for the sorting.

  2. 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:

  1. The trimmed and tuples list t, which has a size O(n) for each query since we store the trimmed strings and their original indices.

  2. The answer list ans that holds one value for each query, giving it a size of O(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.

Fast Track Your Learning with Our Quick Skills Quiz:

In a binary min heap, the maximum element can be found in:

Recommended Readings

Divide and Conquer Intro

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

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

Heap Fundamentals

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

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ