LeetCode 168 - Excel Sheet Column Title

LeetCode Problem 168

Difficulty: 🟢 Easy
Topics: Math, String

Solution

Problem Understanding

The problem asks us to convert a positive integer into the column naming format used by Microsoft Excel. Excel labels columns alphabetically instead of numerically. The sequence begins as:

1  -> A
2  -> B
...
26 -> Z
27 -> AA
28 -> AB

The input, columnNumber, represents a 1-based column index. Our goal is to return the corresponding column title as a string.

At first glance, this resembles converting a number into base 26. However, there is an important difference from a normal positional numeral system. Standard base 26 uses digits from 0 to 25, but Excel columns use letters A through Z, which correspond to values 1 through 26. There is no representation for zero.

This means:

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

instead of:

A = 0
B = 1
...
Z = 25

The constraint is:

1 <= columnNumber <= 2^31 - 1

This tells us the input can be very large, so we need an efficient logarithmic solution. Since each division by 26 reduces the number significantly, the resulting string length is small, at most around 7 characters for the maximum 32-bit integer.

Several edge cases are important:

• Values exactly divisible by 26, such as 26, 52, or 702, are tricky because there is no zero digit.
• The smallest input, 1, should correctly map to "A".
• Boundary transitions like 26 -> Z, 27 -> AA, and 52 -> AZ are common sources of off-by-one errors.
• Very large numbers must still work efficiently without overflow issues.

Approaches

Brute Force Approach

A brute force approach would simulate Excel column generation sequentially. We could start from "A" and repeatedly generate the next column title until reaching the target number.

For example:

1  -> A
2  -> B
...
26 -> Z
27 -> AA

This method is correct because it directly follows the ordering Excel uses. However, it is extremely inefficient for large inputs. If columnNumber is close to 2^31 - 1, generating billions of intermediate strings would be infeasible.

The time complexity would be proportional to the input value itself, making it far too slow.

Optimal Approach

The optimal solution treats the problem as a modified base-26 conversion.

The key observation is that Excel columns behave like a 1-indexed numeral system. In normal base conversion, digits range from 0 to base - 1. Here, letters represent values from 1 to 26.

To handle this cleanly, we subtract 1 before each modulo operation.

The process works like this:

1. Subtract 1 from the current number.
2. Compute (columnNumber - 1) % 26 to determine the current character.
3. Convert the remainder into a letter:

• 0 -> A
• 25 -> Z

4. Divide (columnNumber - 1) by 26 to continue processing the next digit.

Because we extract characters from right to left, we reverse the result at the end.

This approach is efficient because each iteration reduces the number by a factor of 26.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(log n)	Generates every column title sequentially
Optimal	O(log₍26₎ n)	O(log₍26₎ n)	Uses modified base-26 conversion

Algorithm Walkthrough

1. Initialize an empty list called result.

We use a list because repeatedly appending characters to a string is less efficient in many languages. Each extracted character will represent one digit of the Excel column title. 2. Repeat while columnNumber > 0.

Each iteration processes one character of the final title. 3. Subtract 1 from columnNumber.

This is the most important step. Excel columns are 1-indexed instead of 0-indexed. Subtracting 1 converts the problem into a standard 0-based remainder system. 4. Compute the remainder using % 26.

The remainder determines which letter to use:

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

5. Convert the remainder into a character.

We use ASCII arithmetic:

chr(ord('A') + remainder)

6. Append the character to result.

The least significant character is produced first, so the characters are generated in reverse order. 7. Update columnNumber using integer division by 26.

This removes the processed digit and moves to the next position. 8. Reverse the collected characters and join them into a string.

Since characters were generated from right to left, reversing restores the correct order.

Why it works

The algorithm works because every iteration extracts exactly one base-26 digit from a 1-indexed numeral system. Subtracting 1 before modulo and division transforms the Excel representation into a standard zero-based positional representation. Repeating this process eventually decomposes the entire number into its corresponding sequence of letters.

Python Solution

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

        while columnNumber > 0:
            columnNumber -= 1

            remainder = columnNumber % 26
            character = chr(ord('A') + remainder)

            result.append(character)

            columnNumber //= 26

        return ''.join(reversed(result))

The implementation begins by creating an empty list called result to store the generated characters.

Inside the loop, we first decrement columnNumber by 1. This adjustment converts the Excel numbering scheme into a zero-based system that works naturally with modulo arithmetic.

