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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int[] ArrayRankTransform(int[] arr) {
6 int[] sorted = (int[])arr.Clone();
7 Array.Sort(sorted);
8
9 Dictionary<int, int> rankMap = new Dictionary<int, int>();
10 int rank = 1;
11 foreach (int num in sorted) {
12 if (!rankMap.ContainsKey(num)) {
13 rankMap[num] = rank++;
14 }
15 }
16
17 for (int i = 0; i < arr.Length; i++) {
18 arr[i] = rankMap[arr[i]];
19 }
20 return arr;
21 }
22}The C# solution uses sorting and a Dictionary to establish a rank map. The sorted array allows ranks to be assigned, which are then used to transform the original array.
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.