SEO PACKAGE

1. SEO Title

Rank Transform of an Array in Python — LeetCode 1331 Explained with Sort, Set & Hash Map

2. SEO Subtitle

Learn how to replace every number with its rank in O(n log n) using sorting, a set for duplicates, and a hash map for instant lookups.

3. Featured Quote

"Sort once to learn the ranks, then look them up forever — that single pattern quietly powers half the array problems you'll ever meet."

4. Meta Description

Solve LeetCode 1331 Rank Transform of an Array in Python. Learn sorting, sets, and hash maps to rank numbers in O(n log n) with clean, interview-ready code.

5. URL Slug

rank-transform-of-an-array-python-leetcode-1331

6. Keywords

rank transform of an array, leetcode 1331, python hash map, python dictionary, python set, sorting algorithm python, coding interview python, o(n log n) sorting, rank array problem, enumerate python, coordinate compression, data structures python, array ranking algorithm, python list comprehension, binary search python, leetcode easy python, hash map lookup, unique values python, sort a copy python, python interview questions

7. Tags

Python, LeetCode, Coding Interview, Data Structures, Algorithms, Hash Map, Sorting, Sets, Software Engineering, Problem Solving, Array Problems, Beginner Python, Interview Prep, Coordinate Compression

---

Rank Transform of an Array: The Sort → Map → Look Up Pattern Every Developer Should Own

8. Introduction

Some coding problems look trivial until a duplicate value quietly breaks your first attempt. Rank Transform of an Array (LeetCode 1331) is exactly that kind of problem — deceptively simple, but a great teacher. It hands you an array of integers and asks you to replace each value with its rank: the smallest becomes 1, the next distinct value becomes 2, and so on.

Interviewers love this problem because it tests three fundamental skills at once: choosing the right data structures, reasoning about duplicates, and preserving the original order of the input. None of those are hard on their own, but combining them cleanly separates engineers who reach for the right tool from those who brute-force their way through.

If you're learning hash maps and sorting patterns for coding interviews, this is one of the highest-return problems you can study. The technique you'll learn here — sort the unique values, map each to its rank, then look everything up in O(1) — shows up again and again in real interview questions. Master it once, reuse it forever.

9. Problem Overview

You're given an integer array arr. Return a new array of the same length where each element is replaced by its rank, following three rules:

1. Rank starts at 1. The smallest value in the array is rank 1.
2. Larger values get larger ranks. If one value is bigger than another, its rank is bigger too.
3. Equal values share a rank, and ranks have no gaps. Two identical numbers must get the same rank, and the ranks are as small as possible — no numbers are skipped.

The output must line up with the original positions of the input. If arr[0] was the largest value, then answer[0] must hold the largest rank. You are transforming values in place, not sorting the array.

10. Example

Let's start with a clean, no-duplicates case.

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

Rank each value by size:

Value	Size order	Rank
10	smallest	1
20	2nd	2
30	3rd	3
40	largest	4

Now write those ranks back into the original positions. 40 sat at index 0, so rank 4 goes to index 0.

Output: [4, 1, 2, 3]

Notice the shape of the output matches the shape of the input — only the values changed.

Now the twist that trips people up:

Input: arr = [100, 100, 100]

All three values are equal, so they all share rank 1. There are no gaps, so we do not produce [1, 2, 3].

Output: [1, 1, 1]

This is the heart of the problem: duplicates must not consume extra ranks. That single requirement is why a plain "sort and count position" approach fails, and why we need a set.

11. Intuition

Here's how an experienced engineer arrives at the answer without writing a line of code first.

Picture lining up a group of people from shortest to tallest. Once they're in order, each person's position in the line is their rank. The shortest person is 1st, the next is 2nd, and so on. Numbers work the same way: if you sort them, a value's position in the sorted list is its rank.

But two problems appear immediately:

• Duplicates. If two people are the same height, they should share a rank — so before lining up, collapse duplicates into a single entry. That's a set: it automatically keeps only unique values.
• Original order. The answer has to match where each value started. If we sort the input array itself, we destroy that information. So we sort a copy off to the side, learn the ranks there, and leave the original untouched.

