Replace Elements by Their Rank

8
0

Given an array of N integers, transform each element into its rank based on its value in the array. The rank of an element is determined by its position in the sorted array of distinct elements, starting from 1.

Follow these rules while assigning ranks:

  • The smallest element receives rank 1.

  • Larger elements receive progressively higher ranks.

  • Equal elements must be assigned the same rank.

  • The relative order of elements in the original array must remain unchanged.

Return the resulting array containing the ranks of all elements.

Example 1

Input: arr = [40, 10, 30, 20, 50]

Output: [4, 1, 3, 2, 5]

Explanation:

Sorted unique array is [10, 20, 30, 40, 50].

Ranks: 10 → 1, 20 → 2, 30 → 3, 40 → 4, 50 → 5.

Replacing each element with its corresponding rank gives [4, 1, 3, 2, 5].

Example 2

Input: arr = [7, 3, 7, 2, 9, 3, 5]

Output: [4, 2, 4, 1, 5, 2, 3]

Explanation:

Sorted unique array is [2, 3, 5, 7, 9].

Ranks: 2 → 1, 3 → 2, 5 → 3, 7 → 4, 9 → 5.

Both occurrences of 7 receive rank 4, and both occurrences of 3 receive rank 2.

Replacing each element with its corresponding rank gives [4, 2, 4, 1, 5, 2, 3].

Brute Force Approach

Sorting the array makes it easier to compare elements and determine their ranks. So the most direct idea is to use the position of each element in the sorted order to assign its rank.

Since duplicate elements should have the same rank, only distinct elements need to be considered. Once the sorted unique elements are obtained, each element's rank can be found by checking its position in that array.

Algorithm

  • Create a copy of the original array and sort it in ascending order.

  • Create a separate array to store only distinct elements.

  • Traverse the sorted array and add an element only if it differs from the previous element.

  • Create an answer array of the same size as the original array.

  • Traverse the original array and perform a linear search for each element in the distinct array.

  • Assign the element's 1-based index as its rank.

  • Return the resulting answer array.

Dry Run

Replace Elements by Their Rank - Brute

Replace Elements by Their Rank - Brute

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to replace each array element with its rank.
vector<int> replaceWithRank(vector<int>& arr) {
// Create a sorted copy of the original array.
vector<int> sortedArr = arr;
sort(sortedArr.begin(), sortedArr.end());
// Store only distinct elements in the sorted array.
vector<int> uniqueArr;
// Traverse the sorted array and remove duplicates.
for (int i = 0; i < sortedArr.size(); i++) {
// Add the element if it is the first or differs from the previous one.
if (i == 0 || sortedArr[i] != sortedArr[i - 1]) {
uniqueArr.push_back(sortedArr[i]);
}
}
// Store the ranks corresponding to the original elements.
vector<int> ans;
// Find the rank of each element using linear search.
for (int i = 0; i < arr.size(); i++) {
// Search for the current element in the unique array.
for (int j = 0; j < uniqueArr.size(); j++) {
// Assign the 1-based index when the element is found.
if (arr[i] == uniqueArr[j]) {
ans.push_back(j + 1);
break;
}
}
}
return ans;
}
};
// Driver code starts
int main() {
Solution obj;
vector<int> arr = {7, 3, 7, 2, 9, 3, 5};
vector<int> ans = obj.replaceWithRank(arr);
// Print the resulting rank array.
for (int x : ans) {
cout << x << " ";
}
return 0;
}

Complexity Analysis

Let N be the number of elements in the input array and U be the number of distinct elements, where U ≤ N.

  • Time Complexity: O(N²), where sorting the array takes O(N log N), removing duplicates takes O(N), and finding the rank of each element using linear search takes O(N × U) in the worst case. Since U can be equal to N, the overall complexity is O(N²).

  • Space Complexity: O(N), as additional arrays are used to store the sorted elements, distinct elements, and resulting ranks.

Optimal Approach

Sorting the array gives the elements in increasing order, so their ranks can be assigned based on their positions. However, searching for each element separately takes extra time, especially when the array contains many elements.

A better way is to store the rank of each distinct element in a hash map. This allows the corresponding rank to be retrieved directly, avoiding repeated linear searches. Duplicate elements are automatically assigned the same rank because each distinct value is stored only once.

Algorithm

  • Create a copy of the original array and sort it in ascending order.

  • Create a hash map to store each distinct element and its corresponding rank.

  • Initialize the rank with 1.

  • Traverse the sorted array:

    • If the current element is not already present in the hash map, assign the current rank to it.

    • Increment the rank after assigning it to a new element.

  • Create an answer array of the same size as the original array.

  • Traverse the original array and retrieve the corresponding rank of each element from the hash map.

  • Store the retrieved ranks in the answer array and return it.

Dry Run

Replace Elements by Their Rank - Optimal

Replace Elements by Their Rank - Optimal

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to replace each array element with its rank.
vector<int> replaceWithRank(vector<int>& arr) {
// Create a sorted copy of the original array.
vector<int> sortedArr = arr;
sort(sortedArr.begin(), sortedArr.end());
// Store the rank of each distinct element.
unordered_map<int, int> rankMap;
// Initialize the rank starting from 1.
int rank = 1;
// Traverse the sorted array and assign ranks.
for (int i = 0; i < sortedArr.size(); i++) {
// Assign a rank only if the element is not already present.
if (rankMap.find(sortedArr[i]) == rankMap.end()) {
rankMap[sortedArr[i]] = rank;
rank++;
}
}
// Store the ranks corresponding to the original elements.
vector<int> ans;
// Retrieve the rank of each element using the hash map.
for (int i = 0; i < arr.size(); i++) {
ans.push_back(rankMap[arr[i]]);
}
return ans;
}
};
// Driver code starts
int main() {
Solution obj;
vector<int> arr = {7, 3, 7, 2, 9, 3, 5};
vector<int> ans = obj.replaceWithRank(arr);
// Print the resulting rank array.
for (int x : ans) {
cout << x << " ";
}
return 0;
}

Complexity Analysis

  • Time Complexity: O(Nlog(N)), where N is the number of elements in the input array. Sorting takes O(Nlog(N)), while assigning ranks and retrieving them using the hash map take O(N) time each on average. Therefore, sorting dominates the overall time complexity.

  • Space Complexity: O(N), where N is the number of elements in the input array. The sorted copy, hash map, and answer array require linear additional space.

Interview follow-up Questions

Sorting arranges the elements in ascending order, making it easy to determine their relative positions. Without sorting, the rank of an element cannot be assigned directly based on its position in the original array.

ArraysSortingTCS NQT

Read Similar Blogs

Comments0