Encode and Decode TinyURL

MediumHash Tables · Design🧩 Hashing & Counting LeetCode #535 ↗Updated Oct 30, 2026

Problem

Build a URL shortener class Codec with encode(longUrl), which returns a short URL such as http://tinyurl.com/4e9iAk, and decode(shortUrl), which returns the original long URL. Any scheme is allowed as long as decode(encode(url)) always gives back url.

Inputencode("https://leetcode.com/x")Output"http://tinyurl.com/0"

Inputdecode("http://tinyurl.com/0")Output"https://leetcode.com/x"

1 ≤ url.length ≤ 10⁴ · url is a valid URL · decode is only called with URLs produced by encode on the same object

Try it yourself

Java

class Codec {
    public String encode(String longUrl) {
        
    }

    public String decode(String shortUrl) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A shortener is just a hash map from short key to long URL. The design choice is how to generate keys: short, unique, hard to guess, and ideally the same key for a repeated URL.

PatternHashing & Counting

Instinct Need "have I seen this before?", "how many times?" or "group things that look alike"? Trade memory for O(1) lookups with a HashMap, HashSet or int[26].

Memory hack Don't search, remember - every element checks in at the front desk, and the desk answers instantly.

Open the Hashing & Counting guide →

Approaches

Brute ForceIncrementing Integer ID

Time O(1) per callSpace O(N)

Give each new URL the next integer (0, 1, 2, ...) and store id → url. Decoding strips the prefix and parses the number. IDs are unique by construction, so no collisions can occur.

Java

class Codec {
    private static final String BASE = "http://tinyurl.com/";
    private final Map<Integer, String> map = new HashMap<>();
    private int id = 0;

    public String encode(String longUrl) {
        map.put(id, longUrl);
        return BASE + id++;
    }

    public String decode(String shortUrl) {
        return map.get(Integer.parseInt(shortUrl.substring(BASE.length())));
    }
}

Trivial and collision-free, but keys are guessable and the same URL gets new IDs.

BetterRandom 6-char Base62 Key

Time O(1) expectedSpace O(N)

Draw 6 random characters from [a-zA-Z0-9]: 62⁶ ≈ 5.7·10¹⁰ keys, so keys are short, fixed-length and not guessable. On the rare collision just redraw.

Java

class Codec {
    private static final String BASE = "http://tinyurl.com/";
    private static final String CHARS =
        "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    private final Map<String, String> map = new HashMap<>();
    private final Random rand = new Random();

    public String encode(String longUrl) {
        String key;
        do {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 6; i++) sb.append(CHARS.charAt(rand.nextInt(62)));
            key = sb.toString();
        } while (map.containsKey(key));   // retry on collision
        map.put(key, longUrl);
        return BASE + key;
    }

    public String decode(String shortUrl) {
        return map.get(shortUrl.substring(BASE.length()));
    }
}

Short, unpredictable keys; still stores duplicates when a URL is re-encoded.

OptimalRandom Base62 + Reverse Map

Time O(L) encode, O(1) decodeSpace O(N)

Add a second map url → key. Encoding a URL seen before returns its existing short link, so each distinct URL is stored once and encoding is idempotent. Hashing the long URL costs O(L), where L is its length.

Java

class Codec {
    private static final String BASE = "http://tinyurl.com/";
    private static final String CHARS =
        "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    private final Map<String, String> keyToUrl = new HashMap<>();
    private final Map<String, String> urlToKey = new HashMap<>();
    private final Random rand = new Random();

    public String encode(String longUrl) {
        String key = urlToKey.get(longUrl);
        if (key == null) {
            do {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < 6; i++) sb.append(CHARS.charAt(rand.nextInt(62)));
                key = sb.toString();
            } while (keyToUrl.containsKey(key));
            keyToUrl.put(key, longUrl);
            urlToKey.put(longUrl, key);
        }
        return BASE + key;
    }

    public String decode(String shortUrl) {
        return keyToUrl.get(shortUrl.substring(BASE.length()));
    }
}

Unguessable, fixed-length, deduplicated keys — what a real service does.

Pro tip

In a distributed system, swap Random for a global counter encoded in base62 — unique without collision checks.

At a glance

Level	Approach	Time	Space
Brute Force	Incrementing Integer ID	`O(1) per call`	`O(N)`
Better	Random 6-char Base62 Key	`O(1) expected`	`O(N)`
Optimal	Random Base62 + Reverse Map	`O(L) encode, O(1) decode`	`O(N)`

Common pitfalls

Using longUrl.hashCode() as the key — different URLs can collide.
Decoding with replace(BASE, "") — breaks if the prefix appears again; use substring.
Forgetting the collision check when generating random keys.

Interview tips

Clarify requirements: key length, guessability, and whether duplicates should share a key.
Estimate capacity: 62⁶ ≈ 56 billion keys for 6 characters.
Discuss scaling: persistent store, counter service, cache for hot keys.

Pattern

Bidirectional hash map design → issue compact IDs for large objects and look them up later.

My notes saved in this browser