Skip to main content

Heaps

Query Kth Smallest Trimmed Number Solution In C++/Python/Java/JS

Problem Description

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

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.

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 <= 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
💡
Try it yourself
The problem involves processing a list of numeric strings based on trimming their rightmost digits as specified by queries. For each query, you trim the numbers, find the k-th smallest trimmed value, and return its original index while maintaining ties by their initial order. The goal is to efficiently sort and retrieve results for multiple queries without altering the original data..

Optimal Approach

Intuition

The intuition behind this approach revolves around simplifying the problem by focusing only on the relevant part of each number, much like narrowing down a search in a long list of items. Instead of comparing the entire string of digits, we trim each number to its rightmost given digits, reducing the complexity and looking in on the portion that matters for the current query. This is similar to looking at just the last few digits of serial numbers in a library to identify books more quickly. Once trimmed, we sort these reduced representations to determine the k-th smallest value, while still maintaining ties based on their original order. After each query, we reset the numbers to their original state, ensuring consistency for subsequent queries. This process makes the task efficient and structured by addressing only the essential parts of the data while adhering to the given constraints.

Approach

Step 1: Trim the Numbers
For each query, use the provided trim value to extract the rightmost digits from each numeric string in the array. For example, if the trim value is 3, then for every number in the list, keep only its last three digits.

Step 2: Pair Each Trimmed Number with Its Original Index
After trimming, create pairs that consist of the trimmed number and its corresponding original index from the list. This helps maintain a reference to where the number came from after sorting.

Step 3: Sort Based on Trimmed Values
Sort the array of paired elements (trimmed number and original index) in ascending order by the trimmed numbers. If two trimmed numbers are equal, the pair with the smaller original index should come first. Using a stable sorting algorithm will automatically handle this requirement.

Step 4: Find the k-th Smallest Trimmed Number
For each query [k, trim], once the list is sorted, identify the k-th element in the sorted list. Retrieve the original index from this pair, as this index represents the position of the k-th smallest trimmed number in the original array.

Step 5: Return the Result
After processing all the queries, compile the original indices of the k-th smallest trimmed numbers into a result array and return that array.

Dry Run

Input:
nums = ["102", "473", "251", "814"]queries = [[1,1], [2,3], [4,2], [1,2]]
Output:
[2, 2, 1, 0]

Step-by-Step Dry Run : Query 1: [1, 1]

  • Trim each number to the last 1 digit:nums = ["2", "3", "1", "4"]
  • Pair with original indices:[(2, 0), (3, 1), (1, 2), (4, 3)]
  • Sort by trimmed values:[(1, 2), (2, 0), (3, 1), (4, 3)]
  • Find the k-th smallest (1st smallest):The 1st smallest is (1, 2), so the result is 2.

Query 2: [2, 3]

  • Trim each number to the last 3 digits (no change here since nums[i] has length 3):nums = ["102", "473", "251", "814"]
  • Pair with original indices:[(102, 0), (473, 1), (251, 2), (814, 3)]
  • Sort by trimmed values:[(102, 0), (251, 2), (473, 1), (814, 3)]
  • Find the k-th smallest (2nd smallest):The 2nd smallest is (251, 2), so the result is 2.

Query 3: [4, 2]

  • Trim each number to the last 2 digits:nums = ["02", "73", "51", "14"]
  • Pair with original indices:[(02, 0), (73, 1), (51, 2), (14, 3)]
  • Sort by trimmed values:[(02, 0), (14, 3), (51, 2), (73, 1)]
  • Find the k-th smallest (4th smallest):The 4th smallest is (73, 1), so the result is 1.

Query 4: [1, 2]

  • Trim each number to the last 2 digits:nums = ["02", "73", "51", "14"]
  • Pair with original indices:[(02, 0), (73, 1), (51, 2), (14, 3)]
  • Sort by trimmed values:[(02, 0), (14, 3), (51, 2), (73, 1)]
  • Find the k-th smallest (1st smallest):The 1st smallest is (02, 0), so the result is 0.
    Final Output:
    [2, 2, 1, 0]
