Daily Problem 10/02/2024: Rank Transform of an Array

Given an array, turn its elements into their respective indices in the sorted version of the array.

The problem statement may be found on leetcode.

Analysis

A trivial solution would just take all values in the input, sort all unique values, define their rank as their positions in the array, and return the initial array as the image of these.

Solution

Trivial Solution

The trivial solution performs shockingly well. Over two submissions it performed both very well and very poorly - it would appear that the distribution is stochastic. The best submission got a \(98\%\) in terms of runtime and a \(26\%\) in terms of memory. The worst got \(24\%\) in terms of runtime and a \(45\%\) in terms of memory. The solution is as follows:

class Solution:
    def arrayRankTransform(self, arr: list[int]) -> list[int]:
        ranks = {item: pos + 1 for pos, item in enumerate(sorted(set(arr)))}

        return [ranks[item] for item in arr]