LeetCode 171 - Excel Sheet Column Number

This problem asks us to convert an Excel-style column title into its corresponding numerical index. In Excel spreadsheets, columns are labeled alphabetically: The labeling system works similarly to a positional number system, except instead of digits 0-9, it uses letters A-Z…

leetcodeeasymathstring

LeetCode Problem 171

Difficulty: 🟢 Easy
Topics: Math, String

Solution

Problem Understanding

This problem asks us to convert an Excel-style column title into its corresponding numerical index.

In Excel spreadsheets, columns are labeled alphabetically:

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

The labeling system works similarly to a positional number system, except instead of digits 0-9, it uses letters A-Z, where:

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

The input is a string called columnTitle, consisting only of uppercase English letters. The task is to compute the integer value represented by that title.

For example:

  • "A" corresponds to 1
  • "AB" corresponds to 28
  • "ZY" corresponds to 701

The important observation is that this behaves like a base-26 number system, but with one key difference: there is no zero digit. Instead:

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

This makes the conversion slightly different from standard hexadecimal or decimal conversion.

The constraints tell us that:

  • The string length is at most 7
  • Only uppercase letters appear
  • The largest possible value is "FXSHRXW"

Because the input size is extremely small, performance is not a concern. Even an O(n) solution is more than fast enough.

Important edge cases include:

  • A single-letter column such as "A" or "Z"
  • Multi-letter columns where carries occur, such as "AA" or "ZZ"
  • Very large valid inputs near the upper bound
  • Repeated characters, such as "AAA"

The problem guarantees valid input, so we do not need to handle invalid characters or lowercase letters.

Approaches

Brute Force Approach

A brute force solution would simulate the Excel numbering process from 1 upward, generating every possible column title until reaching the target string.

For example:

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

We could repeatedly generate titles and compare them against columnTitle. Once the generated title matches the input, we return the current number.

This approach is correct because it checks every valid column title in order. Eventually, the target string will be reached.

However, this method is extremely inefficient because generating and comparing every intermediate title wastes enormous amounts of work. Even though the constraints are small, the logic is unnecessarily complicated and much slower than needed.

Optimal Approach

The key insight is that Excel column titles behave like numbers in base 26.

For a title such as "AB":

A = 1
B = 2

AB = (1 * 26) + 2 = 28

For "ZY":

Z = 26
Y = 25

ZY = (26 * 26) + 25 = 701

This is identical to how decimal numbers are processed digit by digit:

345 = ((3 * 10) + 4) * 10 + 5

We process each character from left to right:

  1. Multiply the current result by 26
  2. Add the numeric value of the current letter

This produces the final column number efficiently in linear time.

Approach Time Complexity Space Complexity Notes
Brute Force O(k × n) O(n) Generates every column title until the target is found
Optimal O(n) O(1) Treats the string as a base-26 number

Here:

  • n is the length of columnTitle
  • k is the numerical value represented by the title

Algorithm Walkthrough

Optimal Algorithm

  1. Initialize a variable called result to 0.

This variable will store the progressively built column number. 2. Iterate through each character in columnTitle from left to right.

We process characters in order because this is a positional numbering system. 3. Convert the current letter into its numeric value.

Since:

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

we compute:

value = ord(character) - ord('A') + 1
  1. Multiply the current result by 26.

This shifts all previously processed characters one position to the left in the base-26 number system. 5. Add the current letter value to result.

This incorporates the new digit into the final number. 6. Continue until all characters are processed. 7. Return result.

Why it works

The algorithm works because Excel column titles form a positional numbering system with base 26.

At every step, the invariant is:

result = numeric value of all processed characters

Multiplying by 26 shifts previous digits left by one position, exactly like multiplying by 10 in decimal systems. Adding the current letter value appends the new digit correctly.

Because every character is processed exactly once and positional values are accumulated correctly, the final result is the exact column number.

Python Solution

class Solution:
    def titleToNumber(self, columnTitle: str) -> int:
        result = 0

        for character in columnTitle:
            value = ord(character) - ord('A') + 1
            result = result * 26 + value

        return result