Code for All Languages
C++ 
class Solution {
public:
    vector<int> smallestTrimmedNumbers(vector<string>& nums, vector<vector<int>>& queries) {
        vector<int> result;  // Result vector to store the answer for each query
        int n = nums.size(); // Total number of numeric strings

        // Process each query individually
        for (auto& query : queries) {
            int k = query[0];          // k-th smallest trimmed number to find
            int trimLength = query[1]; // The number of rightmost digits to keep after trimming

            vector<pair<string, int>> trimmedNums;  // Pair: <trimmed number, original index>

            // Iterate over each number in nums to trim it according to trimLength
            for (int i = 0; i < n; i++) {
                // Extract the last 'trimLength' digits from nums[i]
                string trimmed = nums[i].substr(nums[i].size() - trimLength);
                // Pair the trimmed string with its original index
                trimmedNums.push_back({trimmed, i});
            }

            // Sort the trimmed numbers lexicographically (and by index in case of ties)
            sort(trimmedNums.begin(), trimmedNums.end());

            // The k-th smallest trimmed number is at index k-1 after sorting.
            // Retrieve the original index of that number and add it to the result vector.
            result.push_back(trimmedNums[k - 1].second);
        }
        
        // Return the result array containing original indices for each query
        return result;
    }
};

Java 
class Solution {
    public List<Integer> smallestTrimmedNumbers(String[] nums, int[][] queries) {
        // Result list to store the answer for each query
        List<Integer> result = new ArrayList<>();
        int n = nums.length;

        // Process each query from the queries array
        for (int[] query : queries) {
            int k = query[0];          // k-th smallest trimmed number to find
            int trimLength = query[1]; // Number of rightmost digits to keep

            // Create a list to hold pairs of the trimmed number and its original index
            List<Pair> trimmedNums = new ArrayList<>();

            // For each number in the nums array, trim it and store with its index
            for (int i = 0; i < n; i++) {
                // Extract the rightmost 'trimLength' digits
                String trimmed = nums[i].substring(nums[i].length() - trimLength);
                // Add a new Pair with the trimmed number and its original index
                trimmedNums.add(new Pair(trimmed, i));
            }

            // Sort the list based on the trimmed strings (lexicographical order)
            trimmedNums.sort(Comparator.comparing(p -> p.str));

            // After sorting, the k-th smallest trimmed number is at index k-1.
            // Retrieve its original index and add it to the result list.
            result.add(trimmedNums.get(k - 1).index);
        }
        // Return the result list containing the indices for each query.
        return result;
    }
}

// Helper class to represent a pair of trimmed string and its original index
class Pair {
    String str;  // The trimmed numeric string
    int index;   // The original index of the number in the nums array

    Pair(String str, int index) {
        this.str = str;
        this.index = index;
    }
}

Python 
def smallest_trimmed_numbers(nums, queries):
    # Initialize a list to store the answer for each query.
    result = []
    # Determine the number of numeric strings in the input.
    n = len(nums)
    
    # Process each query, where each query is a pair (k, trim_length).
    for k, trim_length in queries:
        # For each number in the list, extract the rightmost 'trim_length' digits.
        # Also, keep track of the original index by enumerating the list.
        trimmed_nums = [(num[-trim_length:], i) for i, num in enumerate(nums)]
        
        # Sort the list of tuples. Sorting is done primarily on the trimmed number (as a string)
        # and then on the original index in case of ties (this happens automatically).
        trimmed_nums.sort()
        
        # The k-th smallest trimmed number (1-indexed) is at index k-1 in the sorted list.
        # Append the original index of this trimmed number to the result.
        result.append(trimmed_nums[k - 1][1])
    
    # Return the list containing the original indices for each query.
    return result

Javascript 
const readline = require("readline");

// Create an interface for reading input from stdin
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let input = [];

