Scale Engineer

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
ArrayHash 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 <= 105
  • -109 <= arr[i] <= 109

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.

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

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

Solutions

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

Next problem