LeetCode 168: Excel Sheet Column Title Solution in Python Explained

Problem Statement

In LeetCode 168, you’re given a positive integer columnNumber. Your task is to convert it to its corresponding Excel sheet column title, where:

• 1 maps to "A", 2 to "B", ..., 26 to "Z".
• 27 to "AA", 28 to "AB", and so on, like a base-26 number system (but 1-based, not 0-based).

The result is a string of uppercase letters. This differs from two-sum problems like LeetCode 167: Two Sum II - Input Array Is Sorted, focusing on number-to-string conversion rather than pair finding.

Constraints

• 1 <= columnNumber <= 2^31 - 1

Example

Let’s see some cases:

Copy codeInput: columnNumber = 1
Output: "A"
Explanation: 1 maps directly to "A".

Copy codeInput: columnNumber = 28
Output: "AB"
Explanation: 28 = 1*26 + 2, maps to "AB" (1→A, 2→B).

Copy codeInput: columnNumber = 701
Output: "ZY"
Explanation: 701 = 26*26 + 25, maps to "ZY" (26→Z, 25→Y).

These examples show we’re converting numbers to base-26 titles.

Understanding the Problem

How do you solve LeetCode 168: Excel Sheet Column Title in Python? Take columnNumber = 1. It’s simply "A". For 28, it’s 126 + 2, so "AB" (A=1, B=2). For 701, it’s 2626 + 25, so "ZY" (Z=26, Y=25). This is a base-26 system, but unlike standard base conversion (0-based), Excel uses 1-26 for A-Z, requiring adjustment (e.g., subtract 1 before dividing). This isn’t a decimal task like LeetCode 166: Fraction to Recurring Decimal; it’s about integer-to-letter mapping. We’ll use: 1. Base-26 Conversion with String Building: O(log n) time, O(1) space—our best solution. 2. Recursive Base-26 Conversion: O(log n) time, O(log n) space—an alternative.

Let’s dive into the best solution.

Best Solution: Base-26 Conversion with String Building Approach

Explanation

Base-26 Conversion with String Building converts the number iteratively:

• Adjust for 1-based indexing by subtracting 1 from columnNumber.
• Repeatedly:
• Take the remainder modulo 26 to get the current digit (0-25 → A-Z).
• Prepend the corresponding letter to the result.
• Divide by 26 for the next iteration.
• Build the string from right to left.

This achieves O(log n) time complexity (n = columnNumber, logarithmic due to division by 26), O(1) space (excluding output), and simplicity by avoiding recursion.

For 28:

• 28-1=27, 27%26=1 (B), 27//26=1.
• 1-1=0, 0%26=0 (A), 0//26=0, stop.
• Build: "B" → "AB".

Step-by-Step Example

Example 1: columnNumber = 1

Goal: Return "A".

• Start: result = "", n = 1.
• Step 1: n-1 = 0, digit = 0 % 26 = 0, chr(65+0) = 'A', result = "A", n = 0 // 26 = 0.
• Step 2: n = 0, stop.
• Finish: Return "A".

Example 2: columnNumber = 28

Goal: Return "AB".

• Start: result = "", n = 28.
• Step 1: n-1 = 27, digit = 27 % 26 = 1, 'B', result = "B", n = 27 // 26 = 1.
• Step 2: n-1 = 0, digit = 0 % 26 = 0, 'A', result = "AB", n = 0 // 26 = 0.
• Step 3: n = 0, stop.
• Finish: Return "AB".

Example 3: columnNumber = 701

Goal: Return "ZY".

• Start: result = "", n = 701.
• Step 1: n-1 = 700, digit = 700 % 26 = 24, 'Y', result = "Y", n = 700 // 26 = 26.
• Step 2: n-1 = 25, digit = 25 % 26 = 25, 'Z', result = "ZY", n = 25 // 26 = 0.
• Step 3: n = 0, stop.
• Finish: Return "ZY".

How the Code Works (Base-26 Conversion with String Building) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef convertToTitle(columnNumber: int) -> str:
    # Line 1: Initialize result
    result = ""
    # Empty string to build title (e.g., "")

    # Line 2: Convert to base-26
    while columnNumber > 0:
        # Continue until number is 0 (e.g., 28)

        # Line 3: Adjust for 1-based indexing
        columnNumber -= 1
        # Shift to 0-based (e.g., 28→27)

        # Line 4: Get current digit
        digit = columnNumber % 26
        # Remainder gives digit (e.g., 27 % 26 = 1)

        # Line 5: Convert to letter and prepend
        result = chr(65 + digit) + result
        # Map to A-Z and add (e.g., 'B' + "" = "B")

        # Line 6: Divide for next iteration
        columnNumber //= 26
        # Next digit (e.g., 27 // 26 = 1)

    # Line 7: Return final title
    return result
    # e.g., "AB"

This detailed breakdown clarifies how base-26 conversion with string building efficiently creates the title.

Alternative: Recursive Base-26 Conversion Approach

Explanation

Recursive Base-26 Conversion uses recursion to build the title:

• Base case: If columnNumber ≤ 26, return the letter directly.
• Recursive case: Compute the remainder and quotient, recurse on the quotient, append the remainder’s letter.

It’s a practical alternative, O(log n) time (recursive calls), O(log n) space (recursion stack), but less efficient due to stack overhead.

For 28:

• 28→1 (A), 27%26=1 (B), "A" + "B" = "AB".

Step-by-Step Example (Alternative)

For 701:

• Step 1: 701→26 (Z), 25 (Y), return "Z" + "Y".
• Finish: Return "ZY".

How the Code Works (Recursive)

Copy codedef convertToTitleRecursive(columnNumber: int) -> str:
    if columnNumber <= 26:
        return chr(64 + columnNumber)
    quotient = (columnNumber - 1) // 26
    remainder = columnNumber % 26 or 26
    return convertToTitleRecursive(quotient) + chr(64 + remainder)

Complexity

• Base-26 Conversion with String Building:
• Time: O(log n) – divisions by 26.
• Space: O(1) – constant space (excluding output).
• Recursive Base-26 Conversion:
• Time: O(log n) – recursive calls.
• Space: O(log n) – recursion stack.

Efficiency Notes

Base-26 Conversion with String Building is the best solution with O(log n) time and O(1) space, offering efficiency and simplicity—Recursive Base-26 Conversion matches time complexity but uses O(log n) space due to recursion, making it elegant but less space-efficient.

Key Insights

• Base-26: A-Z mapping.
• Iterative: Builds directly.
• Recursive: Calls stack up.

Additional Example

For columnNumber = 52:

• Goal: "AZ".
• Iterative: 52-1=51, 51%26=25 (Z), 51//26=1, 1-1=0 (A), "AZ".

Edge Cases

• Single Letter: 1 → "A".
• Boundary: 26 → "Z".
• Large: 702 → "ZZ".

Both solutions handle these well.

Final Thoughts

LeetCode 168: Excel Sheet Column Title in Python is a fun number-to-string challenge. The Base-26 Conversion with String Building solution excels with its efficiency and clarity, while Recursive Base-26 Conversion offers a recursive twist. Want more? Try LeetCode 171: Excel Sheet Column Number for the reverse problem or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 168 on LeetCode with 28, aiming for "AB"—test your skills now!