171. Excel Sheet Column Number
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:
- 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.
- 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).
- 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.
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:
-
We initialize a variable
res
to0
. This will hold the cumulative result as we process each character in the Excel column title. -
We loop over each character
c
in thecolumnTitle
string, processing from left to right.-
For each character, the algorithm makes use of the
ord()
function to get the ASCII value ofc
, 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 fromc
. This is similar to shifting digits to the left in base-10 mathematics when you multiply by 10 (123 * 10
becomes1230
). -
Now, we add the value of
c
(now properly converted to a number from 1 to 26) tores
.
-
-
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).
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 using the input columnTitle = "CAB"
.
-
Initialize
res
to 0. This variable will accumulate our result. -
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
.
- Convert 'C' to its numerical value:
-
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
.
- Convert 'A' to its numerical value:
-
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
.
- Convert 'B' to its numerical value:
-
Now that we've processed all characters,
res
holds the final result (2056
), which represents the column number ofcolumnTitle = "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
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.
In a binary min heap, the minimum element can be found in:
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
Want a Structured Path to Master System Design Too? Donāt Miss This!