algoadvance

Leetcode 1331. Rank Transform of an Array

Problem Statement

Given an array of integers arr, replace each element with its rank. The rank represents how small the element is. The rank should be a number starting from 1 and representing the relative size of the element compared to the other elements in the array.

The rank should be calculated such that:

• The smallest element has rank 1.
• If two elements are equal, they should have the same rank.
• The rank should start from 1 and increase sequentially.

Example:

Input: arr = [40, 10, 20, 30]
Output: [4, 1, 2, 3]

Input: arr = [100, 100, 100]
Output: [1, 1, 1]

Input: arr = [37, 12, 28, 9, 100, 56, 80, 5, 12]
Output: [5, 3, 4, 2, 8, 6, 7, 1, 3]

Clarifying Questions

1. Are there any constraints on the size of the array?
   • The problem generally assumes that the array length is within a reasonable range for typical computation, like 1 to 10^5 elements.
2. Are the elements within a specific range of values?
   • For simplicity, it’s safe to assume that the elements are within the bounds of typical 32-bit integers (e.g., -10^9 to 10^9).
3. Do we need to handle empty arrays?
   • Usually, yes. If the input array is empty, the output should also be an empty array.

Strategy

To transform the array into ranks, the steps are:

1. Copy the array: Create a sorted version of the array.
2. Create a rank map: Assign ranks to each unique element in the sorted array.
3. Replace elements with ranks: Map each original element to its corresponding rank using the rank map.

Code

#include <vector>
#include <unordered_map>
#include <algorithm>

std::vector<int> arrayRankTransform(std::vector<int>& arr) {
    if (arr.empty()) {
        return {};
    }
    
    std::vector<int> sortedArr = arr;
    std::sort(sortedArr.begin(), sortedArr.end());
    
    std::unordered_map<int, int> rankMap;
    int rank = 1;
    
    for (const int& num : sortedArr) {
        if (rankMap.find(num) == rankMap.end()) {
            rankMap[num] = rank++;
        }
    }
    
    std::vector<int> result;
    result.reserve(arr.size());
    for (const int& num : arr) {
        result.push_back(rankMap[num]);
    }
    
    return result;
}

Time Complexity

• Copy and sort the array: O(n log n) where n is the number of elements in the array.
• Creating the rank map: O(n) since we iterate through the sorted array and create map entries.
• Mapping original elements to ranks: O(n) to iterate through the original array and construct the result.

Thus, the overall time complexity is O(n log n).

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?