Once we know each value's rank, we don't want to search for it every time. We want to ask and instantly get the answer. That's a hash map (a Python dict): store value → rank, then every lookup is O(1).

So the full insight is: sort the unique values to learn the ranks, store them in a hash map, then walk the original array and swap each value for its rank.

12. Brute Force Solution

Idea: For each element, count how many distinct values are less than or equal to it. That count is its rank.

Algorithm:

1. For each element x in arr, scan the entire array.
2. Count how many unique values are ≤ x.
3. That count is the rank of x.

def array_rank_transform_brute(arr):
    unique = set(arr)
    result = []
    for x in arr:
        rank = sum(1 for u in unique if u <= x)
        result.append(rank)
    return result

Advantages:

• Requires almost no cleverness; easy to reason about correctness.
• Naturally handles duplicates because it counts unique values.

Disadvantages:

• For every element we rescan all unique values → quadratic work.
• Far slower than necessary; will time out on large inputs.

Time complexity: O(n²) — for each of n elements we scan up to n unique values. Space complexity: O(n) for the set of unique values.

13. Optimal Solution

We can do dramatically better by sorting once and reusing that work.

Step 1 — Drop duplicates. Convert the array to a set so equal values collapse into one entry. This guarantees duplicates share a rank.

Step 2 — Sort the unique values. Sorting lines them up smallest to largest. Now each value's index in the sorted list tells us its rank.

Step 3 — Build the rank map. Walk the sorted unique values with enumerate, which hands out positions starting at 0. Since ranks start at 1, we add 1.

Sorted unique	Index (enumerate)	Rank (index + 1)
10	0	1
20	1	2
30	2	3
40	3	4

Step 4 — Look up each original value. Walk the original array in order. For each value, ask the hash map for its rank — an instant O(1) lookup — and collect the answers.

Because both copies of a duplicated value query the same hash map, they both receive the same rank. The duplicate problem solves itself.

14. Python Code

def array_rank_transform(arr):
    # Sort the unique values so each position reveals its rank.
    rank = {value: i + 1 for i, value in enumerate(sorted(set(arr)))}

    # Replace each original element with its rank via O(1) lookups.
    return [rank[value] for value in arr]

The verbose, loop-based version — identical logic, easier to read while learning:

def array_rank_transform(arr):
    rank = {}
    for i, value in enumerate(sorted(set(arr))):
        rank[value] = i + 1  # ranks start at 1

    result = []
    for value in arr:
        result.append(rank[value])
    return result

15. Code Walkthrough

• set(arr) — removes duplicates so equal values are represented once. Without this, duplicates would each grab a distinct position and violate the "shared rank, no gaps" rule.
• sorted(...) — orders the unique values from smallest to largest. This is the single step that actually computes the ranks; everything else is bookkeeping.
• enumerate(...) — pairs each sorted value with its position i, starting at 0.
• i + 1 — shifts from zero-based indexing to one-based ranks.
• The dict comprehension — builds {value: rank}, our instant lookup table.
• [rank[value] for value in arr] — walks the original array in its original order, swapping each value for its rank. Order is preserved because we iterate arr directly, not the sorted copy.

16. Dry Run

Let's trace arr = [40, 10, 20, 40] (note the duplicate 40).

1. set(arr) → {40, 10, 20} — the two 40s collapse into one.
2. sorted(...) → [10, 20, 40].
3. Build the map:
   • enumerate gives (0, 10), (1, 20), (2, 40).
   • rank = {10: 1, 20: 2, 40: 3}.
4. Look up each original value:

Original value	Position in input	rank[value]
40	0	3
10	1	1
20	2	2
40	3	3

Output: [3, 1, 2, 3] — both 40s correctly received rank 3, and the original order is intact.

17. Complexity Analysis

Time complexity: O(n log n).

• set(arr) is O(n).
• sorted(...) is O(n log n) — this dominates everything else.
• Building the map is O(n); the final lookups are O(n) total (each lookup is O(1)).
• Sum: O(n) + O(n log n) + O(n) = O(n log n).

Space complexity: O(n).

• The set holds up to n unique values.
• The hash map holds up to n key-value pairs.
• The result list holds n elements.

The sort is the bottleneck, and no rank-transform solution can beat O(n log n) in the comparison model — you fundamentally have to order the values to know their ranks.

18. Alternative Solutions

Binary search instead of a hash map. Keep the sorted unique list, but skip building the map. For each value, run a binary search (bisect) to find its position in the sorted list — that position is its rank.

from bisect import bisect_left

def array_rank_transform_bisect(arr):
    ordered = sorted(set(arr))
    return [bisect_left(ordered, value) + 1 for value in arr]

Comparison:

Aspect	Hash map	Binary search
Time	O(n log n)	O(n log n)
Per-lookup cost	O(1)	O(log n)
Extra memory	O(n) map	Still needs sorted list
Code clarity	Simplest	Fiddlier to get right

Both are O(n log n) because sorting dominates. The binary-search version saves the memory of the map, but it still needs the sorted list, so the savings are tiny — and every lookup now costs a small search instead of being instant.

When to pick which? Almost always pick the hash map: same speed, simpler code. Reach for binary search only when memory is extremely tight.

19. Edge Cases

• Empty array [] — the set is empty, the map is empty, the comprehension iterates zero times, and we return []. No crash, no special case needed.
• All duplicates [7, 7, 7] — the set collapses to {7}, giving rank = {7: 1}, so the output is [1, 1, 1]. Correct by construction.
• Single element [5] — sorts to [5], maps to {5: 1}, returns [1].
• Negative numbers [-9, 0, -3] — sorting already knows -9 < -3 < 0, so ranks come out right with zero extra handling.
• Extreme values — the largest and smallest 32-bit integers sort correctly in Python, which uses arbitrary-precision integers.

The clean solution survives every edge case for free precisely because it leans on set and sorted to do the hard thinking.

20. Common Mistakes

1. Sorting the original array in place. This destroys the mapping between values and their positions, so you can no longer rebuild the answer in original order. Always sort a copy.
2. Forgetting the set. Ranking positions of the raw sorted array gives duplicates different ranks ([1, 2, 3] instead of [1, 1, 1]).
3. Off-by-one on the rank. enumerate starts at 0, but ranks start at 1. Forgetting + 1 shifts every rank down by one.
4. Rebuilding the map inside the loop. Constructing the rank lookup once is O(n log n); rebuilding it per element balloons to O(n² log n).
5. Assuming input is non-empty. A naive min/max-based approach can crash on []; the set-and-sort approach handles it silently.

21. Interview Questions

Likely follow-ups after you solve this:

• What's the time complexity, and which step dominates? (O(n log n), the sort.)
• Can you do it without extra space? (Not meaningfully — you need the sorted order, which itself costs space or destroys the input.)
• How would you handle streaming input where the array doesn't fit in memory?
• What if ranks needed to start at 0, or count from the largest value down?
• This is coordinate compression — where else have you seen this technique?

22. Similar Problems

• LeetCode 1122 — Relative Sort Array: also remaps values based on ordering, reinforcing the sort-and-map idea.
• LeetCode 1046 — Last Stone Weight: uses ordering of values (via a heap) to drive the result.
• LeetCode 315 — Count of Smaller Numbers After Self: a harder cousin built on ranking and coordinate compression.
• LeetCode 220 — Contains Duplicate III: relies on ordered structures and bucketing, close relatives of sorting-based ranking.

These share the core skill: use ordering to assign meaning to values, then look those meanings up efficiently.

23. Key Takeaways

• Sort once, then reuse. The expensive step is the sort; everything after is cheap O(1) or O(n) work.
• Sets handle duplicates for free. Collapse equal values before ranking so they share a rank with no gaps.
• Hash maps turn "search" into "ask." Precompute value → rank and every lookup becomes instant.
• Never mutate the input when order matters. Sort a copy so you can rebuild the answer in original position.
• The sort → map → look up pattern is one of the most reusable tools in your interview toolkit.

