LeetCode 1331. Rank Transform of an Array Solution in Java, C++, Python & More | Explanation + Code

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

Solutions

Solution 1: Discretization

First, we copy an array t, then sort and deduplicate it to obtain an array of length m that is strictly monotonically increasing.

Next, we traverse the original array arr. For each element x in the array, we use binary search to find the position of x in t. The position plus one is the rank of x.

The time complexity is O(n × log n), and the space complexity is O(n). Here, n is the length of the array arr.

PythonJavaC++GoTypeScript

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

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; } }(code-box)

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; } };(code-box)

func arrayRankTransform(arr []int) (ans []int) { t := make([]int, len(arr)) copy(t, arr) sort.Ints(t) m := 0 for i, x := range t { if i == 0 || x != t[i-1] { t[m] = x m++ } } t = t[:m] for _, x := range arr { ans = append(ans, sort.SearchInts(t, x)+1) } return }(code-box)

function arrayRankTransform(arr: number[]): number[] { const t = [...arr].sort((a, b) => a - b); let m = 0; for (let i = 0; i < t.length; ++i) { if (i === 0 || t[i] !== t[i - 1]) { t[m++] = t[i]; } } const search = (t: number[], right: number, x: number) => { let left = 0; while (left < right) { const mid = (left + right) >> 1; if (t[mid] > x) { right = mid; } else { left = mid + 1; } } return left; }; const ans: number[] = []; for (const x of arr) { ans.push(search(t, m, x)); } return ans; }(code-box)

Solution 2: Sorting + Hash Map

TypeScriptJavaScript

function arrayRankTransform(arr: number[]): number[] { const sorted = [...new Set(arr)].sort((a, b) => a - b); const map = new Map<number, number>(); let c = 1; for (const x of sorted) { map.set(x, c++); } return arr.map(x => map.get(x)!); }(code-box)

function arrayRankTransform(arr) { const sorted = [...new Set(arr)].sort((a, b) => a - b); const map = new Map(); let c = 1; for (const x of sorted) { map.set(x, c++); } return arr.map(x => map.get(x)); }(code-box)