The power and simplicity of IComparer III

IComparer can be used with BigInteger too which makes it very handy for problems like this one. Notice that the only reason to use IComparer is that the sorting is conditional when the two elements are the same (in this case we need to use the elements' indexes). Other than that, just follow exactly what the problem description says - since the constraints of the problem are very small, execution time won't suffer as much despite the time complexity being of O(N^2 * NLogN). N is very small (10^2), hence this reduces to N^3, or one million. Code is down below, cheers, ACC.

Query Kth Smallest Trimmed Number - LeetCode

2343. Query Kth Smallest Trimmed Number

Medium

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

Accepted

11,082

Submissions

29,970

public class NumberIndex
{
    public BigInteger value = 0;
    public int index = 0;

    public NumberIndex(BigInteger value, int index)
    {
        this.value = value;
        this.index = index;
    }
}

public class MyComparerNumberIndex : IComparer
{
    public int Compare(Object x, Object y)
    {
        NumberIndex xn = (NumberIndex)x;
        NumberIndex yn = (NumberIndex)y;

        if (xn.value != yn.value) return xn.value.CompareTo(yn.value);
        return xn.index.CompareTo(yn.index);
    }
}

public int[] SmallestTrimmedNumbers(string[] nums, int[][] queries)
{
    int[] retVal = new int[queries.Length];

    for (int i = 0; i < queries.Length; i++)
    {
        NumberIndex[] numbers = new NumberIndex[nums.Length];
        for (int j = 0; j < nums.Length; j++)
        {
            string temp = (queries[i][1] < nums[j].Length) ? nums[j].Substring(nums[j].Length - queries[i][1]) : nums[j];
            numbers[j] = new NumberIndex(BigInteger.Parse(temp), j);
        }

        Array.Sort(numbers, new MyComparerNumberIndex());
        retVal[i] = numbers[queries[i][0] - 1].index;
    }

    return retVal;
}