Leetcode Daily Question 02/10/2024 - 1331. Rank Transform of an Array

Problem Description:

Given an array of integers arr, replace each element with its rank. | ------------------ | The rank represents how large the element is. The rank has the following rules: | ------------------ | Rank is an integer starting from 1. | ------------------ | The larger the element, the larger the rank. If two elements are equal, their rank must be the same. Rank should be as small as possible.

from typing import List
class Solution:
  def arrayRankTransform(self, arr: List[int]) -> List[int]:
    unique_elts = sorted(set(arr))
    ranks = {value: rank for rank, value in enumerate(arr, 1)}
    return [ranks[num] for num in arr]

Explanation:

We can solve this by finding the sorted unique order of elements in arr. This will tell us how many unique ranks there are (since equal elements have the same rank).

Then we use a dictionary to correspond value in arr and rank using 1-indexed enumeration.

Then we just return the associated rank arr.

def arrayRankTransform(arr):
  unique_elts = sorted(set(arr))
  ranks = {value: rank for rank, value in enumerate(arr, 1)}
  return [ranks[num] for num in arr]

The time complexity is O(n). set() takes O(n) time, sorted takes O(m log m) time, where m = len(set(arr)). Ranks dictionary takes O(n) time to construct.

The space complexity is O(n). We need to store the resulting ranks in an array of the same size as the original arr.

The full solution can be found near the top of the page.