171. Excel Sheet Column Number

EasyMathString
Leetcode Link

Problem Description

The problem is akin to translating a specialized numbering system, akin to a base-26 number system, into a decimal (base-10) system. In this system instead of using digits, Excel sheets use uppercase English letters where 'A' corresponds to 1, 'B' to 2, ..., and 'Z' to 26. After 'Z', the sequence continues with combinations of these letters, starting with 'AA', 'AB', etc., similar to how after 9 in decimal comes 10. Our task is to convert an input string columnTitle representing an Excel column title to its equivalent column number. For instance, 'A' is 1, 'Z' is 26, 'AA' is 27, 'AB' is 28, and so on.

Intuition

The solution is founded on understanding how the Excel column title translation to a number works. We recognize the pattern that it is almost like a base-26 number system but with a key distinction: there is no zero in the Excel system (it starts from 'A'=1, whereas in base-26, the least digit is '0').

Each character in the string is a "digit" in the base-26 system, with the rightmost character being the least significant "digit". To find the corresponding number, we start processing the string from left to right (the most significant "digit").

For each character, we follow these steps:

  1. Convert the letter to its corresponding numerical value, which is its position in the alphabet ('A' is 1, 'B' is 2, ..., 'Z' is 26). We do this by subtracting the ASCII value of 'A' from the ASCII value of the character and then adding 1.
  2. Multiply the current total by 26 to make space for the value of the next character (since each position is 26 times more significant than the position to its right).
  3. Add the numerical value of the current character to the running total.

We keep a running total and repeat these steps for each character. By the end of the loop, the running total represents the column number of the columnTitle.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Solution Approach

The implementation of the solution is fairly straightforward and does not require complex data structures. It applies a simple for-loop and arithmetic operations to achieve the conversion from the Excel column title to a number.

Here's a step-by-step walkthrough of the solution implementation:

  1. We initialize a variable res to 0. This will hold the cumulative result as we process each character in the Excel column title.

  2. We loop over each character c in the columnTitle string, processing from left to right.

    • For each character, the algorithm makes use of the ord() function to get the ASCII value of c, then subtracts the ASCII value of 'A' to align it with a base-26 system. But since Excel's numbering starts with 1 and not 0 (e.g., 'A' is 1, not 0), we add 1 to the result.

    • Then, we update the result res by multiplying it by 26 to make space for the next "digit" coming from c. This is similar to shifting digits to the left in base-10 mathematics when you multiply by 10 (123 * 10 becomes 1230).

    • Now, we add the value of c (now properly converted to a number from 1 to 26) to res.

  3. Once the loop concludes, res contains the final column number that corresponds to the input column title. This value is then returned from the function.

The solution uses a single for loop and operates in O(n) time complexity, where n is the length of the string columnTitle, because it reads each character exactly once. The space complexity is O(1) since it uses only a fixed amount of extra space (the res variable).

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

Which algorithm should you use to find a node that is close to the root of the tree?

Example Walkthrough

