DDSA Solutions

1331. Rank Transform of an Array

UnknownView on LeetCode
ArrayHash TableSorting
Time: O(n log n)
Space: O(n)

Problem Overview

The rank of an element is its position in the sorted unique values.

Intuition

The rank of an element is its position in the sorted unique values. Sort unique values, assign ranks 1,2,3,..., then replace each element.

Algorithm

  1. 1Create sorted unique array. Map value -> rank (1-indexed).
  2. 2Replace each element with its rank.

Common Pitfalls

  • •Duplicate values get the same rank. Rank is based on relative order among unique values.
1331.cs
C#
// Approach: Sort a deduplicated copy; build value-to-rank map; replace each element.
// Time: O(n log n) Space: O(n)

public class Solution
{
    public int[] ArrayRankTransform(int[] arr)
    {
        int[] sortedArr = (int[])arr.Clone();
        Dictionary<int, int> rank = new Dictionary<int, int>();

        Array.Sort(sortedArr);

        foreach (int a in sortedArr)
        {
            if (!rank.ContainsKey(a))
                rank[a] = rank.Count + 1;
        }

        for (int i = 0; i < arr.Length; ++i)
            arr[i] = rank[arr[i]];

        return arr;
    }
}
Was this solution helpful?

Related Problems