// Read input line by line
rl.on("line", (line) => {
    input.push(line);
}).on("close", () => {
    let index = 0;
    
    // Read number of strings
    const n = parseInt(input[index++]);
    const nums = input.slice(index, index + n);
    index += n;
    
    // Read number of queries
    const q = parseInt(input[index++]);
    const queries = input.slice(index, index + q).map(line => line.split(" ").map(Number));
    
    /**
     * Function to find the k-th smallest trimmed number's original index
     * @param {string[]} nums - Array of numerical strings
     * @param {number[][]} queries - List of queries, each containing [k, trimLength]
     * @returns {number[]} - List of indices corresponding to query results
     */
    function smallestTrimmedNumbers(nums, queries) {
        let result = [];
        let n = nums.length;

        for (let [k, trimLength] of queries) {
            // Trim each number to the last 'trimLength' digits and store with index
            let trimmedNums = nums.map((num, i) => [num.slice(-trimLength), i]);
            
            // Sort lexicographically, using index as a tiebreaker
            trimmedNums.sort((a, b) => a[0].localeCompare(b[0]) || a[1] - b[1]);
            
            // Get the k-th smallest trimmed number's original index
            result.push(trimmedNums[k - 1][1]);
        }
        return result;
    }
    
    // Compute results for all queries
    const result = smallestTrimmedNumbers(nums, queries);
    
    // Print the results space-separated
    console.log(result.join(" "));
});

Time Complexity:O(Q×N×(T+log⁡N))

  1. Loop over Queries:
    We iterate through each query, so the number of iterations is Q, where Q is the number of queries.
  2. Trimming and Storing the Numbers:
    For each query, we iterate over all strings in the nums array, which has N strings. For each string in nums, we perform the trimming operation (substr(nums[i].size()-q[1])), which takes O(T), where T is the trim_length from the current query.
    So, for each query, trimming all strings and storing their trimmed versions takes O(N×T).
  3. Sorting the Trimmed Numbers:
    After trimming, we need to sort the trimmed strings with respect to their lexicographical order. Sorting N trimmed strings takes O(Nlog⁡N) time.
    Sorting after trimming takes O(Nlog⁡N) time for each query.
  4. Final Calculation:
    After sorting, finding the k-th smallest element in the sorted list takes O(1), as it's a direct lookup into the sorted list.

Overall Time Complexity per Query:
For each query, the time complexity is dominated by:

  • Trimming: O(N×T)
  • Sorting: O(Nlog⁡N)

Thus, the total time complexity per query is:

O(N×T+Nlog⁡N)

Thus, the final time complexity is:

O(Q×N×(T+log⁡N))

Space Complexity : O(N+Q)

Auxiliary Space Complexity:

  • Auxiliary space refers to the extra space used by the algorithm excluding the space used by the input and the result.
  • In this case:

We use a temporary list pq to store the trimmed numbers for sorting, which requires O(N)space.

Therefore, the auxiliary space complexity is: O(N).This space is used for temporarily storing the trimmed strings and their original indices for each query. It does not depend on the number of queries but only on the number of strings in nums.

Overall Space Complexity:

  • The overall space complexity is determined by the space needed to store the result and any auxiliary data structures used throughout the process.
  • For each query, we store:

A list of trimmed numbers, which requires O(N) space, where N is the number of strings in nums.

The final result array (answer) stores the index of the k-th smallest element for each query, which takes O(Q) space, where Q is the number of queries.

  • Therefore, the overall space complexity is: O(N+Q)Here:
  • N is the number of strings in nums.
  • Q is the number of queries.

Learning Tip

Now we have successfully tackled this problem, let's try these similar problems.

Longest Happy String

Given three integers a, b, and c representing the counts of characters 'a', 'b', and 'c', construct the longest possible string using these characters such that no three consecutive characters are the same.

Reorganize String

Given a string s, the task is to rearrange its characters so that no two adjacent characters are the same. If such a rearrangement is possible, return any valid reorganization of the string; otherwise, return an empty string.