We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Query Kth Smallest Trimmed Number

Number: 2422

Difficulty: Medium

Paid? No

Companies: DE Shaw

Problem Description

Given an array of numeric strings (all of equal length) and a set of queries, each query provides a value k and a trim parameter. For each query, trim every string to keep only its rightmost digits as specified by trim. Then, sort the trimmed numbers while preserving their original indices (if two trimmed numbers are the same, the one with the lower index is considered smaller). Finally, return the index of the kth smallest trimmed number for each query.

Key Insights

  • Trimming involves taking the rightmost "trim" digits of each string.
  • The comparison between trimmed numbers is lexicographical unless converted to integers, but lexicographical comparison works correctly when the strings are of equal length.
  • Use sorting for each query to rank the trimmed numbers, or optimize via precomputation (e.g., Radix Sort) given the constraints.
  • The original indices play a role as a tiebreaker when two trimmed numbers are the same.

Space and Time Complexity

Time Complexity: O(q * n log n * L) in the sorting approach, where q is the number of queries, n is the number of numbers, and L is the cost for slicing/comparing strings. Space Complexity: O(n) per query for storing temporary results.

Solution

For each query, iterate over the list of numbers and trim each number to the specified number of rightmost digits. Pair the trimmed string with its index. Sort this list of pairs based on the trimmed string first and index second (for tie-breaking). Then, select the kth smallest trimmed number's original index. One can also precompute the results for each unique trim length and reuse them for multiple queries. Another alternative is to use Radix Sort to take advantage of the fact that strings are fixed-length digits, which yields a time complexity of O(n * L) per query.

Code Solutions

# Python Solution
class Solution:
    def smallestTrimmedNumbers(self, nums, queries):
        answers = []
        # iterate over each query
        for k, trim in queries:
            trimmed_with_index = []
            # Build list of (trimmed_number, index)
            for idx, num in enumerate(nums):
                trimmed = num[-trim:]  # keep rightmost 'trim' digits
                trimmed_with_index.append((trimmed, idx))
            # Sort based on trimmed value, then original index
            trimmed_with_index.sort(key=lambda x: (x[0], x[1]))
            # kth smallest: k-1 due to 0-indexing 
            answers.append(trimmed_with_index[k-1][1])
        return answers

# Example usage:
sol = Solution()
nums = ["102", "473", "251", "814"]
queries = [[1, 1], [2, 3], [4, 2], [1, 2]]
print(sol.smallestTrimmedNumbers(nums, queries))  # Expected Output: [2, 2, 1, 0]
← Back to All Questions