Problem Description

The Excel Sheet Column Title problem asks you to convert a given positive integer columnNumber into its corresponding column title as it appears in Microsoft Excel. For example, Excel columns are labeled as A, B, ..., Z, AA, AB, ..., AZ, BA, and so on.

Constraints:

• 1 ≤ columnNumber ≤ 2³¹ - 1
• The solution must be unique for each input.
• Each column title uses only uppercase English letters.

Example:
Input: columnNumber = 28
Output: AB

Thought Process

At first glance, this problem looks similar to converting a number into a different base, like base-26 for the 26 letters of the alphabet. However, there is a twist: Excel columns do not have a zero digit, so 'A' represents 1, not 0, and 'Z' represents 26. After 'Z', the next column is 'AA', not 'BA'.

A brute-force approach might try to build up the string from 1 to columnNumber, but that is inefficient and unnecessary. Instead, we need to figure out how to map the number to its title directly, similar to converting to base-26, but with an offset because there is no zero.

The main insight is to repeatedly find the rightmost letter by taking (columnNumber - 1) % 26, map that to a character, and then reduce columnNumber by dividing by 26 (after subtracting 1). We keep doing this until columnNumber is zero.

Solution Approach

To solve the problem, we treat the input as a special base-26 number system without a zero digit. Here’s how we proceed:

1. Initialize an empty string: This will store the resulting column title in reverse order.
2. Repeat until columnNumber becomes zero:
   • Subtract 1 from columnNumber to adjust for the 1-based indexing.
   • Find the remainder when dividing by 26: remainder = (columnNumber - 1) % 26.
   • Convert the remainder to a letter: chr(remainder + ord('A')) in Python (or similar in other languages).
   • Prepend this letter to the result string.
   • Update columnNumber to (columnNumber - 1) // 26.
3. Return the result string: This is your final column title.

This approach is efficient because it processes each "digit" of the title in one pass, similar to base conversion.

Example Walkthrough

Let's work through the example where columnNumber = 28:

1. First iteration:
   • columnNumber = 28
   • Subtract 1: 27
   • Remainder: 27 % 26 = 1
   • Corresponds to letter: 'B' (since 0 is 'A')
   • Update columnNumber: 27 // 26 = 1
2. Second iteration:
   • columnNumber = 1
   • Subtract 1: 0
   • Remainder: 0 % 26 = 0
   • Corresponds to letter: 'A'
   • Update columnNumber: 0 // 26 = 0
3. Result: Prepending the letters gives 'AB'.

Code Implementation

class Solution:
    def convertToTitle(self, columnNumber: int) -> str:
        result = []
        while columnNumber > 0:
            columnNumber -= 1
            result.append(chr(ord('A') + columnNumber % 26))
            columnNumber //= 26
        return ''.join(reversed(result))
      

class Solution {
public:
    string convertToTitle(int columnNumber) {
        string result = "";
        while (columnNumber > 0) {
            columnNumber--;
            char c = 'A' + (columnNumber % 26);
            result = c + result;
            columnNumber /= 26;
        }
        return result;
    }
};
      

class Solution {
    public String convertToTitle(int columnNumber) {
        StringBuilder sb = new StringBuilder();
        while (columnNumber > 0) {
            columnNumber--;
            char c = (char)('A' + columnNumber % 26);
            sb.append(c);
            columnNumber /= 26;
        }
        return sb.reverse().toString();
    }
}
      

var convertToTitle = function(columnNumber) {
    let result = '';
    while (columnNumber > 0) {
        columnNumber--;
        result = String.fromCharCode('A'.charCodeAt(0) + (columnNumber % 26)) + result;
        columnNumber = Math.floor(columnNumber / 26);
    }
    return result;
};
      

Time and Space Complexity

Brute-force Approach:

• Building up all titles from 1 to columnNumber would take O(N) time and space, which is infeasible for large columnNumber.

• The loop runs once for each "digit" in the base-26 representation of columnNumber. Since the number of digits is O(log₂₆N), this is O(log N) time.
• Space complexity is also O(log N) for the result string.

Both time and space are efficient, since the number of letters in the answer grows slowly as columnNumber increases.

Summary

The Excel Sheet Column Title problem is a variation of base conversion, with the twist that there's no zero digit. By adjusting the input at each step and mapping remainders to letters, we can efficiently build the column title in O(log N) time and space. The key insight is to subtract 1 before modulo and division, aligning the mapping with Excel's 1-indexed system. This makes the solution both elegant and efficient.