Rank Transform of an Array - Solution & Explanation

Problem Overview: Given an integer array, replace every element with its rank after sorting the values in ascending order. The smallest value gets rank 1. Equal values share the same rank, and ranks increase only when the value changes.

Approach 1: Sorting and Ranking (O(n log n) time, O(n) space)

This approach sorts the unique values and assigns ranks incrementally. Start by copying the array and sorting it. Then iterate through the sorted list and build a hash table that maps each number to its rank. Only assign a new rank when the current value differs from the previous value so duplicates receive the same rank. Finally, iterate through the original array and replace each value with its stored rank using constant-time hash lookups.

The key insight is separating ordering from mapping. Sorting determines the rank order, while the hash map allows quick translation back to the original positions. This approach works well for most cases and keeps the implementation simple. Time complexity comes from sorting the array (O(n log n)) and the additional passes are linear.

Approach 2: Using Coordinate Compression (O(n log n) time, O(n) space)

Coordinate compression reduces large or scattered values into a compact rank range. First, copy the array and sort it. Remove duplicates from the sorted list so you only keep unique values. Each unique value’s index in this sorted list determines its rank (index + 1). Store these mappings in a dictionary and then transform the original array by replacing each element with its compressed coordinate (rank).

This method is conceptually similar to the first approach but emphasizes the compression idea commonly used in competitive programming and sorting problems. It is especially useful when the input values are very large or sparse but you only care about relative ordering. By compressing them into ranks, you reduce the value domain without losing ordering information.

Both methods rely on sorting to establish global ordering and use a array traversal to rebuild the result. The difference is mainly conceptual: the first focuses on ranking while the second frames the process as coordinate compression.

Recommended for interviews: The sorting + hash map solution is the most direct and the one interviewers typically expect. It clearly demonstrates understanding of ordering, duplicate handling, and efficient lookups. Mentioning coordinate compression shows deeper algorithmic awareness, especially in problems involving large ranges or index remapping.