Sponsored
Sponsored
This approach involves sorting the array to determine the rank of each element. After sorting, unique elements are mapped to their ranks.
Time Complexity: O(N log N) due to sorting.
Space Complexity: O(N) for storing the sorted array and rank map.
1import java.util.*;
2
3class Solution {
4 public int[] arrayRankTransform(int[] arr) {
5 int[] sorted = arr.clone();
6 Arrays.sort(sorted);
7
8 Map<Integer, Integer> rankMap = new HashMap<>();
9 int rank = 1;
10 for (int num : sorted) {
11 if (!rankMap.containsKey(num)) {
12 rankMap.put(num, rank++);
13 }
14 }
15
16 for (int i = 0; i < arr.length; i++) {
17 arr[i] = rankMap.get(arr[i]);
18 }
19 return arr;
20 }
21}The Java solution utilizes sorting and a HashMap to track the ranks. Unique elements are assigned ranks as they appear in the sorted order, then mapped back to the original array positions.
Coordinate compression is a method to map large ranges of numbers to smaller ranges, maintaining their relative order. This approach uses this idea to assign ranks.
Time Complexity: O(N log N) due to sorting and binary search operations.
Space Complexity: O(N) for rank maps.
1def arrayRankTransform(arr):
2 sorted_arr =
Coordinate compression in this Python solution involves using sorting and a dictionary for mapping ranks. The sorted elements guide the rank allocation to the array with minimal memory use.