query-kth-smallest-trimmed-number

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

Algorithms

You are given a 0-indexed array of strings <code>nums</code>, where each string is of equal length and consists of only digits.

You are also given a 0-indexed 2D integer array <code>queries</code> where <code>queries[i] = [ki, trimi]</code>. For each <code>queries[i]</code>, you need to:

<ul>
	<li>Trim each number in <code>nums</code> to its rightmost <code>trimi</code> digits.</li>
	<li>Determine the index of the <code>kith</code> smallest trimmed number in <code>nums</code>. If two trimmed numbers are equal, the number with the lower index is considered to be smaller.</li>
	<li>Reset each number in <code>nums</code> to its original length.</li>
</ul>

Return an array <code>answer</code> of the same length as <code>queries</code>, where <code>answer[i]</code> is the answer to the <code>ith</code> query.

Note:

<ul>
	<li>To trim to the rightmost <code>x</code> digits means to keep removing the leftmost digit, until only <code>x</code> digits remain.</li>
	<li>Strings in <code>nums</code> may contain leading zeros.</li>
</ul>

&nbsp;
Example 1:

<pre>
Input: nums = [&quot;102&quot;,&quot;473&quot;,&quot;251&quot;,&quot;814&quot;], queries = [[1,1],[2,3],[4,2],[1,2]]
Output: [2,2,1,0]
Explanation:
1. After trimming to the last digit, nums = [&quot;2&quot;,&quot;3&quot;,&quot;1&quot;,&quot;4&quot;]. 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 = [&quot;02&quot;,&quot;73&quot;,&quot;51&quot;,&quot;14&quot;]. 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 &quot;02&quot; is evaluated as 2.
</pre>

Example 2:

<pre>
Input: nums = [&quot;24&quot;,&quot;37&quot;,&quot;96&quot;,&quot;04&quot;], queries = [[2,1],[2,2]]
Output: [3,0]
Explanation:
1. Trimmed to the last digit, nums = [&quot;4&quot;,&quot;7&quot;,&quot;6&quot;,&quot;4&quot;]. 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.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 100</code></li>
	<li><code>1 &lt;= nums[i].length &lt;= 100</code></li>
	<li><code>nums[i]</code> consists of only digits.</li>
	<li>All <code>nums[i].length</code> are equal.</li>
	<li><code>1 &lt;= queries.length &lt;= 100</code></li>
	<li><code>queries[i].length == 2</code></li>
	<li><code>1 &lt;= ki &lt;= nums.length</code></li>
	<li><code>1 &lt;= trimi &lt;= nums[i].length</code></li>
</ul>

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