24. Watch the Video

Prefer to see the intuition build step by step — the lockers, the guest list, the phone book, and the duplicate twist drawn out visually? Watch the full walkthrough here: {LINK}. It's the fastest way to lock in the sort-and-map pattern before your next interview.

25. About the Series

This is part of the Daily Python LeetCode series, where we solve one interview problem a day in clean, readable Python. Every post builds intuition before code, explains why each approach works, and connects the problem to the broader patterns interviewers actually test. No memorization — just durable understanding you can carry from one problem to the next.

26. Call To Action

If this helped the pattern click:

• Subscribe on YouTube so you never miss a daily solution.
• Subscribe to the Substack for the written deep-dives and code you can copy.
• Comment with the approach you used — brute force, hash map, or binary search.
• Share this with a friend who's grinding LeetCode for interviews.

---

SOCIAL MEDIA

LinkedIn Post

Rank Transform of an Array (LeetCode 1331) looks trivial: replace each number with its rank. Then a duplicate shows up and quietly breaks the naive solution.

Here's what makes it a great interview problem — it tests three skills at once:

1. Choosing the right data structure
2. Handling duplicates correctly
3. Preserving the original order of the input

The clean approach is a pattern worth memorizing:

→ Put the values in a set to drop duplicates (equal values must share a rank). → Sort the unique values — now each position is the rank. → Store value → rank in a hash map for O(1) lookups. → Walk the original array and swap each value for its rank.

Total cost: O(n log n), dominated entirely by the sort.

Two details that separate strong candidates:

• We sort a copy, never the original — otherwise we lose track of where each value belongs in the output. • Duplicates solve themselves. Both copies query the same map and get the same rank.

The "sort once, then look up" pattern shows up constantly — coordinate compression, relative sorting, counting problems. Learn it here and you'll reuse it for years.

What's your default: hash map or binary search on the sorted list?

#Python #LeetCode #CodingInterview #DataStructures #Algorithms #SoftwareEngineering

Twitter/X Thread

1/ LeetCode 1331 "Rank Transform of an Array" looks trivial — until a duplicate breaks your first solution.

Here's the clean O(n log n) Python approach every dev should know. 🧵

2/ The task: replace each number with its rank. Smallest → 1, next → 2, and so on.

[40, 10, 20, 30] → [4, 1, 2, 3]

The output keeps the original order. Only the values change.

3/ The twist that trips people up:

[100, 100, 100] → [1, 1, 1]

NOT [1, 2, 3].

Equal values share a rank, with no gaps. Remember this — it drives the whole solution.

4/ Key insight: if you line numbers up smallest → largest, each value's POSITION is its rank.

Sort them, and ranking is basically free.

5/ But two problems: • Duplicates should share a rank → use a SET to drop them first. • We must keep original order → sort a COPY, never the input itself.

6/ Once we know the ranks, we don't want to search every time. Store value → rank in a hash map (Python dict). Every lookup is O(1).

7/ The whole thing in two lines:

rank = {v: i+1 for i, v in enumerate(sorted(set(arr)))}
return [rank[v] for v in arr]

8/ Why duplicates just work: both copies of a value query the SAME map, so both get the SAME rank. No special handling.

9/ Complexity: • Time: O(n log n) — the sort dominates. • Space: O(n) — set + map + result.

You can't beat O(n log n): you fundamentally must order the values.

10/ The "sort → map → look up" pattern shows up all over interviews (coordinate compression, relative sort, counting problems).

Learn it once, reuse it forever. Save this thread. 🔖

Facebook Post

Ever hit a coding problem that looks easy… until a duplicate value quietly breaks your solution? 😅

That's LeetCode 1331, "Rank Transform of an Array." You replace each number with its rank — smallest gets 1, next gets 2, and so on. Simple, right? Then you see [100, 100, 100] and realize all three must share rank 1, not 1-2-3.

