Query Kth Smallest Trimmed Number - Practice Coding Problems

Query Kth Smallest Trimmed Number - Problem

Array String Divide and Conquer Sorting Heap (Priority Queue) Radix Sort Quickselect Medium

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.

Input & Output

Example 1 — Basic Trimming

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

› Output: [2,2,1,0]

💡 Note: Query [1,1]: trim=1 gives ["2","3","1","4"], 1st smallest is "1" at index 2. Query [2,3]: trim=3 gives ["102","473","251","814"], 2nd smallest is "251" at index 2. Query [4,2]: trim=2 gives ["02","73","51","14"], 4th smallest is "73" at index 1. Query [1,2]: trim=2 gives ["02","73","51","14"], 1st smallest is "02" at index 0.

Example 2 — Leading Zeros

$ Input: nums = ["24","37","96","04"], queries = [[2,1],[2,2]]

› Output: [3,0]

💡 Note: Query [2,1]: trim=1 gives ["4","7","6","4"], sorted: ["4","4","6","7"]. Second smallest "4" is at index 3 (lower index wins tiebreaker). Query [2,2]: trim=2 gives ["24","37","96","04"], sorted: ["04","24","37","96"]. Second smallest is "24" at index 0.

Constraints

1 ≤ nums.length ≤ 100
1 ≤ nums[i].length ≤ 100
nums[i] consists of only digits
All nums[i] are of the same length
1 ≤ queries.length ≤ 100
queries[i].length == 2
1 ≤ k_i ≤ nums.length
1 ≤ trim_i ≤ nums[i].length

Visualization

Tap to expand

Understanding the Visualization

Input

Array of equal-length digit strings and queries [k, trim]

Process

Trim each string to rightmost 'trim' digits, sort with indices

Output

Return original index of k-th smallest trimmed number

Key Takeaway

🎯 Key Insight: Trim strings to specified length, then sort while tracking original indices for the answer

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to sort trimmed numbers while preserving original indices for tiebreaking. The brute force approach sorts for each query in O(q × n log n). The optimized approach precomputes sorted orders for all trim lengths in O(d × n log n + q) time and O(d × n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Sort for Each Query	O(q × n log n)	O(n)	For each query, trim all numbers, sort them with original indices, and find k-th element
Optimized - Radix Sort Approach	O(d × n + q)	O(d × n)	Use radix sort from least significant digit to avoid full sorting for each query

Brute Force - Sort for Each Query — Algorithm Steps

Step 1: For each query, extract trim length and k value
Step 2: Create list of (trimmed_number, original_index) pairs
Step 3: Sort pairs by trimmed number, using original index as tiebreaker
Step 4: Return original index of k-th element (k-1 due to 0-indexing)

Visualization

Tap to expand

Step-by-Step Walkthrough

Trim Numbers

Extract rightmost 'trim' digits from each number

Sort with Indices

Sort (trimmed_value, original_index) pairs

Find k-th Element

Return original index of k-th sorted element

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char trimmed[20];
    int index;
} Pair;

int compare(const void* a, const void* b) {
    Pair* pa = (Pair*)a;
    Pair* pb = (Pair*)b;
    int cmp = strcmp(pa->trimmed, pb->trimmed);
    if (cmp == 0) {
        return pa->index - pb->index;
    }
    return cmp;
}

int* solution(char nums[][20], int numsSize, int queries[][2], int queriesSize, int* returnSize) {
    *returnSize = queriesSize;
    int* result = (int*)malloc(queriesSize * sizeof(int));
    
    for (int q = 0; q < queriesSize; q++) {
        int k = queries[q][0];
        int trim = queries[q][1];
        
        // Create pairs of (trimmed_number, original_index)
        Pair* trimmedPairs = (Pair*)malloc(numsSize * sizeof(Pair));
        for (int i = 0; i < numsSize; i++) {
            int len = strlen(nums[i]);
            if (trim >= len) {
                strcpy(trimmedPairs[i].trimmed, nums[i]);
            } else {
                strcpy(trimmedPairs[i].trimmed, nums[i] + len - trim);
            }
            trimmedPairs[i].index = i;
        }
        
        // Sort by trimmed number, then by original index
        qsort(trimmedPairs, numsSize, sizeof(Pair), compare);
        
        // Get the k-th smallest (k-1 due to 0-indexing)
        result[q] = trimmedPairs[k-1].index;
        
        free(trimmedPairs);
    }
    
    return result;
}

int main() {
    char nums[100][20];
    int queries[100][2];
    int numsSize = 0, queriesSize = 0;
    
    // Simple parsing - assume well-formed input
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse nums (simplified)
    char* token = strtok(line, "[],\"\n ");
    while (token != NULL && numsSize < 100) {
        if (strlen(token) > 0 && token[0] >= '0' && token[0] <= '9') {
            strcpy(nums[numsSize], token);
            numsSize++;
        }
        token = strtok(NULL, "[],\"\n ");
    }
    
    // Parse queries (simplified)
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[], \n");
    while (token != NULL && queriesSize < 100) {
        if (strlen(token) > 0 && token[0] >= '0' && token[0] <= '9') {
            queries[queriesSize][0] = atoi(token);
            token = strtok(NULL, "[], \n");
            if (token != NULL) {
                queries[queriesSize][1] = atoi(token);
                queriesSize++;
            }
        } else {
            token = strtok(NULL, "[], \n");
        }
    }
    
    int returnSize;
    int* result = solution(nums, numsSize, queries, queriesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(q × n log n)

For each of q queries, we sort n elements taking O(n log n) time

⚡ Linearithmic

Space Complexity

O(n)

Extra space for storing trimmed number and index pairs

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Sort for Each Query — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler