Query Kth Smallest Trimmed Number — LeetCode 2343 Python Solution

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].

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.

Python solution

class Solution:
    def smallestTrimmedNumbers(
        self, nums: List[str], queries: List[List[int]]
    ) -> List[int]:
        ans = []
        for k, trim in queries:
            t = sorted((v[-trim:], i) for i, v in enumerate(nums))
            ans.append(t[k - 1][1])
        return ans

Complexity

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2343. Query Kth Smallest Trimmed Number is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Heap (Priority Queue).

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Related problems