168. Excel Sheet Column Title

EasyMathString

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 the columnNumber 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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

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 method convertToTitle, which takes an integer columnNumber as its parameter and returns a string.
Inside the convertToTitle method, initialize an empty list res which will store the characters of our result in reverse order (the least significant 'digit' first).
Use a while loop to process the columnNumber 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. Use chr() to get the character from this ASCII value and append it to our list res.
Prepare for the next iteration by performing integer division columnNumber //= 26 to reduce our columnNumber 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 list res 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 initial columnNumber.
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 Evaluator

Example 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 result res is currently an empty list.
Enter the while loop since columnNumber > 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' to res.
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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don't know