168. Excel Sheet Column Title
Problem Description
The given problem requires us to convert an integer, columnNumber
, into a string that represents the corresponding column title as seen in an Excel sheet. In Excel, columns are labeled alphabetically from A to Z, then continuing with AA, AB, etc., after Z. This sequence creates a pattern similar to base-26 numeral system, except that it doesn't contain a zero and it starts from A (1) rather than zero (0).
In this pattern, A
corresponds to 1, B
to 2, and so on up to Z
which corresponds to 26. Then, the sequence continues with two-letter combinations such as AA
for 27, AB
for 28, and so on. Unlike our decimal system, where the digit '0' represents zero and serves as a place-holder, there is no 'zero' character in the Excel column titles.
The challenge is to convert the given columnNumber
into this special alphabet-based naming system. This includes figuring out how many times we can divide the number by 26 to advance letters and how to correctly wrap around after reaching the end of the alphabet.
Intuition
To solve this problem, we can use a method similar to converting a number from base-10 to base-26, with the twist that Excel's column naming scheme is 1-indexed, not 0-indexed. This means the sequence goes 1, 2, ..., 25, 26 (A, B, ..., Y, Z) and then wraps to 27 (AA), rather than the standard 0, 1, ..., 24, 25 (A, B, ..., Y, Z) and then wrap to 26 (AA).
Here's the approach step-by-step:
-
Initialize an empty list
res
to accumulate the characters (from the least important digit to the most important one). -
Enter a loop that will continue as long as
columnNumber
is greater than zero. This iterative process will divide thecolumnNumber
until it cannot be divided anymore, indicating completion. -
Inside the loop, since the numbering is 1-indexed, we decrease
columnNumber
by 1 to convert it to a 0-indexed number. -
Obtain the remainder of the current
columnNumber
when divided by 26. This modulo operation gives us an index corresponding to the letters from A to Z. -
Convert this index into a character by adding it to the ASCII value of 'A' and append the resulting character to the list
res
. -
Prepare for the next iteration by dividing
columnNumber
by 26 since we have already handled one "digit" of our base-26 number. -
Once the loop is done, we reverse
res
because we have been appending the less significant characters first, and then we join the characters together to form a string. -
Return the resulting string, which is the column title that corresponds to the original
columnNumber
.
By repeatedly taking modulus and division, we handle the number 'column by column', just like an actual base conversion, but always taking into consideration the offset caused by the lack of 'zero' in the Excel system. This approach keeps us within Excel's 1-indexed column naming system.
Learn more about Math patterns.
Solution Approach
The implementation of the solution involves a straightforward approach that resembles a base-conversion algorithm. Here's a detailed walk-through of the implementation steps.
-
Create a class
Solution
with a methodconvertToTitle
, which takes an integercolumnNumber
as its parameter and returns a string. -
Inside the
convertToTitle
method, initialize an empty listres
which will store the characters of our result in reverse order (the least significant 'digit' first). -
Use a
while
loop to process thecolumnNumber
as long as it's greater than 0. This loop will be used to iteratively break down the number from base-10 to the equivalent 'base-26'. -
As Excel columns start from 1 (A) instead of 0, we subtract 1 from
columnNumber
each iteration to properly align our values with the index for character mapping. -
Calculate the remainder with
columnNumber % 26
to determine which character in the range A-Z corresponds to the current least significant 'digit' of the number. -
Use
ord('A')
to get the ASCII value of 'A', then add the remainder to it. This will give us the ASCII value of the character we want. Usechr()
to get the character from this ASCII value and append it to our listres
. -
Prepare for the next iteration by performing integer division
columnNumber //= 26
to reduce ourcolumnNumber
for the subsequent 'digit'. -
Once the
while
loop concludes, we have all the characters of our column title in reverse order. We use[::1]
to reverse the listres
back to the correct order. -
Finally, we join the list of characters with
join()
into a string, which represents the column title equivalent to the initialcolumnNumber
. -
The method
convertToTitle
returns this string, completing the conversion process.
This solution doesn't use any complex libraries or specific data structures beyond a basic list and standard Python string operations. The pattern here mirrors a familiar concept of converting between numeral systems, accommodating the unique Excel spreadsheet 1-indexed base. It is an elegant and efficient solution that works within the confines of Python's simple data manipulation capabilities.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through an example to illustrate the solution approach by converting the columnNumber
705 to its corresponding Excel column title.
-
We begin with
columnNumber
= 705. Our resultres
is currently an empty list. -
Enter the
while
loop sincecolumnNumber
> 0. -
Subtract 1 from
columnNumber
to make it 0-indexed:columnNumber
= 705 - 1 = 704. -
Calculate the remainder of
columnNumber
divided by 26 to determine the character for this 'digit':remainder
=columnNumber
% 26 = 704 % 26 = 24. -
Convert this remainder to a character by finding the ASCII value of 'A', adding the remainder to it, and then converting back to a character with
chr()
:character
=chr(ord('A') + remainder)
= chr(65 + 24) = 'Y'. Append 'Y' tores
. -
Update
columnNumber
for the next iteration:columnNumber
//= 26 = 704 // 26 = 27. -
As
columnNumber
is still greater than 0, we repeat steps 3-6:columnNumber
= 27 - 1 = 26- remainder = 26 % 26 = 0
- 'A' + 0 = 'A', append 'A' to
res
. Now,res
= ['Y', 'A']. columnNumber
= 26 // 26 = 1
-
We loop again:
columnNumber
= 1 - 1 = 0- remainder = 0 % 26 = 0
- 'A' + 0 = 'A', append 'A' to
res
. Now,res
= ['Y', 'A', 'A']. columnNumber
= 0 // 26 = 0
-
The loop ends because
columnNumber
is now 0. -
Reverse
res
and join the characters to form a string:res.reverse()
= ['A', 'A', 'Y'],result
= ''.join(res) = "AAY". -
Return the result, "AAY", which is the corresponding Excel column title for column number 705.
We have converted the input columnNumber
705 into the Excel column title "AAY" following the solution steps detailed above.
Solution Implementation
1class Solution:
2 def convertToTitle(self, column_number: int) -> str:
3 # Initialize an empty list to store the characters that will
4 # represent the column title in reverse order.
5 title_chars = []
6
7 # Continue to iterate as long as the column_number is greater than zero.
8 while column_number:
9 # Adjust column_number to zero-indexed for modulo operation.
10 column_number -= 1
11
12 # Calculate the character that corresponds to the current modulo of
13 # column_number and 'A'. Append the character to the title_chars list.
14 title_chars.append(chr(ord('A') + column_number % 26))
15
16 # Update column_number by dividing it by 26, for the next iteration
17 # as we move to the next most significant digit in the title.
18 column_number //= 26
19
20 # Since the title_chars list was constructed backwards,
21 # reverse it and join the characters into a single string
22 # to form the column title, then return the result.
23 return ''.join(title_chars[::-1])
24
1class Solution {
2
3 // This method converts a given column number to its corresponding Excel column title.
4 public String convertToTitle(int columnNumber) {
5 // StringBuilder to build the result in reverse order
6 StringBuilder result = new StringBuilder();
7
8 // Loop until the columnNumber is 0
9 while (columnNumber > 0) {
10 // Decrement columnNumber to adjust for 1-indexing in Excel columns
11 columnNumber--;
12
13 // Calculate the character to append using the remainder
14 // and concatenate it to our result string
15 result.append((char) ('A' + columnNumber % 26));
16
17 // Update columnNumber by dividing by 26 for the next iteration
18 columnNumber /= 26;
19 }
20
21 // Reverse the result since we’ve been appending characters from least significant (right most) to most significant
22 return result.reverse().toString();
23 }
24}
25
1#include <string>
2#include <algorithm> // for std::reverse
3
4// This function converts a given column number to a title as it would appear in an Excel sheet.
5// For example, 1 becomes 'A', 27 becomes 'AA', and so on.
6std::string convertToTitle(int columnNumber) {
7 // Initialize a string to hold the characters of the final result.
8 std::string title;
9
10 // Continue the loop until the columnNumber is reduced to 0.
11 while (columnNumber > 0) {
12 // Decrement to map the number to a zero-indexed scale where A=0, B=1, ..., Z=25.
13 columnNumber--;
14
15 // Get the remainder when columnNumber is divided by 26 to find
16 // the character that corresponds to the current place value.
17 int remainder = columnNumber % 26;
18
19 // Convert the remainder to the corresponding uppercase character
20 // by adding it to 'A', then prepend it to the 'title' string.
21 // The ASCII value of 'A' is 65, but adding remainder to 'A' gives the correct character.
22 title.insert(title.begin(), 'A' + remainder);
23
24 // Go to the next place value by dividing columnNumber by 26 before the next iteration.
25 columnNumber /= 26;
26 }
27
28 // The characters are inserted in reverse order, so we must reverse the final string.
29 // This can be done during insertion as in the line above or by reversing the string here.
30 // std::reverse(title.begin(), title.end());
31
32 // Return the column title in the correct format.
33 return title;
34}
35
1// This function converts a given column number to a title as it would appear in an Excel sheet.
2// For example, 1 becomes 'A', 27 becomes 'AA' and so on.
3function convertToTitle(columnNumber: number): string {
4 // Initialize an array to hold the characters of the final result.
5 let titleCharacters: string[] = [];
6
7 // Continue the loop until the columnNumber is reduced to 0.
8 while (columnNumber > 0) {
9 // Decrement to map the number to a zero-indexed scale where A=0, B=1, ..., Z=25.
10 columnNumber--;
11
12 // Get the remainder when columnNumber is divided by 26 to find
13 // the character that corresponds to the current place value.
14 let remainder: number = columnNumber % 26;
15
16 // Convert the remainder to the corresponding ASCII uppercase character
17 // and unshift it to the start of the titleCharacters array.
18 // ASCII value of 'A' is 65, so adding remainder to it gives the correct character.
19 titleCharacters.unshift(String.fromCharCode(remainder + 65));
20
21 // Go to the next place value by dividing columnNumber by 26 before the next iteration.
22 columnNumber = Math.floor(columnNumber / 26);
23 }
24
25 // Join the titleCharacters array into a string to get the column title in the correct format.
26 return titleCharacters.join('');
27}
28
Time and Space Complexity
The time complexity of the function is O(log_{26}(n))
, where n
is the columnNumber
. This is because the loop divides the columnNumber
by 26 in each iteration, effectively converting the number from base 10 to base 26. The number of iterations is proportional to the number of times n
can be divided by 26 before it becomes 0, which is essentially the number of digits in the base-26 representation of n
.
The space complexity of the function is O(log_{26}(n))
as well. The reason behind this is that space is allocated for the res
list, which stores each character corresponding to a digit in the base-26 number. The length of the res
list is equal to the number of digits in the base-26 representation of n
, which results from the same logarithmic relationship as in the time complexity analysis.
Learn more about how to find time and space complexity quickly using problem constraints.
How does merge sort divide the problem into subproblems?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.