LeetCode 168: Excel Sheet Column Title

Problem Restatement

We are given a positive integer:

columnNumber

We need to return the corresponding Excel column title.

Excel columns are labeled like this:

The problem asks us to convert an integer into this Excel-style column label. The constraint is 1 <= columnNumber <= 2^31 - 1.

Input and Output

Example function shape:

def convertToTitle(columnNumber: int) -> str:
    ...

Examples

Example 1:

columnNumber = 1

Output:

"A"

Example 2:

columnNumber = 26

Output:

"Z"

Example 3:

columnNumber = 28

The title is:

"AB"

Example 4:

columnNumber = 701

The title is:

"ZY"

First Thought: Base 26

This looks like base conversion.

In normal base 26, digits would be:

0, 1, 2, ..., 25

But Excel columns use:

A, B, C, ..., Z

where:

A = 1
B = 2
...
Z = 26

There is no digit for zero.

That means this is not ordinary base 26. It is a 1-indexed, or bijective, base-26 system.

The fix is simple: subtract 1 before taking modulo 26.

Key Insight

For each character, do:

columnNumber -= 1
remainder = columnNumber % 26

Now the remainder is between 0 and 25.

We can map it to a letter:

0 -> "A"
1 -> "B"
...
25 -> "Z"

Then divide by 26:

columnNumber //= 26

This extracts the title from right to left.

So we collect characters, then reverse them at the end.

Why We Subtract One

Consider:

columnNumber = 26

If we use normal modulo:

26 % 26 = 0

That would suggest "A" if we mapped 0 to "A", which is wrong.

The answer should be "Z".

So before modulo, use:

columnNumber -= 1

Now:

25 % 26 = 25

and 25 maps to "Z".

This same trick also handles 27:

27 - 1 = 26
26 % 26 = 0 -> "A"
26 // 26 = 1
1 - 1 = 0
0 % 26 = 0 -> "A"

Collected from right to left, this gives:

"AA"

Algorithm

Initialize an empty list:

chars = []

While columnNumber > 0:

1. Subtract 1 from columnNumber.
2. Compute columnNumber % 26.
3. Convert that remainder to a letter.
4. Append the letter to chars.
5. Divide columnNumber by 26.

Finally, reverse chars and join it.

Walkthrough

Use:

columnNumber = 28

First iteration:

columnNumber -= 1     # 27
remainder = 27 % 26   # 1
letter = "B"
columnNumber = 27 // 26  # 1

Collected:

["B"]

Second iteration:

columnNumber -= 1     # 0
remainder = 0 % 26    # 0
letter = "A"
columnNumber = 0 // 26  # 0

Collected:

["B", "A"]

Reverse:

["A", "B"]

Return:

"AB"

Correctness

The algorithm repeatedly extracts the last Excel digit.

Before each modulo operation, it subtracts 1, converting Excel’s 1-based digit system into a 0-based range from 0 to 25.

The remainder then uniquely determines the last letter of the current title.

After extracting that letter, integer division by 26 removes the last Excel digit and leaves the remaining prefix to be processed.

The loop continues until no prefix remains.

Because digits are extracted from right to left, reversing the collected letters gives the title in the correct left-to-right order.

Therefore, the algorithm returns the correct Excel column title.

Complexity

Let k be the number of letters in the output.

Since columnNumber is at most 2^31 - 1, k is small.

Implementation

class Solution:
    def convertToTitle(self, columnNumber: int) -> str:
        chars = []

        while columnNumber > 0:
            columnNumber -= 1

            remainder = columnNumber % 26
            chars.append(chr(ord("A") + remainder))

            columnNumber //= 26

        chars.reverse()
        return "".join(chars)

Code Explanation

Create a list to store letters:

chars = []

The loop runs until the whole number has been converted:

while columnNumber > 0:

Convert from 1-based Excel digits to 0-based modulo digits:

columnNumber -= 1

Find the current letter index:

remainder = columnNumber % 26

Convert it to a character:

chars.append(chr(ord("A") + remainder))

Move to the next higher digit:

columnNumber //= 26

The letters were collected from right to left, so reverse them:

chars.reverse()

Return the final title:

return "".join(chars)

Recursive Implementation

The same logic can be written recursively:

class Solution:
    def convertToTitle(self, columnNumber: int) -> str:
        if columnNumber == 0:
            return ""

        columnNumber -= 1

        prefix = self.convertToTitle(columnNumber // 26)
        current = chr(ord("A") + columnNumber % 26)

        return prefix + current

The iterative version is usually preferable because it avoids recursion overhead.

Testing

def run_tests():
    sol = Solution()

    assert sol.convertToTitle(1) == "A"
    assert sol.convertToTitle(2) == "B"
    assert sol.convertToTitle(26) == "Z"
    assert sol.convertToTitle(27) == "AA"
    assert sol.convertToTitle(28) == "AB"
    assert sol.convertToTitle(52) == "AZ"
    assert sol.convertToTitle(53) == "BA"
    assert sol.convertToTitle(701) == "ZY"
    assert sol.convertToTitle(702) == "ZZ"
    assert sol.convertToTitle(703) == "AAA"

    print("all tests passed")

run_tests()