Query Kth Smallest Trimmed Number solution and explanation
9 more videos on this problem
Leetcode Weekly contest 302 - Medium - Query Kth Smallest Trimmed NumberPrakhar Agrawal · 14:59 · 1K views
2343. Query Kth Smallest Trimmed Number (Leetcode Medium)Programming Live with Larry · 8:44 · 995 views
[Leetcode Weekly Contest 302] 3 - Query Kth Smallest Trimmed NumberSandeep Kumar · 12:40 · 667 views
【每日一题】LeetCode 2343. Query Kth Smallest Trimmed NumberHuifeng Guan · 23:12 · 604 views
6121. Query Kth Smallest Trimmed NumberLiVe-CoDiNg · 1:23 · 599 views
Query Kth Smallest Trimmed Number || Priority Queue || CPP || Medium WalaVijay Jha · 17:32 · 389 views
Leetcode 2343. Query Kth Smallest Trimmed Number - Easy Radix sort / digital sort, or brute forceCode-Yao · 12:17 · 383 views
Radix Sort Implementation with C++ [ARABIC] | Query Kth Smallest Trimmed Number (leetcode problem)Saeed Ahmed · 20:30 · 293 views
[MUST WATCH] Sorting-21 | 2343. Query Kth Smallest Trimmed Number (Optimised)CTO Bhaiya · 46:21 · 244 views
Sorting-19 | 2343. Query Kth Smallest Trimmed Number (Brute) | 🔥 Beginner, Medium & Advanced LevelCTO Bhaiya · 18:39 · 241 views
The problem
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
numsto its rightmosttrimidigits. - Determine the index of the
kithsmallest trimmed number innums. If two trimmed numbers are equal, the number with the lower index is considered to be smaller. - Reset each number in
numsto 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
xdigits means to keep removing the leftmost digit, until onlyxdigits remain. - Strings in
numsmay 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.- All
nums[i].lengthare 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?
Approach overview
Problem Overview: You are given an array of equal-length numeric strings. Each query asks you to trim every number to its last trim digits, then return the index of the k-th smallest trimmed value. If two trimmed numbers are equal, the smaller original index wins. Each query works independently, so the challenge is efficiently comparing many trimmed substrings.
Approach 1: Simple Sorting Approach (O(q · n log n) time, O(n) space)
The direct approach processes every query independently. For a query [k, trim], iterate through the array and extract the last trim digits from each string using substring operations. Store pairs of (trimmed_value, index). Sort this list lexicographically by the trimmed value, and break ties using the index. The answer for the query is the index at position k-1 after sorting.
This method relies on standard sorting and works well when the number of queries or numbers is small. The downside is repeated work: the same trims may be recomputed many times. If there are q queries and n numbers, sorting for each query leads to O(q · n log n) time. Still, the logic is straightforward and easy to implement in any language.
Approach 2: Optimized Bucket Sort Method (Radix Style) (O(m · n) time, O(n) space)
A faster solution observes that trimming always keeps the suffix of the number. Instead of recomputing trims for every query, process digits from right to left using a radix-style technique. Maintain an ordered list of indices representing numbers sorted by their last t digits. For each additional digit position, perform a stable bucket/counting sort based on the next digit to the left.
Because digits range from 0–9, each step distributes indices into 10 buckets, preserving previous order. After processing t digits, the list represents numbers sorted by their last t digits. Store this ordering so queries asking for that trim length can directly access the k-1 position. This technique is essentially a specialized radix sort applied to numeric strings.
The preprocessing runs for at most the number length m, and each pass processes all n numbers, giving O(m · n) time. Query answers become constant time lookups. The idea combines properties of arrays and stable bucket sorting to avoid repeated comparisons.
Recommended for interviews: Start by describing the simple sorting approach. It demonstrates understanding of trimming logic, lexicographic comparison, and tie-breaking with indices. Then explain the radix-style bucket optimization. Interviewers typically expect the optimized idea because it avoids redundant sorting and shows familiarity with digit-based sorting techniques.
Approach 1: Simple Sorting Approach
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.
from typing import List
def kthSmallestTrimmedNumber(nums: List[str], queries: List[List[int]]) -> List[int]:
result = []
for k, trim in queries:
trimmed_list = [(num[-trim:], i) for i, num in enumerate(nums)]
trimmed_list.sort()
result.append(trimmed_list[k - 1][1])
return resultimport java.util.*;
public class Solution {
public int[] kthSmallestTrimmedNumber(String[] nums, int[][] queries) {
int[] result = new int[queries.length];
for (int q = 0; q < queries.length; q++) {
int k = queries[q][0];
int trim = queries[q][1];
List<int[]> list = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
String trimmed = nums[i].substring(nums[i].length() - trim);
list.add(new int[]{Integer.parseInt(trimmed), i});
}
Collections.sort(list, (a, b) -> {
if (a[0] == b[0]) return Integer.compare(a[1], b[1]);
return Integer.compare(a[0], b[0]);
});
result[q] = list.get(k - 1)[1];
}
return result;
}
}#include <vector>
#include <string>
#include <algorithm>
using namespace std;
vector<int> kthSmallestTrimmedNumber(vector<string>& nums, vector<vector<int>>& queries) {
vector<int> result;
for (const auto& query : queries) {
int k = query[0];
int trim = query[1];
vector<pair<string, int>> trimmed_nums;
for (int i = 0; i < nums.size(); ++i) {
string trimmed = nums[i].substr(nums[i].size() - trim);
trimmed_nums.emplace_back(trimmed, i);
}
sort(trimmed_nums.begin(), trimmed_nums.end());
result.push_back(trimmed_nums[k - 1].second);
}
return result;
}function kthSmallestTrimmedNumber(nums, queries) {
const result = [];
for (let [k, trim] of queries) {
const trimmedNums = nums.map((num, i) => [num.slice(-trim), i]);
trimmedNums.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0].localeCompare(b[0]));
result.push(trimmedNums[k - 1][1]);
}
return result;
}#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int compare(const void* a, const void* b) {
int lengthA = strlen(((char**)a)[0]);
int lengthB = strlen(((char**)b)[0]);
int cmp = strncmp(((char**)a)[0], ((char**)b)[0], lengthA < lengthB ? lengthA : lengthB);
if (cmp != 0) return cmp;
return ((int*)a)[1] - ((int*)b)[1];
}
void kthSmallestTrimmedNumber(char** nums, int numsSize, int** queries, int queriesSize, int* queriesColSize, int* result) {
for (int q = 0; q < queriesSize; ++q) {
int k = queries[q][0];
int trim = queries[q][1];
char trimmed[numsSize][101];
int index[numsSize];
for (int i = 0; i < numsSize; ++i) {
int len = strlen(nums[i]);
strcpy(trimmed[i], nums[i] + len - trim);
index[i] = i;
}
char* trimmedNums[numsSize];
for (int i = 0; i < numsSize; ++i) trimmedNums[i] = trimmed[i];
int paired[numsSize][2];
for (int i = 0; i < numsSize; ++i) {
paired[i][0] = i;
paired[i][1] = index[i];
}
qsort(paired, numsSize, sizeof(pair), compare);
result[q] = paired[k - 1][1];
}
}using System;
using System.Collections.Generic;
public class Solution {
public int[] KthSmallestTrimmedNumber(string[] nums, int[][] queries) {
int[] result = new int[queries.Length];
for (int q = 0; q < queries.Length; q++) {
int k = queries[q][0];
int trim = queries[q][1];
var trimmedList = new List<Tuple<string, int>>();
for (int i = 0; i < nums.Length; i++) {
trimmedList.Add(new Tuple<string, int>(nums[i].Substring(nums[i].Length - trim), i));
}
trimmedList.Sort((a, b) =>
a.Item1.Equals(b.Item1) ? a.Item2 - b.Item2 : String.Compare(a.Item1, b.Item1, StringComparison.Ordinal)
);
result[q] = trimmedList[k - 1].Item2;
}
return result;
}
}This Python implementation involves generating a list of tuples for each query, consisting of the trimmed numbers and their indices. It then sorts this list and appends the k-th number's original index to the results list, based on the query.
Time Complexity: O(Q * N * log(N)), where Q is the number of queries and N is the size of nums.
Space Complexity: O(N), due to the data structure for storing trimmed numbers with their indices.
Approach 2: Optimized Bucket Sort Method
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.
from typing import List
def counting_sort(order, nums, digit):
count = [0] * 10
temp_order = [0] * len(order)
for index in order:
digit_value = int(nums[index][digit])
count[digit_value] += 1
for i in range(1, 10):
count[i] += count[i - 1]
for i in reversed(range(len(order))):
index = order[i]
digit_value = int(nums[index][digit])
count[digit_value] -= 1
temp_order[count[digit_value]] = index
return temp_order
def kthSmallestTrimmedNumber(nums: List[str], queries: List[List[int]]) -> List[int]:
n = len(nums)
length = len(nums[0])
order = list(range(n))
result = []
for k, trim in queries:
start_digit = length - trim
# Iterate backwards over relevant digits
for digit in range(length - 1, start_digit - 1, -1):
order = counting_sort(order, nums, digit)
result.append(order[k - 1])
return resultimport java.util.*;
public class Solution {
public int[] kthSmallestTrimmedNumber(String[] nums, int[][] queries) {
int n = nums.length;
int len = nums[0].length();
int[] order = new int[n];
for (int i = 0; i < n; ++i) order[i] = i;
int[] result = new int[queries.length];
for (int q = 0; q < queries.length; ++q) {
int k = queries[q][0];
int trim = queries[q][1];
int startDigit = len - trim;
for (int digit = len - 1; digit >= startDigit; --digit) {
countingSort(order, nums, digit);
}
result[q] = order[k - 1];
}
return result;
}
private void countingSort(int[] order, String[] nums, int digit) {
int[] count = new int[10];
int[] tempOrder = new int[order.length];
for (int index : order) {
int digitValue = nums[index].charAt(digit) - '0';
count[digitValue]++;
}
for (int i = 1; i < 10; ++i) {
count[i] += count[i - 1];
}
for (int i = order.length - 1; i >= 0; --i) {
int index = order[i];
int digitValue = nums[index].charAt(digit) - '0';
tempOrder[--count[digitValue]] = index;
}
System.arraycopy(tempOrder, 0, order, 0, order.length);
}
}#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
void countingSort(vector<int>& order, vector<string>& nums, int digit) {
vector<int> count(10, 0);
vector<int> temp_order(order.size());
for (int index : order) {
int digit_value = nums[index][digit] - '0';
count[digit_value]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = order.size() - 1; i >= 0; i--) {
int index = order[i];
int digit_value = nums[index][digit] - '0';
temp_order[--count[digit_value]] = index;
}
order = temp_order;
}
vector<int> kthSmallestTrimmedNumber(vector<string>& nums, vector<vector<int>>& queries) {
int n = nums.size();
int len = nums[0].length();
vector<int> order(n);
iota(order.begin(), order.end(), 0);
vector<int> result;
for (const auto& q : queries) {
int k = q[0], trim = q[1];
int startDigit = len - trim;
for (int digit = len - 1; digit >= startDigit; --digit) {
countingSort(order, nums, digit);
}
result.push_back(order[k - 1]);
}
return result;
}function kthSmallestTrimmedNumber(nums, queries) {
const n = nums.length;
const len = nums[0].length;
let order = [...Array(n).keys()];
const result = [];
const countingSort = (digit) => {
const count = new Array(10).fill(0);
const tempOrder = new Array(n);
for (const index of order) {
const digitValue = nums[index].charAt(digit) - '0';
count[digitValue]++;
}
for (let i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (let i = order.length - 1; i >= 0; i--) {
const index = order[i];
const digitValue = nums[index].charAt(digit) - '0';
tempOrder[--count[digitValue]] = index;
}
order = tempOrder;
};
for (const [k, trim] of queries) {
const startDigit = len - trim;
for (let digit = len - 1; digit >= startDigit; digit--) {
countingSort(digit);
}
result.push(order[k - 1]);
}
return result;
}/* Radix sort solution for the given problem constraints in C */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void radix_sort(int* order, char** nums, int n, int digit_position) {
int count[10] = {0};
for (int i = 0; i < n; i++) {
int index = nums[order[i]][digit_position] - '0';
count[index]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
int temp[n];
for (int i = n - 1; i >= 0; i--) {
int index = nums[order[i]][digit_position] - '0';
temp[--count[index]] = order[i];
}
for (int i = 0; i < n; i++) {
order[i] = temp[i];
}
}
void kthSmallestTrimmedNumberRadix(char** nums, int numsSize, int** queries, int queriesSize, int* queriesColSize, int* result) {
int length = strlen(nums[0]);
int ordered_idx[numsSize];
for (int i = 0; i < numsSize; i++) {
ordered_idx[i] = i;
}
for (int q = 0; q < queriesSize; q++) {
int k = queries[q][0];
int trim = queries[q][1];
int start = length - trim;
for (int pos = length - 1; pos >= start; pos--) {
radix_sort(ordered_idx, nums, numsSize, pos);
}
result[q] = ordered_idx[k - 1];
}
}using System;
using System.Collections.Generic;
public class Solution {
public int[] KthSmallestTrimmedNumber(string[] nums, int[][] queries) {
int n = nums.Length;
int len = nums[0].Length;
int[] order = new int[n];
for (int i = 0; i < n; ++i) order[i] = i;
int[] result = new int[queries.Length];
for (int q = 0; q < queries.Length; ++q) {
int k = queries[q][0];
int trim = queries[q][1];
int startDigit = len - trim;
for (int digit = len - 1; digit >= startDigit; --digit) {
CountingSort(order, nums, digit);
}
result[q] = order[k - 1];
}
return result;
}
private void CountingSort(int[] order, string[] nums, int digit) {
int[] count = new int[10];
int[] tempOrder = new int[order.Length];
foreach (int index in order) {
int digitValue = nums[index][digit] - '0';
count[digitValue]++;
}
for (int i = 1; i < 10; ++i) {
count[i] += count[i - 1];
}
for (int i = order.Length - 1; i >= 0; --i) {
int index = order[i];
int digitValue = nums[index][digit] - '0';
tempOrder[--count[digitValue]] = index;
}
Array.Copy(tempOrder, order, order.Length);
}
}The Python variant employs a Radix Sort-like counting method on numbers parsed from string digits, specifically focusing on sequentially sorted result orders reflecting element index per query.
Time Complexity: O(D * (N + R)), considering digit depth exploration.
Space Complexity: O(N), managing indexed tracking per request.
Approach 3: Simulation
According to the problem description, we can simulate the cropping process, then sort the cropped strings, and finally find the corresponding number based on the index.
The time complexity is O(m times n times log n times s), and the space complexity is O(n). Here, m and n are the lengths of nums and queries respectively, and s is the length of the string nums[i].
func smallestTrimmedNumbers(nums []string, queries [][]int) []int {
type pair struct {
s string
i int
}
ans := make([]int, len(queries))
t := make([]pair, len(nums))
for i, q := range queries {
for j, s := range nums {
t[j] = pair{s[len(s)-q[1]:], j}
}
sort.Slice(t, func(i, j int) bool { a, b := t[i], t[j]; return a.s < b.s || a.s == b.s && a.i < b.i })
ans[i] = t[q[0]-1].i
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Simple Sorting Approach | Time Complexity: O(Q * N * log(N)), where Q is the number of queries and N is the size of nums. |
| Optimized Bucket Sort Method | Time Complexity: O(D * (N + R)), considering digit depth exploration. |
| Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simple Sorting | O(q · n log n) | O(n) | Best for quick implementation or when constraints are small |
| Bucket Sort (Radix Style) | O(m · n) | O(n) | Preferred for large inputs or many queries; avoids repeated sorting |
Frequently asked questions
Is Query Kth Smallest Trimmed Number easy or hard?
Query Kth Smallest Trimmed Number is generally rated Medium. The brute-force sorting idea is straightforward, but recognizing that multiple queries share overlapping trims and can be optimized with radix-style sorting makes the problem more challenging.
Query Kth Smallest Trimmed Number Python/Java solution
In Python or Java, the basic solution builds a list of (trimmed_string, index) pairs and sorts them using built-in sorting functions. The optimized solution implements counting or bucket sort on digits while storing index order for each trim length.
How to solve Query Kth Smallest Trimmed Number in O(n)?
Use a radix-style approach with bucket or counting sort on digits. Starting from the rightmost digit, repeatedly group indices by digit values (0–9) while maintaining stable order. After processing t digits, the array is sorted by the last t digits, allowing constant-time lookup for queries with trim = t.
What is the best approach for Query Kth Smallest Trimmed Number?
The most efficient approach uses a radix-style bucket sort. Process digits from right to left and maintain the order of indices using stable counting sort. After computing sorted orders for each trim length, every query can be answered by directly selecting the k-1 index. This reduces repeated sorting and runs in O(m · n) time.
Is Query Kth Smallest Trimmed Number asked at Google/Amazon/Meta?
This problem reflects patterns commonly asked in large tech interviews, especially questions involving sorting strings, radix sort, and query preprocessing. Similar problems appear in companies like Amazon and Google where candidates must optimize repeated queries over arrays.
What data structure is used in Query Kth Smallest Trimmed Number?
The problem primarily uses arrays and sorting techniques. The optimized solution relies on bucket arrays for counting sort and maintains ordered lists of indices. These structures help simulate radix sort over numeric strings.
What is the time complexity of Query Kth Smallest Trimmed Number?
The straightforward solution sorts the trimmed numbers for every query, giving O(q · n log n) time and O(n) space. The optimized radix-style bucket method processes digits incrementally and runs in O(m · n) time, where m is the length of each number string.