The clean fix uses just three tools you already know: a set to drop duplicates, sorting to learn the ranks, and a hash map for instant lookups. Sort once, then look up each value — done in O(n log n).

The best part: it's a pattern you'll reuse in tons of other interview problems. Full step-by-step walkthrough in the video and article. Give it a watch and let me know how you'd solve it! 👇

Reddit Summary

Rank Transform of an Array (LC 1331) — the sort/set/hashmap pattern, and why duplicates matter

Quick writeup for anyone practicing array problems.

The task: replace each element with its rank (smallest = 1). Output keeps the original order.

The gotcha most people miss: duplicates must share a rank with no gaps. [100,100,100] → [1,1,1], not [1,2,3].

Clean approach:

1. set(arr) to drop duplicates (equal values share one rank).
2. sorted(...) the unique values — position now equals rank.
3. Build a {value: rank} dict for O(1) lookups.
4. Walk the original array, swap each value for its rank.

def array_rank_transform(arr):
    rank = {v: i + 1 for i, v in enumerate(sorted(set(arr)))}
    return [rank[v] for v in arr]

Time O(n log n) (sort dominates), space O(n).

Two things worth noting:

• Sort a copy, not the input — you need original positions to build the answer.
• There's a bisect-based variant that skips the map, but it's O(log n) per lookup and still needs the sorted list, so the memory savings are marginal. Hash map is simpler and just as fast.

Edge cases (empty array, all duplicates, negatives) all fall out for free because set + sorted do the heavy lifting. Curious if anyone uses the binary-search version in practice, or if it's always hashmap for you.

---

GITHUB README

# Rank Transform of an Array — LeetCode 1331 (Python)

Replace every element of an array with its **rank**: the smallest value becomes 1,
the next distinct value becomes 2, and equal values share the same rank with no gaps.
The output preserves the original order.

## Problem

Given an integer array `arr`, return an array of the same length where each element
is replaced by its rank.

- Rank starts at 1.
- Larger values get larger ranks.
- Equal values get the same rank, and ranks have no gaps.

**Example 1**

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

**Example 2**

Input: [100, 100, 100] Output: [1, 1, 1] # duplicates share a rank

## Intuition

Line the numbers up from smallest to largest — each value's position in that line
is its rank. Two adjustments make it correct:

- **Duplicates** should share a rank → drop them with a `set` first.
- **Original order** must be preserved → sort a *copy*, never the input.

Once ranks are known, store `value → rank` in a hash map so every lookup is O(1).

## Approach

1. `set(arr)` — remove duplicates so equal values share one rank.
2. `sorted(...)` — order the unique values; position reveals the rank.
3. Build a `{value: rank}` map with `enumerate` (add 1 since ranks start at 1).
4. Walk the original array and replace each value with its rank via O(1) lookups.

## Python Solution

```python
def array_rank_transform(arr):
    # Sort unique values so each position reveals its rank.
    rank = {value: i + 1 for i, value in enumerate(sorted(set(arr)))}

    # Replace each original element with its rank via O(1) lookups.
    return [rank[value] for value in arr]

Binary-search alternative (skips the map, O(log n) per lookup):

from bisect import bisect_left

def array_rank_transform(arr):
    ordered = sorted(set(arr))
    return [bisect_left(ordered, value) + 1 for value in arr]

Complexity

Metric	Value	Why
Time	O(n log n)	Sorting dominates; lookups are O(1) each
Space	O(n)	Set + hash map + result list

Edge Cases

• [] → []
• [7, 7, 7] → [1, 1, 1]
• Negative numbers sort correctly with no special handling.

Video

Watch the full walkthrough: {LINK}

Article

Read the detailed explanation with dry runs, diagrams, and common mistakes in the Daily Python LeetCode series. ```

def arrayRankTransform(arr):
    # unique values, smallest to largest
    unique_sorted = sorted(set(arr))

    # value -> rank, starting at 1
    ranks = {}
    for i, value in enumerate(unique_sorted):
        ranks[value] = i + 1