The implementation begins by initializing result to 0.

The loop iterates through every character in columnTitle. For each character, we compute its alphabetical position using ASCII values. Since 'A' should map to 1, we subtract ord('A') and add 1.

The statement:

result = result * 26 + value

is the core of the algorithm. Multiplying by 26 shifts the existing digits left in the positional system, and adding value appends the current character.

After all characters are processed, result contains the final column number.

Go Solution

func titleToNumber(columnTitle string) int {
    result := 0

    for _, character := range columnTitle {
        value := int(character-'A') + 1
        result = result*26 + value
    }

    return result
}

The Go implementation follows the exact same logic as the Python version.

One small difference is that Go characters are handled as rune values during iteration. We convert the rune arithmetic result into an integer using:

int(character-'A') + 1

The problem constraints guarantee the result fits safely within Go's standard integer range, so no overflow handling is necessary.

Worked Examples

Example 1

Input:

columnTitle = "A"
Step Character Value Previous Result New Result
1 A 1 0 0 × 26 + 1 = 1

Final answer:

1

Example 2

Input:

columnTitle = "AB"
Step Character Value Previous Result New Result
1 A 1 0 0 × 26 + 1 = 1
2 B 2 1 1 × 26 + 2 = 28

Final answer:

28

Example 3

Input:

columnTitle = "ZY"
Step Character Value Previous Result New Result
1 Z 26 0 0 × 26 + 26 = 26
2 Y 25 26 26 × 26 + 25 = 701

Final answer:

701

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character is processed once
Space O(1) Only a few integer variables are used

The algorithm performs a single pass through the input string. Each iteration performs constant-time arithmetic operations, so the total runtime grows linearly with the string length.

The space usage remains constant because no auxiliary data structures are allocated.

Test Cases

solution = Solution()

assert solution.titleToNumber("A") == 1          # Smallest possible input
assert solution.titleToNumber("B") == 2          # Simple single-letter case
assert solution.titleToNumber("Z") == 26         # Largest single-letter column

assert solution.titleToNumber("AA") == 27        # First two-letter column
assert solution.titleToNumber("AB") == 28        # Basic two-letter example
assert solution.titleToNumber("AZ") == 52        # End of A-prefixed range

assert solution.titleToNumber("BA") == 53        # Transition after AZ
assert solution.titleToNumber("ZZ") == 702       # Largest two-letter column

assert solution.titleToNumber("AAA") == 703      # First three-letter column
assert solution.titleToNumber("ZY") == 701       # Provided example

assert solution.titleToNumber("FXSHRXW") == 2147483647  # Maximum constraint value
Test Why
"A" Verifies smallest valid input
"B" Verifies basic single-letter conversion
"Z" Verifies upper bound of single letters
"AA" Verifies transition from one digit to two digits
"AB" Verifies normal multi-character conversion
"AZ" Verifies handling of maximum trailing character
"BA" Verifies carry behavior after "AZ"
"ZZ" Verifies largest two-letter value
"AAA" Verifies transition into three letters
"ZY" Verifies provided example
"FXSHRXW" Verifies maximum allowed input

Edge Cases

Single Character Inputs

Inputs such as "A" or "Z" are important because they represent the simplest possible valid columns. A buggy implementation might incorrectly treat "A" as 0 instead of 1.

This implementation handles the issue correctly by explicitly mapping:

ord(character) - ord('A') + 1

which ensures "A" becomes 1.

Transition Between Digit Lengths

Cases such as "Z" to "AA" are common sources of off-by-one mistakes. Standard positional systems usually include a zero digit, but Excel columns do not.

The implementation avoids this issue because letters are mapped from 1 to 26 instead of 0 to 25.

Large Inputs Near the Constraint Limit

The maximum allowed input is "FXSHRXW", which equals 2147483647.

A naive implementation using floating-point arithmetic or inefficient recursion could introduce errors or overflow risks.

This solution uses only integer arithmetic and processes the string iteratively, so it safely handles the largest valid input.