Next, we compute the remainder when dividing by 26. This remainder identifies the current letter. We convert it into a character using ASCII arithmetic and append it to the result list.

After extracting the current digit, we divide the number by 26 using integer division to move to the next position.

Because characters are generated from least significant to most significant, the list is reversed before joining into the final string.

Go Solution

func convertToTitle(columnNumber int) string {
    result := []byte{}

    for columnNumber > 0 {
        columnNumber--

        remainder := columnNumber % 26
        character := byte('A' + remainder)

        result = append(result, character)

        columnNumber /= 26
    }

    // Reverse the slice
    for left, right := 0, len(result)-1; left < right; left, right = left+1, right-1 {
        result[left], result[right] = result[right], result[left]
    }

    return string(result)
}

The Go implementation follows the same logic as the Python version. The primary difference is that Go uses a []byte slice to efficiently store characters.

After constructing the characters in reverse order, the slice is reversed in place using a two-pointer approach. Finally, the byte slice is converted into a string.

Since the input constraint fits within a 32-bit signed integer, Go's standard int type is sufficient on modern systems.

Worked Examples

Example 1

Input:

columnNumber = 1

Step	columnNumber After Decrement	Remainder	Character	Result
1	0	0	A	["A"]

After reversing:

"A"

Example 2

Input:

columnNumber = 28

Step	columnNumber After Decrement	Remainder	Character	Result
1	27	1	B	["B"]
2	0	0	A	["B", "A"]

Reversing the list:

["A", "B"]

Final result:

"AB"

Example 3

Input:

columnNumber = 701

Step	columnNumber After Decrement	Remainder	Character	Result
1	700	24	Y	["Y"]
2	25	25	Z	["Y", "Z"]

Reversing:

["Z", "Y"]

Final result:

"ZY"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log₍26₎ n)	Each iteration divides the number by 26
Space	O(log₍26₎ n)	The output string stores one character per digit

The number of iterations equals the number of base-26 digits required to represent the input. Since the value shrinks by a factor of 26 each iteration, the runtime grows logarithmically with respect to the input size.

The space complexity comes from storing the output characters. No additional large data structures are used.

Test Cases

solution = Solution()

# Provided examples
assert solution.convertToTitle(1) == "A"      # Smallest valid input
assert solution.convertToTitle(28) == "AB"    # Standard two-letter case
assert solution.convertToTitle(701) == "ZY"   # Mixed two-letter case

# Single-letter boundaries
assert solution.convertToTitle(26) == "Z"     # Largest single-letter column
assert solution.convertToTitle(2) == "B"      # Simple single-letter conversion

# Transition to two letters
assert solution.convertToTitle(27) == "AA"    # First two-letter column
assert solution.convertToTitle(52) == "AZ"    # End of A-prefix range
assert solution.convertToTitle(53) == "BA"    # Start of B-prefix range

# Larger values
assert solution.convertToTitle(702) == "ZZ"   # Largest two-letter column
assert solution.convertToTitle(703) == "AAA"  # First three-letter column

# Maximum constraint stress test
assert solution.convertToTitle(2147483647) == "FXSHRXW"  # Maximum allowed input

Test	Why
1 -> "A"	Validates smallest input
26 -> "Z"	Checks exact divisibility by 26
27 -> "AA"	Verifies transition to two letters
28 -> "AB"	Standard multi-letter conversion
52 -> "AZ"	Tests end of a prefix block
53 -> "BA"	Tests beginning of next prefix block
701 -> "ZY"	Confirms mixed two-letter conversion
702 -> "ZZ"	Largest two-letter title
703 -> "AAA"	Transition to three letters
2147483647 -> "FXSHRXW"	Stress test for maximum input

Edge Cases

One important edge case occurs when the number is exactly divisible by 26. In a normal base-26 system, a remainder of zero would correspond to digit 0. Excel does not have a zero digit, so 26 must map to "Z" instead of "BA" or another incorrect value. The implementation handles this by subtracting 1 before applying modulo arithmetic.

Another critical edge case is the transition between digit lengths. For example, 26 -> Z and 27 -> AA. Many incorrect implementations produce "BA" for 27 because they fail to account for Excel's 1-based numbering system. The decrement step ensures the transition works correctly.

A third edge case involves very large inputs near the maximum constraint. Since the algorithm repeatedly divides by 26, the number of iterations remains small even for huge values. This guarantees efficient execution without performance problems.