algoadvance

Leetcode 1331. Rank Transform of an Array

Problem Statement

Given an array of integers arr, you will need to transform the array such that each element of the array will be replaced by its rank.

The rank represents how large the element is. The rank has the following rules:

Clarifying Questions

  1. Q: Are there any constraints on the size of the array? A: There is no specific constraint mentioned for the size of the array, but typically problems on LeetCode fit within reasonable memory and performance limits.

  2. Q: Can the array contain negative numbers? A: Yes, the array can contain negative numbers as there are no restrictions mentioned regarding the range of numbers.

  3. Q: What should be done if the array is empty? A: If the array is empty, we should return an empty array as there are no elements to rank.

Strategy

  1. Identify Unique Elements: Extract unique elements from the array.
  2. Sort Unique Elements: Sort these unique elements, as ranks are derived based on sorting.
  3. Assign Ranks: Use a hash map/dictionary to map each unique element to its respective rank.
  4. Transform the Array: Replace each element in the original array with its corresponding rank based on the hash map.

Code

import java.util.Arrays;
import java.util.HashMap;

public class Solution {
    public int[] arrayRankTransform(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new int[0];
        }

        int[] sortedArr = arr.clone();
        Arrays.sort(sortedArr);

        HashMap<Integer, Integer> rankMap = new HashMap<>();
        int rank = 1;
        for (int num : sortedArr) {
            if (!rankMap.containsKey(num)) {
                rankMap.put(num, rank++);
            }
        }

        int[] result = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            result[i] = rankMap.get(arr[i]);
        }

        return result;
    }
}

Time Complexity

  1. Sort the Array:
    • Sorting the array takes (O(n \log n)), where (n) is the number of elements in the array.
  2. Populate HashMap:
    • Populating the hash map takes (O(n)) as each insertion/check is on average (O(1)).
  3. Transform the Array:
    • Transforming the array (replacing each element with its rank) takes (O(n)).

Hence, the overall time complexity of the solution is (O(n \log n)).

This effectively solves the problem by ensuring all elements are ranked correctly based on their unique values and their respective sorted positions.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI