Problem Overview

You are given:

• A string longUrl

Your task is to design a system that:

• Encodes the given long URL into a shorter URL (TinyURL format)

• Decodes the shortened URL back into the original URL

Each encoded URL looks like:

http://tinyurl.com/{code}

Where:

• {code} is a unique identifier for each original URL

You must implement:

• encode(longUrl) → returns a shortened URL

• decode(shortUrl) → returns the original long URL

It is guaranteed that:

• Every shortUrl passed to decode() was generated by the same system instance

This problem is popular in interviews because it tests:

• Hash maps (key-value storage)

• String manipulation

• Unique ID generation

• System design intuition (mapping real-world services like URL shorteners)

• Reverse lookup design thinking

Example

Input:

url = "https://leetcode.com/problems/design-tinyurl"

Process:

encode(url) → "http://tinyurl.com/0"
decode(encoded_url) → original url

Approach 1: Brute Force Idea

Idea:

We could try to generate random short strings every time and search for collisions.

Disadvantages:

• Collision handling becomes complex

• Harder to guarantee uniqueness

• Slower lookup in worst cases

Best Approach: Hash Map + Unique ID Generator

Core Observation

We need a one-to-one mapping:

• long URL → short URL

• short URL → long URL

So we store:

id → longUrl

Then we generate:

shortUrl = baseUrl + id

Data Structure Used

We use:

unordered_map<int, string> mp;
int id = 0;

Where:

• mp[id] stores the original URL

• id acts as a unique counter

Encoding Process

For every new URL:

mp[id] = longUrl;
return "http://tinyurl.com/" + to_string(id++);

So each URL gets a unique numeric code.

Decoding Process

Given a short URL:

Example:

http://tinyurl.com/5

Steps:

1. Extract the number after last /

2. Convert it to integer key

3. Lookup original URL in map

key = 5
return mp[5]

Step-by-Step Example

Input

encode("https://leetcode.com/problems/design-tinyurl")

Step 1: Store Mapping

mp[0] = "https://leetcode.com/problems/design-tinyurl"

Step 2: Return Short URL

http://tinyurl.com/0

Decode Step

Input:

http://tinyurl.com/0

Extract:

key = 0

Lookup:

mp[0]

Return:

https://leetcode.com/problems/design-tinyurl

Why This Works

Key insight:

We don’t need to “compress” URLs mathematically.

We only need:

• A unique identifier

• A fast reversible mapping

So we convert the problem into:

“Store + retrieve using a hash map”

Time and Space Complexity

Time Complexity

• encode() → O(1)

• decode() → O(1)

Space Complexity

• O(n) where n is number of URLs stored

Final Code (Optimized)

class Solution {
public:
    unordered_map<int, string> mp;
    int id = 0;

    string encode(string longUrl) {
        mp[id] = longUrl;
        return "http://tinyurl.com/" + to_string(id++);
    }

    string decode(string shortUrl) {
        int pos = shortUrl.find_last_of('/');
        int key = stoi(shortUrl.substr(pos + 1));
        return mp[key];
    }
};