Excel Sheet Column Title
EasyPrompt
Given an integer columnNumber, return its corresponding column title as it appears in an Excel sheet.
For example:
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
...
Example 1:
Input: columnNumber = 1
Output: "A"Example 2:
Input: columnNumber = 28
Output: "AB"Example 3:
Input: columnNumber = 701
Output: "ZY"
Constraints:
1 <= columnNumber <= 231 - 1
Approaches
2 approaches with complexity analysis and trade-offs.
This approach treats the problem as a base conversion from base-10 to a modified base-26 system. A recursive function is a natural way to implement this. The key insight is that this isn't a standard base-26 system (with digits 0-25), but one with digits 1-26. To handle this, we can convert the number to a 0-indexed system at each step by subtracting 1 before performing the modulo and division operations. The function calculates the rightmost character and then calls itself to find the prefix.
Algorithm
The recursive solution is based on the idea of base conversion. The problem is equivalent to converting a number from base-10 to a special base-26 system where digits are 'A' through 'Z' (representing 1 through 26).
- Base Case: The recursion terminates when the
columnNumberbecomes 0. In this case, an empty string is returned. - Recursive Step: For any
columnNumber > 0: a. To handle the 1-based nature of Excel columns (A=1, Z=26) versus the 0-based nature of modulo arithmetic, we first decrementcolumnNumberby 1. This maps the range[1, 26]to[0, 25]. b. The last character of the Excel title corresponds to(columnNumber - 1) % 26. We convert this numeric value (0-25) to its character representation ('A'-'Z'). c. The preceding part of the title is found by recursively calling the function with the quotient(columnNumber - 1) / 26. d. The final result is constructed by concatenating the result of the recursive call (the prefix) with the character found in step 2b.
Walkthrough
The function convertToTitle(n) works as follows: If n is 0, it returns an empty string, which is our base case. Otherwise, it calculates the last character. This is done by (n - 1) % 26. The -1 is crucial because it maps 1->A, 26->Z correctly to 0->A, 25->Z. The rest of the number is then processed by a recursive call with (n - 1) / 26. The result of this recursive call is the prefix of our final string, to which we append the character we just calculated.
For example, convertToTitle(28):
n=28.(28-1)%26 = 1, which is 'B'.- Recursive call with
(28-1)/26 = 1. convertToTitle(1):(1-1)%26 = 0, which is 'A'.- Recursive call with
(1-1)/26 = 0. convertToTitle(0)returns"".- The call for
n=1returns"" + 'A'->"A". - The call for
n=28returns"A" + 'B'->"AB".
class Solution { public String convertToTitle(int columnNumber) { if (columnNumber == 0) { return ""; } // Decrement to map to a 0-25 range columnNumber--; // Recursively find the prefix and append the current character return convertToTitle(columnNumber / 26) + (char)('A' + (columnNumber % 26)); }}Complexity
Time
O(log_{26}(N))
Space
O(log_{26}(N))
Trade-offs
Pros
The code is very concise and elegant.
It directly models the mathematical recurrence relation of the problem.
Cons
Incurs overhead from recursive function calls, which can be slightly slower than an iterative solution.
For extremely large inputs (beyond the problem's constraints), it could risk a stack overflow error.
This is an iterative version of the base-26 conversion logic. It's generally more efficient than recursion as it avoids the overhead of function calls and eliminates the risk of stack overflow. The core logic remains the same: repeatedly use the modulo operator to find the rightmost digit (character) and division to process the rest of the number. Since we generate characters from right to left (least significant to most significant), we build the string in reverse and then perform a single reversal at the end.
Algorithm
This approach uses a loop to perform the base conversion iteratively, which avoids the overhead of recursion.
- Initialize an empty
StringBuilderto construct the result string. - Start a
whileloop that continues as long ascolumnNumberis greater than 0. - Inside the loop:
a. Decrement
columnNumberby 1 to map the 1-26 range to a 0-25 range. b. Calculate the remainder:rem = columnNumber % 26. This gives the 0-indexed value of the current character. c. Convert the remainder to its corresponding character(char)('A' + rem)and append it to theStringBuilder. d. UpdatecolumnNumberfor the next iteration by integer division:columnNumber = columnNumber / 26. - After the loop finishes, the
StringBuilderwill hold the characters of the title in reverse order. - Reverse the
StringBuilderand convert it to aStringto get the final correct title.
Walkthrough
We use a StringBuilder for efficient string construction. The loop continues as long as there's a part of the number left to process. In each step, we perform the (n-1) trick to align with a 0-indexed system. The remainder of a division by 26 gives us the current character, which we append to our builder. The quotient becomes the new number for the next iteration. This process effectively extracts the base-26 digits from right to left.
For example, columnNumber = 701:
- Initial:
sb = "",n = 701 - Iteration 1:
n--->n=700.rem = 700 % 26 = 24.char = 'Y'.sb = "Y".n = 700 / 26 = 26. - Iteration 2:
n--->n=25.rem = 25 % 26 = 25.char = 'Z'.sb = "YZ".n = 25 / 26 = 0. - End Loop:
nis now 0. - Final Step:
sb.reverse()gives"ZY". Return this string.
class Solution { public String convertToTitle(int columnNumber) { StringBuilder result = new StringBuilder(); while (columnNumber > 0) { // Decrement to map to a 0-25 range columnNumber--; // Get the remainder and convert to character int remainder = columnNumber % 26; result.append((char) ('A' + remainder)); // Update columnNumber for the next digit columnNumber = columnNumber / 26; } // The result is built in reverse, so reverse it before returning return result.reverse().toString(); }}Complexity
Time
O(log_{26}(N))
Space
O(log_{26}(N))
Trade-offs
Pros
Highly efficient in both time and space.
Avoids recursion, making it robust and preventing any chance of stack overflow.
Considered the standard and optimal solution for this type of problem.
Cons
Requires an explicit reversal step after the loop, which adds a small amount of complexity.
The code might be slightly more verbose than the recursive one.
Solutions
Solution
public class Solution { public string ConvertToTitle(int columnNumber) { StringBuilder res = new StringBuilder(); while (columnNumber != 0) { --columnNumber; res.Append((char)('A' + columnNumber % 26)); columnNumber /= 26; } return new string(res.ToString().Reverse().ToArray()); }}class Solution {public String convertToTitle(int columnNumber) { StringBuilder res = new StringBuilder(); while (columnNumber != 0) { --columnNumber; res.append((char)('A' + columnNumber % 26)); columnNumber /= 26; } return res.reverse().toString(); }}class Solution: def convertToTitle(self, columnNumber: int) -> str: res = [] while columnNumber: columnNumber -= 1 res . append(chr(ord('A') + columnNumber % 26)) columnNumber //= 26 return '' . join(res[:: - 1])Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.