# Rank Transform of an Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/rank-transform-of-an-array)
Canonical: https://scaleengineer.com/dsa/problems/rank-transform-of-an-array
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
---
## Problem
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.

**Example 1:**

**Input:** arr = [40,10,20,30]
**Output:** [4,1,2,3]
**Explanation**: 40 is the largest element. 10 is the smallest. 20 is the second smallest. 30 is the third smallest.

**Example 2:**

**Input:** arr = [100,100,100]
**Output:** [1,1,1]
**Explanation**: Same elements share the same rank.

**Example 3:**

**Input:** arr = [37,12,28,9,100,56,80,5,12]
**Output:** [5,3,4,2,8,6,7,1,3]

**Constraints:**

* `0 <= arr.length <= 105`
* `-109 <= arr[i] <= 109`

# Approaches
## Brute Force with Nested Loops
This approach uses a straightforward, brute-force method. For each element in the array, it performs a full scan of the array to count how many other unique elements are smaller. The rank is then determined by this count plus one. A `HashSet` is used to ensure that we only count unique smaller elements, which is crucial for handling duplicate values in the input array correctly.
**Time:** O(N^2), where N is the number of elements in the array. The outer loop runs N times, and for each iteration, the inner loop also runs N times. This results in a quadratic time complexity, which is too slow for large inputs. · **Space:** O(N), where N is the number of elements in the array. In the worst-case scenario (an array of unique, sorted numbers), the `HashSet` for the largest element will store N-1 elements.
**Pros:** Simple to understand and implement.; Does not require modifying the original array or creating a full copy for sorting.
**Cons:** Highly inefficient due to the nested loops, leading to a quadratic time complexity.; Will likely result in a 'Time Limit Exceeded' error on platforms like LeetCode for input sizes specified in the constraints (up to 10^5).
### Explanation
The core idea is to determine the rank of each number individually. To find the rank of a number `x`, we need to find out how many unique numbers in the entire array are smaller than `x`. If there are `k` such unique numbers, the rank of `x` will be `k + 1`.

We can implement this by iterating through the input array with an outer loop. For each element `arr[i]`, we use an inner loop to traverse the array again. Inside this inner loop, we use a `HashSet` to collect all elements `arr[j]` that are smaller than `arr[i]`. The `HashSet` automatically handles duplicates, so we get a count of unique smaller elements. The size of the set at the end of the inner loop gives us `k`. We then calculate the rank as `k + 1` and store it in our result array.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] arrayRankTransform(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];

        for (int i = 0; i < n; i++) {
            Set<Integer> smallerElements = new HashSet<>();
            for (int j = 0; j < n; j++) {
                if (arr[j] < arr[i]) {
                    smallerElements.add(arr[j]);
                }
            }
            result[i] = smallerElements.size() + 1;
        }
        return result;
    }
}
```
### Algorithm
- Create a `result` array of the same size as the input `arr`.
- Iterate through each element `arr[i]` from `i = 0` to `n-1` (where `n` is the length of `arr`):
  - For each `arr[i]`, initialize an empty `HashSet` called `smallerElements` to count the number of unique elements smaller than `arr[i]`.
  - Start a nested loop, iterating through each element `arr[j]` from `j = 0` to `n-1`.
  - Inside the nested loop, if `arr[j]` is less than `arr[i]`, add `arr[j]` to the `smallerElements` set.
  - After the inner loop completes, the number of unique smaller elements is `smallerElements.size()`.
  - The rank of `arr[i]` is `smallerElements.size() + 1`.
  - Assign this rank to `result[i]`.
- After the outer loop finishes, return the `result` array.

## Sorting with Hash Map
A much more efficient approach is to leverage sorting. The rank of an element is directly related to its position in a sorted list of the unique elements. This method first creates a sorted version of the array's unique elements to establish the ranks. It then uses a `HashMap` to store a mapping from each unique number to its calculated rank. Finally, it iterates through the original array, using the map to replace each element with its corresponding rank.
**Time:** O(N log N), where N is the number of elements. The dominant step is sorting the array copy. Building the rank map and the final result array both take O(N) time. Therefore, the total time complexity is governed by the sort. · **Space:** O(N), where N is the number of elements. We allocate space for a copy of the array (O(N)), the `HashMap` which can store up to N unique elements in the worst case (O(N)), and the result array (O(N)).
**Pros:** Efficient with a time complexity of O(N log N), which is suitable for the given constraints.; Correctly handles all ranking rules, including those for duplicate elements.; Considered the standard and optimal solution for this problem.
**Cons:** Requires extra space proportional to the input size for the array copy and the hash map.
### Explanation
This optimal approach consists of three main steps:

1.  **Sort:** We first need to understand the relative ordering of the numbers. The easiest way to do this is to create a copy of the input array and sort it. Sorting takes O(N log N) time.

2.  **Map Ranks:** After sorting, we can determine the rank of each unique number. We iterate through the sorted array and use a `HashMap` to store the first occurrence of each number with its rank. We start with rank 1. As we encounter new, unique numbers in the sorted array, we assign them the current rank and then increment the rank. Duplicates in the sorted array are skipped, ensuring they all share the same rank.

3.  **Transform:** Finally, we iterate through the original, unsorted array one last time. For each number, we look up its rank in the `HashMap` we created and build our final result array.

This process correctly assigns ranks according to the rules and is efficient enough to pass for large inputs.

```java
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] arrayRankTransform(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new int[0];
        }

        // 1. Create a copy and sort it
        int[] sortedArr = arr.clone();
        Arrays.sort(sortedArr);

        // 2. Create a map to store ranks
        Map<Integer, Integer> rankMap = new HashMap<>();
        int rank = 1;
        for (int num : sortedArr) {
            // Use putIfAbsent or check with containsKey to handle duplicates
            if (!rankMap.containsKey(num)) {
                rankMap.put(num, rank);
                rank++;
            }
        }

        // 3. Build the result array by looking up ranks
        int[] result = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            result[i] = rankMap.get(arr[i]);
        }

        return result;
    }
}
```
### Algorithm
- Create a copy of the input array, `arr`.
- Sort the copied array. This places all elements in ascending order.
- Initialize a `HashMap<Integer, Integer>` to store the rank of each unique number.
- Initialize a `rank` variable to 1.
- Iterate through the `sorted` array. For each number:
  - If the number is not already a key in the `HashMap`, it's the first time we've seen this unique value.
  - Add the number to the `HashMap` as a key, with the current `rank` as its value.
  - Increment the `rank` for the next unique number.
- Create a `result` array of the same size as the original `arr`.
- Iterate through the original `arr`. For each element `arr[i]`:
  - Look up its rank in the `HashMap`.
  - Store the retrieved rank in `result[i]`.
- Return the `result` array.

# Solutions
### Java

```java
class Solution {
public
  int[] arrayRankTransform(int[] arr) {
    int n = arr.length;
    int[] t = arr.clone();
    Arrays.sort(t);
    int m = 0;
    for (int i = 0; i < n; ++i) {
      if (i == 0 || t[i] != t[i - 1]) {
        t[m++] = t[i];
      }
    }
    int[] ans = new int[n];
    for (int i = 0; i < n; ++i) {
      ans[i] = Arrays.binarySearch(t, 0, m, arr[i]) + 1;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> arrayRankTransform(vector<int> &arr) {
    vector<int> t = arr;
    sort(t.begin(), t.end());
    t.erase(unique(t.begin(), t.end()), t.end());
    vector<int> ans;
    for (int x : arr) {
      ans.push_back(upper_bound(t.begin(), t.end(), x) - t.begin());
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def arrayRankTransform(self, arr: List[int]) -> List[int]: t = sorted(set(arr)) return [bisect_right(t, x) for x in arr]

```