2343. Query Kth Smallest Trimmed Number LeetCode Solution

In this guide, you will get 2343. Query Kth Smallest Trimmed Number LeetCode Solution with the best time and space complexity. The solution to Query Kth Smallest Trimmed Number problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Query Kth Smallest Trimmed Number solution in C++
Query Kth Smallest Trimmed Number solution in Java
Query Kth Smallest Trimmed Number solution in Python
Additional Resources

2343. Query Kth Smallest Trimmed Number LeetCode Solution image

Problem Statement of Query Kth Smallest Trimmed Number

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 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 <= 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

Follow up: Could you use the Radix Sort Algorithm to solve this problem? What will be the complexity of that solution?

Complexity Analysis

Time Complexity: O(q \cdot \texttt{sort})
Space Complexity: O(q + n)

2343. Query Kth Smallest Trimmed Number LeetCode Solution in C++

class Solution {
 public:
  vector<int> smallestTrimmedNumbers(vector<string>& nums,
                                     vector<vector<int>>& queries) {
    vector<int> ans;
    for (const vector<int>& query : queries)
      ans.push_back(getKSmallestIndex(nums, query[0], query[1]));
    return ans;
  }

 private:
  int getKSmallestIndex(const vector<string>& nums, int k, int trim) {
    const int startIndex = nums[0].length() - trim;
    vector<pair<string, int>> trimmed;  // (num, index)

    for (int i = 0; i < nums.size(); ++i) {
      const string& num = nums[i];
      trimmed.push_back({num.substr(startIndex), i});
    }

    ranges::sort(trimmed);
    return trimmed[k - 1].second;
  }
};
/* code provided by PROGIEZ */