Rank Transform of an Array

Easy

#1237Time: 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.

Algorithms

Sorting

Data structures

Array Hash Table

Prompt

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 <= 10⁵
-10⁹ <= arr[i] <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public int[] arrayRankTransform(int[] arr) {6        int n = arr.length;7        int[] result = new int[n];8 9        for (int i = 0; i < n; i++) {10            Set<Integer> smallerElements = new HashSet<>();11            for (int j = 0; j < n; j++) {12                if (arr[j] < arr[i]) {13                    smallerElements.add(arr[j]);14                }15            }16            result[i] = smallerElements.size() + 1;17        }18        return result;19    }20}

Complexity

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.

Trade-offs

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).

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.

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.

Walkthrough

This optimal approach consists of three main steps:

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.
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.
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.

1import java.util.Arrays;2import java.util.HashMap;3import java.util.Map;4 5class Solution {6    public int[] arrayRankTransform(int[] arr) {7        if (arr == null || arr.length == 0) {8            return new int[0];9        }10 11        // 1. Create a copy and sort it12        int[] sortedArr = arr.clone();13        Arrays.sort(sortedArr);14 15        // 2. Create a map to store ranks16        Map<Integer, Integer> rankMap = new HashMap<>();17        int rank = 1;18        for (int num : sortedArr) {19            // Use putIfAbsent or check with containsKey to handle duplicates20            if (!rankMap.containsKey(num)) {21                rankMap.put(num, rank);22                rank++;23            }24        }25 26        // 3. Build the result array by looking up ranks27        int[] result = new int[arr.length];28        for (int i = 0; i < arr.length; i++) {29            result[i] = rankMap.get(arr[i]);30        }31 32        return result;33    }34}

Complexity

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)).

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int[] arrayRankTransform(int[] arr) {4    int n = arr.length;5    int[] t = arr.clone();6    Arrays.sort(t);7    int m = 0;8    for (int i = 0; i < n; ++i) {9      if (i == 0 || t[i] != t[i - 1]) {10        t[m++] = t[i];11      }12    }13    int[] ans = new int[n];14    for (int i = 0; i < n; ++i) {15      ans[i] = Arrays.binarySearch(t, 0, m, arr[i]) + 1;16    }17    return ans;18  }19}

1class Solution {2public:3  vector<int> arrayRankTransform(vector<int> &arr) {4    vector<int> t = arr;5    sort(t.begin(), t.end());6    t.erase(unique(t.begin(), t.end()), t.end());7    vector<int> ans;8    for (int x : arr) {9      ans.push_back(upper_bound(t.begin(), t.end(), x) - t.begin());10    }11    return ans;12  }13};

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem