Rank Transform of an Array

EASY

Description

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

Checkout 2 different approaches to solve Rank Transform of an Array. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: 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 and Cons

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

Code Solutions

Checking out 3 solutions in different languages for Rank Transform of an Array. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Rank Transform of an Array

Algorithms:

Sorting

Data Structures:

ArrayHash Table