• Posts

Problem 1331 Rank Transform of an Array

Problem Statement

Link - Problem 1331

Question

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

Solution

class Solution {
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        map<int,int>ind;
        vector<int>temp = arr;
        sort(temp.begin(),temp.end());
        int rank = 1;
        for(int i=0; i<temp.size(); i++){
            if(i>0 && temp[i]>temp[i-1])
                rank++;

            ind[temp[i]] = rank;
        }

        for(int i=0; i<arr.size(); i++)
            arr[i] = ind[arr[i]];

        return arr;
    }
};

Complexity Analysis

| Algorithm        | Time Complexity | Space Complexity |
| ---------------- | --------------- | ---------------- |
| Modified Sorting | O(n log n)      | O(n)             |

Explanation

Intial Thoughts

The problem requires replacing each element in the array with its rank. To solve this, think of ranking students based on their scores, where students with the same score get the same rank, and the next student with a higher score gets a rank that’s one more than the previous highest rank. This requires sorting and then mapping each unique score to its corresponding rank. Consider using a data structure that allows for efficient sorting and mapping, such as arrays or hash maps.

Intuitive Analysis

Intuitively, solve this problem by sorting the array and assigning ranks to each unique element. Think of a ladder where each rung represents a rank, and elements with the same value are on the same rung. The next element with a higher value climbs to the next rung, and the rank increases accordingly. Break down the solution into steps, such as creating a temporary sorted array, mapping each unique element to its rank, and finally replacing each element in the original array with its corresponding rank. Consider the constraints and how they affect the solution, such as the array size and the range of element values.

1. Intuition

• The problem requires replacing each element in the array with its rank, where the rank represents how large the element is.
• To achieve this, we need to first understand the rules of ranking, which state that the rank should be an integer starting from 1, the larger the element, the larger the rank, and if two elements are equal, their rank must be the same.
• We also need to ensure that the rank is as small as possible, meaning that we should assign the smallest possible rank to each element while maintaining the rules.
• A key insight to solve this problem is to use a sorting approach, where we sort the array in ascending order and then assign ranks based on the sorted order.
• Another important aspect is to handle duplicate elements, where we assign the same rank to equal elements.
• The overall approach involves creating a mapping of elements to their corresponding ranks and then replacing each element in the original array with its rank.
• This solution works because it ensures that the rank is assigned based on the relative size of each element, and it handles duplicate elements correctly.

2. Implementation

• We start by creating a copy of the input array arr and sorting it in ascending order using the sort function.
• We then create a map called ind to store the mapping of elements to their corresponding ranks.
• We iterate through the sorted array and assign ranks to each element using the rank variable, incrementing the rank only when we encounter a larger element.
• We use the ind map to store the rank of each element, where the key is the element and the value is the rank.
• Finally, we iterate through the original array arr and replace each element with its corresponding rank from the ind map using arr[i] = ind[arr[i]].
• The function returns the modified array arr with the ranks assigned to each element.
• The use of a map for storing the element-rank mapping allows for efficient lookup and assignment of ranks, with an overall time complexity of O(n log n) due to the sorting step.

Complexity Analysis

Time Complexity:

• The time complexity is dominated by the sort(temp.begin(),temp.end()) operation, which has a time complexity of O(n log n) due to the use of a comparison-based sorting algorithm.
• Additional operations, such as the iteration over the temp vector and the population of the ind map, have a linear time complexity of O(n), but are overshadowed by the sorting operation.
• Therefore, the overall time complexity is O(n log n) due to the sorting step, which is the most computationally expensive part of the algorithm.

Space Complexity:

• The algorithm uses a map<int,int> called ind to store the ranks of the elements, which requires O(n) space in the worst case, as each element in the input array arr needs to be stored in the map.
• Additionally, a temporary vector temp is created to store the sorted elements, which also requires O(n) space.
• Overall, the space complexity is O(n) due to the use of the ind map and the temp vector, which both scale linearly with the size of the input array arr.

Footnote

This question is rated as Easy difficulty.

Hints

Use a temporary array to copy the array and sort it.

The rank of each element is the number of unique elements smaller than it in the sorted array plus one.

Similar Questions: