Problem Description

You have an array of strings nums where all strings have the same length and contain only digits. You also have a 2D array queries where each query contains two values: [k, trim].

For each query, you need to:

1. Trim all numbers in nums by keeping only the rightmost trim digits. For example, if a number is "12345" and trim = 3, the trimmed number becomes "345".

2. Sort the trimmed numbers and find the k-th smallest one (1-indexed). When two trimmed numbers are equal, the one that appears earlier in the original array (smaller index) is considered smaller.

3. Return the original index of the k-th smallest trimmed number.

4. Reset the array back to its original state before processing the next query.

The function should return an array where each element is the answer (original index) for the corresponding query.

Example walkthrough:

• If nums = ["102", "473", "251", "814"] and query is [2, 1]:
  • Trim to rightmost 1 digit: ["2", "3", "1", "4"]
  • Sort with original indices: "1"(index 2) < "2"(index 0) < "3"(index 1) < "4"(index 3)
  • The 2nd smallest is at original index 0

Key points:

• Trimming means removing digits from the left until only the specified number of rightmost digits remain
• The strings may have leading zeros after trimming
• When comparing equal trimmed values, use the original index as a tiebreaker

Intuition

The key insight is that we need to process each query independently while preserving the original indices of the numbers. Since each query asks for the k-th smallest trimmed number, we need both the trimmed values for comparison and their original positions for the final answer.

The most straightforward approach is simulation - actually perform the trimming operation for each query. Since strings in Python support slicing, we can easily get the rightmost trim digits using negative indexing: s[-trim:] gives us the last trim characters.

For sorting, we need to maintain a connection between each trimmed value and its original index. This naturally leads to creating pairs of (trimmed_value, original_index). When we sort these pairs, Python will automatically sort by the trimmed value first, and if two values are equal, it will sort by the second element (the index), which perfectly matches our tiebreaker requirement.

The beauty of this approach is that we don't need to explicitly handle the tiebreaker logic - by pairing each trimmed string with its index and sorting these tuples, we get the correct ordering automatically. After sorting, the k-th smallest element (using 1-based indexing) is at position k-1 in our sorted list, and we just need to extract its original index.

Since we're creating new trimmed strings for each query rather than modifying the original array, there's no need to "reset" anything - the original nums array remains unchanged throughout the process.

Learn more about Divide and Conquer, Sorting and Heap (Priority Queue) patterns.

Solution Approach

The solution follows a direct simulation approach for each query:

Step 1: Process each query independently

for k, trim in queries:

We iterate through each query, extracting the k value (position we need) and trim value (number of rightmost digits to keep).

Step 2: Create trimmed pairs with indices

t = sorted((v[-trim:], i) for i, v in enumerate(nums))

This line does several things:

• enumerate(nums) gives us each string with its original index
• v[-trim:] extracts the rightmost trim digits from each string. For example, if v = "12345" and trim = 3, then v[-3:] gives "345"
• We create tuples of (trimmed_value, original_index) for each element
• sorted() sorts these tuples lexicographically

The sorting works as follows:

• First compares by the trimmed string value (lexicographic comparison works correctly for digit strings)
• If two trimmed values are equal, it compares by the second element (the original index)
• This automatically handles the tiebreaker rule where smaller indices come first

Step 3: Extract the k-th smallest element's index

ans.append(t[k - 1][1])

• Since the query uses 1-based indexing (k-th smallest), we access t[k-1] for 0-based indexing
• t[k-1] gives us the tuple (trimmed_value, original_index)
• t[k-1][1] extracts just the original index, which is what we need to return

Time Complexity: O(Q * N * log N) where Q is the number of queries and N is the number of strings, since we sort for each query.

Space Complexity: O(N) for storing the temporary sorted list of tuples.

Example Walkthrough

Let's walk through a concrete example with nums = ["24", "37", "96", "04"] and query [2, 1].

Step 1: Extract query parameters

• k = 2 (we want the 2nd smallest)
• trim = 1 (keep only the rightmost 1 digit)

Step 2: Create trimmed pairs For each string, we trim to the rightmost 1 digit and pair with its original index:

• nums[0] = "24" → trim to "4" → pair: ("4", 0)
• nums[1] = "37" → trim to "7" → pair: ("7", 1)
• nums[2] = "96" → trim to "6" → pair: ("6", 2)
• nums[3] = "04" → trim to "4" → pair: ("4", 3)

Step 3: Sort the pairs When we sort these tuples, Python compares the trimmed values first:

• ("4", 0) and ("4", 3) both have trimmed value "4"
• ("6", 2) has trimmed value "6"
• ("7", 1) has trimmed value "7"

For the two "4"s, since they're equal, Python uses the second element (index) as tiebreaker:

• ("4", 0) comes before ("4", 3) because 0 < 3

Sorted result: [("4", 0), ("4", 3), ("6", 2), ("7", 1)]

Step 4: Find the k-th smallest Since k = 2 (1-indexed), we need the element at position 1 (0-indexed):

• t[1] = ("4", 3)
• Extract the original index: 3

Answer: The 2nd smallest trimmed number comes from index 3 in the original array.

This approach elegantly handles the tiebreaker rule automatically through tuple sorting, without needing any special comparison logic.

Solution Implementation

Time and Space Complexity

The time complexity is O(m × n × log n × s), where:

• m is the length of queries (number of queries to process)
• n is the length of nums (number of strings in the input array)
• log n comes from the sorting operation on n elements
• s is the maximum length of strings in nums (for string comparison during sorting)

Breaking down the analysis:

• The outer loop iterates through all queries: O(m)
• For each query, we create a list of tuples containing trimmed strings and indices: O(n × trim) where trim ≤ s
• Sorting this list of n tuples requires O(n × log n) comparisons
• Each comparison between trimmed strings takes O(trim) time in the worst case, where trim ≤ s
• Combined: O(m × n × log n × s)

The space complexity is O(n × s), where:

• For each query, we create a temporary list t containing n tuples
• Each tuple stores a trimmed string of length up to s and an index
• The trimmed strings require O(n × s) space in the worst case when trim = s
• The output list ans stores m integers: O(m)
• Overall space complexity is dominated by O(n × s)

Note: The reference answer states space complexity as O(n), which appears to only account for the number of elements stored but not the string content itself. The more precise analysis should include the space for storing the trimmed strings.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect String Comparison for Numbers

Issue: A common mistake is assuming that string comparison of numbers works the same as numeric comparison. For instance, comparing "9" and "10" as strings would incorrectly place "9" > "10" because '9' > '1' lexicographically.

Why it works here: This is actually NOT a problem in this specific case because all trimmed strings have the same length (we trim to exactly trim digits). When comparing equal-length digit strings, lexicographic comparison gives the correct numerical ordering. For example, "09" < "10" and "99" < "100" would never occur since both strings have the same length after trimming.

Pitfall 2: Forgetting 1-Based Indexing

Issue: The problem states that k is 1-indexed (finding the k-th smallest), but Python lists use 0-based indexing. Forgetting to subtract 1 when accessing the sorted list would cause an off-by-one error.

Incorrect:

result.append(trimmed_with_indices[k_position][1])  # Wrong!

Correct:

result.append(trimmed_with_indices[k_position - 1][1])  # Correct

Pitfall 3: Modifying the Original Array

Issue: Some might try to modify the nums array in-place for efficiency, but the problem requires resetting to the original state between queries.

Incorrect approach:

# Don't do this - it modifies the original array
for i in range(len(nums)):
    nums[i] = nums[i][-trim_length:]
# Now nums is permanently changed!

Correct approach: Create new trimmed values without modifying the original:

trimmed_with_indices = [(number[-trim_length:], index) for index, number in enumerate(nums)]

Pitfall 4: Using Only the Trimmed Value for Sorting

Issue: When trimmed values are equal, we need to use the original index as a tiebreaker. Simply sorting by trimmed values alone would give incorrect results.

Incorrect:

# This doesn't handle ties correctly
trimmed = [num[-trim_length:] for num in nums]
sorted_indices = sorted(range(len(nums)), key=lambda i: trimmed[i])

Correct: Using tuples ensures proper tiebreaking:

trimmed_with_indices = [(number[-trim_length:], index) for index, number in enumerate(nums)]
trimmed_with_indices.sort()  # Automatically uses index as tiebreaker