1331. Rank Transform of an Array

Time: O(n log n)

Space: O(n)

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

1Create sorted unique array. Map value -> rank (1-indexed).
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

// 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?