Let's walk through an example to illustrate the solution approach using the input columnTitle = "CAB".

  1. Initialize res to 0. This variable will accumulate our result.

  2. We process the first character, 'C':

    • Convert 'C' to its numerical value: ord('C') - ord('A') + 1 = 3 - 1 + 1 = 3.
    • Multiply res by 26 (since it's the first character, res is still 0): res = 0 * 26 + 3 = 3.

  3. Move to the second character, 'A':

    • Convert 'A' to its numerical value: ord('A') - ord('A') + 1 = 1 - 1 + 1 = 1.
    • Multiply res by 26 to make space for the 'A' value: res = 3 * 26 = 78.
    • Add the value of 'A': res = 78 + 1 = 79.

  4. Process the third character, 'B':

    • Convert 'B' to its numerical value: ord('B') - ord('A') + 1 = 2 - 1 + 1 = 2.
    • Multiply res by 26 to accommodate the 'B' value: res = 79 * 26 = 2054.
    • Add the value of 'B': res = 2054 + 2 = 2056.

  5. Now that we've processed all characters, res holds the final result (2056), which represents the column number of columnTitle = "CAB".

The column title 'CAB' translates to the column number 2056. Each character is weighed by its position's significance, akin to place value in our traditional base-10 number system, only in this case, it follows a base-26 logic without the digit '0'.

Solution Implementation

1class Solution:
2    def titleToNumber(self, column_title: str) -> int:
3        # Initialize the result to 0
4        result = 0
5
6        # Iterate through each character in the column title
7        for char in column_title:
8            # Convert the character to a number (A=1, B=2, ..., Z=26)
9            # and shift the previous result by multiplying by 26 (since it's base 26)
10            result = result * 26 + (ord(char) - ord('A') + 1)
11
12        # Return the final numerical result
13        return result
14
1class Solution {
2
3    /**
4     * This method converts a column title from a spreadsheet to its corresponding number.
5     * 
6     * @param columnTitle A string representing the column title to be converted.
7     * @return The numeric value of the column title.
8     */
9    public int titleToNumber(String columnTitle) {
10        int result = 0; // Initialize result to 0
11      
12        // Iterate over each character in the columnTitle string
13        for (char ch : columnTitle.toCharArray()) {
14            // Convert character to corresponding number ('A' -> 1, 'B' -> 2, ..., 'Z' -> 26)
15            int numericValue = ch - 'A' + 1;
16          
17            // Update the result by shifting it 26 places (base 26 number system) and adding the numeric value of the current character
18            result = result * 26 + numericValue;
19        }
20      
21        // Return the computed numeric value of the column title
22        return result;
23    }
24}
25
1class Solution {
2public:
3    // Function to convert a column title to its corresponding number
4    int titleToNumber(string columnTitle) {
5        int result = 0; // Initialize result to zero to store the column number
6
7        // Iterate over each character of the column title
8        for (char c : columnTitle) {
9            // Convert char to its position in the alphabet and add it to the result
10            // 'A' maps to 1, 'B' maps to 2, ..., so 'A' - 'A' + 1 starts at 1.
11            // Multiply the current result by 26 for base-26 calculation.
12            result = result * 26 + (c - 'A' + 1);
13        }
14        return result; // Return the resulting column number
15    }
16};
17
1/**
2 * Converts a column title from an Excel sheet (e.g., "A", "B", ..., "Z", "AA", etc.)
3 * to its corresponding column number.
4 *
5 * @param {string} columnTitle - The title of the column in Excel sheet notation.
6 * @return {number} The column number corresponding to the column title.
7 */
8function titleToNumber(columnTitle: string): number {
9    // Initialize the result variable to 0. This will be the final column number.
10    let columnNumber: number = 0;
11
12    // Loop through each character in the columnTitle string.
13    for (let character of columnTitle) {
14        // Convert the current character to its corresponding column number
15        // taking 'A' as 1, 'B' as 2, and so on by subtracting 64 from the ASCII code 
16        // (since 'A' is ASCII 65, 'B' is 66, etc.).
17        // Multiply the current result by 26 (number of letters in the alphabet) 
18        // to "shift" its value to the left before adding the new value.
19        columnNumber = columnNumber * 26 + character.charCodeAt(0) - 64;
20    }
21
22    // Return the final computed column number.
23    return columnNumber;
24}
25
Not Sure What to Study? Take the 2-min Quiz：

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Time and Space Complexity

The time complexity of the given code is O(n), where n is the length of the input string columnTitle. This is because the code iterates through each character in the input string exactly once, and for each character, it performs a constant-time operation (calculating the value of res based on ASCII values).

The space complexity of the code is O(1). This is because the space required to store the intermediate results and the final output does not depend on the size of the input string. The same amount of space (for variables res and c) is used regardless of the length of columnTitle.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Depth first search is equivalent to which of the tree traversal order?

Recommended Readings

Math Basics

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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 Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