Excel Sheet Column Title - Decoding Base-26 Conversion

Today, we're tackling "Excel Sheet Column Title" (LeetCode #168).

This problem asks us to convert a given integer columnNumber into its corresponding Excel column title (like A, B, Z, AA, AB, etc.). While it looks like a simple base conversion, there's a unique characteristic that requires a slight adjustment to the standard algorithm. Let's decode this base-26 puzzle!

---

Understanding the Problem:

We are given an integer columnNumber (e.g., 1, 2, 26, 27, 28). Our task is to return its corresponding column title as it appears in an Excel sheet.

The mapping is as follows:

• A -> 1

• B -> 2

• C -> 3

• ...

• Z -> 26

• AA -> 27

• AB -> 28

• ...

• AZ -> 52

• BA -> 53

• ...

Notice how it behaves like a base-26 system, but with a crucial difference: there's no '0' equivalent. 'Z' represents 26, not 0, and it acts as the "last digit" in a place value. This is often called a "1-indexed base-26" system.

Examples:

• Input: columnNumber = 1

  • Output: "A"

• Input: columnNumber = 28

  • Output: "AB" (26 * 1 + 2)

• Input: columnNumber = 52

  • Output: "AZ" (26 * 1 + 26)

• Input: columnNumber = 701

  • Output: "ZY" (26 * 26 + 25)

---

My Thought Process & Approach (Modified Base-26 Conversion):

At first glance, this problem screams "base conversion!" It's similar to converting a decimal number to binary (base-2) or hexadecimal (base-16) using repeated division and modulo operations.

The Standard Base Conversion Algorithm: To convert a decimal number N to base B:

1. The last digit is N % B.

2. The remaining number is N / B.

3. Repeat until N becomes 0.

4. The digits are read in reverse order of generation.

The "Excel Twist": The challenge here is the 1-based indexing (A=1, Z=26) and the absence of a '0' digit. In a standard base-26 system, if val % 26 were 0, it would correspond to the 0th digit. But in Excel's system, 26 maps to Z, not some 'A-1'.

Consider columnNumber = 26:

• Standard: 26 % 26 = 0 (digit 0), 26 / 26 = 1. Then 1 % 26 = 1 (digit 1), 1 / 26 = 0. This would give "BA" (1,0) if A was 1 and B was 2. This is incorrect. We want "Z".

The Fix: When val % 26 results in 0, it actually means the current "digit" should be 'Z' (representing the 26th letter). When this happens, we must treat 26 as the "remainder," and crucially, we must "borrow" from the next higher place value by decrementing the val before dividing it by 26. This handles the 'Z' case correctly, where Z effectively carries over a full '26' to the next 'column'.

Here's the refined logic:

1. Initialize val = columnNumber, alph = 26, and an empty StringBuilder sb.

2. Loop while val is not 0:

   • Calculate last = val % alph. This is our potential digit.

   • If last == 0: This is the special case for 'Z'.

     • Append 'Z' to sb.

     • Decrement val by 1 (val--). This is the "borrow" to correctly handle the carry-over from 'Z' in the next division.

   • Else (last != 0): This is a standard digit.

     • Append the character (char)('A' + (last - 1)) to sb. (e.g., if last is 1, A + (1-1) gives 'A').

   • Divide val by alph (val = val / alph) to move to the next higher place value.

3. After the loop, the StringBuilder sb contains the characters in reverse order (e.g., for 28 -> B then A). Reverse sb to get the final title.

4. Convert sb to String and return it.

This iterative process correctly converts the 1-indexed number to its Excel column title.

---

Java Code Implementation:

class Solution {
    public String convertToTitle(int columnNumber) {
        int val = columnNumber;
        int alph = 26;
        StringBuilder sb = new StringBuilder();
        while(val!=0){
            int last = val%alph;
            if(last == 0) {sb.append('Z'); val--;}
            else sb.append((char)('A' + (last-1)));
            val = val/alph;
        }
        sb = sb.reverse();
        return sb.toString();
    }
}

Time and Space Complexity Analysis:

• Time Complexity: O(log{26} N)

  • In each iteration of the while loop, the val is divided by 26. This means the number of iterations is proportional to the logarithm base 26 of the input columnNumber (N).

  • Operations inside the loop (modulo, division, append) are constant time.

  • The StringBuilder.reverse() and toString() operations take time proportional to the length of the resulting string, which is also O(log{26} N).

  • Therefore, the total time complexity is O(log{26} N).

• Space Complexity: O(log{26} N)

  • The StringBuilder stores the characters of the resulting column title. The length of this title is proportional to O(log{26} N).

  • No other data structures are used whose size depends on the input N.

  • Therefore, the space complexity is O(log{26} N).