Rank Transform of an Array - Practice Coding Problems

Rank Transform of an Array - Problem

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.

Input & Output

Example 1 — Basic Case

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

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

💡 Note: 40 is the largest (rank 4), 10 is smallest (rank 1), 20 is second smallest (rank 2), 30 is third smallest (rank 3)

Example 2 — Duplicate Values

$ Input: arr = [100,100,100]

› Output: [1,1,1]

💡 Note: All elements are equal, so they all get the same rank 1 (smallest possible)

Example 3 — Mixed with Duplicates

$ Input: arr = [37,12,28,9,100,56,80,5,12]

› Output: [6,2,4,1,8,7,3,5,2]

💡 Note: Unique sorted values are [5,9,12,28,37,56,80,100] with ranks 1-8. Element 12 appears twice and both get rank 2

Constraints

0 ≤ arr.length ≤ 10⁵
-10⁹ ≤ arr[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Array

Original array with possibly duplicate values

Find Unique & Sort

Extract unique values and sort to determine rank order

Assign Ranks

Transform each element to its corresponding rank

Key Takeaway

🎯 Key Insight: Sort unique values first to establish the rank order, then map each element to its rank position

Asked in

a Amazon 15 f Facebook 12 G Google 8 M Microsoft 6

The key insight is to sort unique values first to establish rank order. The optimal approach extracts unique values, sorts them, creates a value-to-rank mapping, then transforms the original array. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Sort and Map Approach	O(n log n)	O(n)	Sort unique values first, create rank mapping, then transform original array
Brute Force - Count Smaller Elements	O(n³)	O(n)	For each element, count how many unique smaller elements exist to determine its rank

Sort and Map Approach — Algorithm Steps

Get unique values from array
Sort unique values to determine rank order
Create mapping: value → rank
Transform original array using mapping

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract Unique

Get unique values: {37, 12, 28}

Sort Values

Sort to get rank order: [12, 28, 37]

Create Mapping

Map each value to its rank position

Transform Array

Replace each element with its rank

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int* solution(int* arr, int arrSize, int* returnSize) {
    *returnSize = arrSize;
    
    // Get unique values
    int* uniqueValues = (int*)malloc(arrSize * sizeof(int));
    int uniqueCount = 0;
    
    for (int i = 0; i < arrSize; i++) {
        int found = 0;
        for (int j = 0; j < uniqueCount; j++) {
            if (uniqueValues[j] == arr[i]) {
                found = 1;
                break;
            }
        }
        if (!found) {
            uniqueValues[uniqueCount++] = arr[i];
        }
    }
    
    // Sort unique values
    qsort(uniqueValues, uniqueCount, sizeof(int), compare);
    
    // Transform original array using mapping
    int* result = (int*)malloc(arrSize * sizeof(int));
    for (int i = 0; i < arrSize; i++) {
        for (int j = 0; j < uniqueCount; j++) {
            if (arr[i] == uniqueValues[j]) {
                result[i] = j + 1;
                break;
            }
        }
    }
    
    free(uniqueValues);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int arr[1000];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        arr[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(arr, size, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting unique values takes O(k log k) where k ≤ n, plus O(n) to build result

⚡ Linearithmic

Space Complexity

O(n)

Hash map stores up to n unique values, plus result array

⚡ Linearithmic Space

89.4K Views

Medium Frequency

~12 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort and Map Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler