Jobs

Interviews

Discussions

Excel Sheet Column Number

Easy

Asked by:

More companies

53 views

Topics:

StringsArrays

Given a string columnTitle that represents the column title as appears in an Excel sheet, return its corresponding column number.

For example:

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 
...

Example 1:

Input: columnTitle = "A"
Output: 1

Example 2:

Input: columnTitle = "AB"
Output: 28

Example 3:

Input: columnTitle = "ZY"
Output: 701

Constraints:

1 <= columnTitle.length <= 7
columnTitle consists only of uppercase English letters.
columnTitle is in the range ["A", "FXSHRXW"].

Try coding it in LeetCode

Excel Sheet Column Number

Easy

Asked by:

53 views

Topics:

StringsArrays

Given a string columnTitle that represents the column title as appears in an Excel sheet, return its corresponding column number.

For example:

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 
...

Example 1:

Input: columnTitle = "A"
Output: 1

Example 2:

Input: columnTitle = "AB"
Output: 28

Example 3:

Input: columnTitle = "ZY"
Output: 701

Constraints:

1 <= columnTitle.length <= 7
columnTitle consists only of uppercase English letters.
columnTitle is in the range ["A", "FXSHRXW"].

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the `columnTitle` string? Are there any length constraints?
Can the input `columnTitle` be an empty string or null?
Is the input `columnTitle` guaranteed to contain only uppercase English letters (A-Z)?
Are there any invalid characters or special symbols expected in `columnTitle` besides uppercase letters?
Could you provide an example of a very large column title, such as something long that would result in a very large column number to help me understand edge cases?

Brute Force Solution

Approach

The problem asks to convert a column title like 'AB' to its corresponding column number. The brute force way to do this is similar to trying all possible number combinations, but with letters. We can think of each letter as a digit in a base-26 number system.

Here's how the algorithm would work step-by-step:

Start from the leftmost letter in the column title.
Convert that letter into its corresponding number (A=1, B=2, ..., Z=26).
If there is only one letter, that's the answer.
If there are more letters, multiply the number you got in step 2 by 26.
Then, move to the next letter to the right and convert it to its number.
Add this number to the result from step 4.
Repeat steps 4, 5, and 6 for each remaining letter in the column title.
The final result after processing all the letters is the column number.

Code Implementation

def excel_sheet_column_number_brute_force(column_title):
    result = 0
    for i in range(len(column_title)): 
        # Iterate through each character of the column title
        character = column_title[i]
        letter_value = ord(character) - ord('A') + 1

        # For letters beyond the first, update the result
        if i < len(column_title) - 1:
            result = result + letter_value * (26 ** (len(column_title) - i - 1))

        # Add the value of the right-most character
        else:
            result = result + letter_value

    return result

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string (column title) once, where n is the length of the string. In each iteration, it performs a constant number of operations: converting a character to its corresponding value and updating the result. The number of operations is directly proportional to the length of the input string. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The provided algorithm iterates through the input string and performs calculations, but it doesn't create any auxiliary data structures that scale with the input size N (the length of the column title string). It only uses a constant amount of extra memory for variables like the intermediate result, regardless of the input length. Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

The problem is like figuring out what number a name like 'AB' represents in a spreadsheet. Each letter's position matters, with later letters being 'worth' more, similar to how digits in a number system work.

Here's how the algorithm would work step-by-step:

Start with zero. This will be our running total.
Look at each letter in the column name from left to right.
For each letter, think of it as a digit in base 26 (because there are 26 letters in the alphabet). Convert the letter to its numerical value (A=1, B=2, ..., Z=26).
Multiply the current running total by 26 (because each position to the left is 26 times more significant).
Add the numerical value of the current letter to the running total.
Continue this process for each letter in the column name.
The final running total is the column number.

Code Implementation

def excel_sheet_column_number(column_title):
    running_total = 0

    for character in column_title:
        #Convert the character to its numerical value (A=1, B=2, ..., Z=26)
        character_value = ord(character) - ord('A') + 1

        # Multiply the current total by 26
        running_total = running_total * 26

        # Add the numerical value of the current letter to the total
        running_total += character_value

    return running_total

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each character of the input string (column name) once. The number of iterations is directly proportional to the length of the input string, which we can denote as 'n'. Inside the loop, there are only constant-time operations: multiplication, addition, and character-to-integer conversion. Therefore, the time complexity is linear with respect to the input size 'n', resulting in O(n).

Space Complexity

O(1) – The algorithm iteratively processes the input string without using any auxiliary data structures that scale with the input size. It only uses a constant amount of extra space to store the running total, which does not depend on the length of the input string (N). Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input string	Return 0 immediately as there is no column title.
Single-character input (e.g., "A")	The algorithm correctly handles single-character inputs by converting the character to its corresponding numerical value (A=1, B=2, etc.).
Input string with mixed-case characters (e.g., "aB")	Convert the input to uppercase to ensure uniformity and correct calculation.
Very long input string representing a large column number (e.g., "FXSHRXW")	Ensure that the intermediate calculations do not result in integer overflow; use a 64-bit integer type if necessary.
Input string contains invalid characters (e.g., "A!C")	Throw an exception or return an error value, as the problem statement defines the input string to only contain letters.
Input string "Z"	The algorithm should correctly convert "Z" to 26.
Input string "AA"	The algorithm should correctly convert "AA" to 27 (1 * 26 + 1).
Maximum possible input string (e.g., "XFD" which is 2^14 -1 )	The algorithm should handle the largest column number and ensure no overflow; data type used to hold result must be large enough.

Null or empty input string

How to Handle:

Return 0 immediately as there is no column title.

Single-character input (e.g., "A")

How to Handle:

The algorithm correctly handles single-character inputs by converting the character to its corresponding numerical value (A=1, B=2, etc.).

Input string with mixed-case characters (e.g., "aB")

How to Handle:

Convert the input to uppercase to ensure uniformity and correct calculation.

Very long input string representing a large column number (e.g., "FXSHRXW")

How to Handle:

Ensure that the intermediate calculations do not result in integer overflow; use a 64-bit integer type if necessary.

Input string contains invalid characters (e.g., "A!C")

How to Handle:

Throw an exception or return an error value, as the problem statement defines the input string to only contain letters.

Input string "Z"

How to Handle:

The algorithm should correctly convert "Z" to 26.

Input string "AA"

How to Handle:

The algorithm should correctly convert "AA" to 27 (1 * 26 + 1).

Maximum possible input string (e.g., "XFD" which is 2^14 -1 )

How to Handle:

The algorithm should handle the largest column number and ensure no overflow; data type used to hold result must be large enough.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the `columnTitle` string? Are there any length constraints?
Can the input `columnTitle` be an empty string or null?
Is the input `columnTitle` guaranteed to contain only uppercase English letters (A-Z)?
Are there any invalid characters or special symbols expected in `columnTitle` besides uppercase letters?
Could you provide an example of a very large column title, such as something long that would result in a very large column number to help me understand edge cases?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start from the leftmost letter in the column title.
Convert that letter into its corresponding number (A=1, B=2, ..., Z=26).
If there is only one letter, that's the answer.
If there are more letters, multiply the number you got in step 2 by 26.
Then, move to the next letter to the right and convert it to its number.
Add this number to the result from step 4.
Repeat steps 4, 5, and 6 for each remaining letter in the column title.
The final result after processing all the letters is the column number.

Code Implementation

def excel_sheet_column_number_brute_force(column_title):
    result = 0
    for i in range(len(column_title)): 
        # Iterate through each character of the column title
        character = column_title[i]
        letter_value = ord(character) - ord('A') + 1

        # For letters beyond the first, update the result
        if i < len(column_title) - 1:
            result = result + letter_value * (26 ** (len(column_title) - i - 1))

        # Add the value of the right-most character
        else:
            result = result + letter_value

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start with zero. This will be our running total.
Look at each letter in the column name from left to right.
For each letter, think of it as a digit in base 26 (because there are 26 letters in the alphabet). Convert the letter to its numerical value (A=1, B=2, ..., Z=26).
Multiply the current running total by 26 (because each position to the left is 26 times more significant).
Add the numerical value of the current letter to the running total.
Continue this process for each letter in the column name.
The final running total is the column number.

Code Implementation

def excel_sheet_column_number(column_title):
    running_total = 0

    for character in column_title:
        #Convert the character to its numerical value (A=1, B=2, ..., Z=26)
        character_value = ord(character) - ord('A') + 1

        # Multiply the current total by 26
        running_total = running_total * 26

        # Add the numerical value of the current letter to the total
        running_total += character_value

    return running_total

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return 0 immediately as there is no column title.
Single-character input (e.g., "A")	The algorithm correctly handles single-character inputs by converting the character to its corresponding numerical value (A=1, B=2, etc.).
Input string with mixed-case characters (e.g., "aB")	Convert the input to uppercase to ensure uniformity and correct calculation.
Very long input string representing a large column number (e.g., "FXSHRXW")	Ensure that the intermediate calculations do not result in integer overflow; use a 64-bit integer type if necessary.
Input string contains invalid characters (e.g., "A!C")	Throw an exception or return an error value, as the problem statement defines the input string to only contain letters.
Input string "Z"	The algorithm should correctly convert "Z" to 26.
Input string "AA"	The algorithm should correctly convert "AA" to 27 (1 * 26 + 1).
Maximum possible input string (e.g., "XFD" which is 2^14 -1 )	The algorithm should handle the largest column number and ensure no overflow; data type used to hold result must be large enough.

Null or empty input string

How to Handle:

Return 0 immediately as there is no column title.

Single-character input (e.g., "A")

How to Handle:

The algorithm correctly handles single-character inputs by converting the character to its corresponding numerical value (A=1, B=2, etc.).

Input string with mixed-case characters (e.g., "aB")

How to Handle:

Convert the input to uppercase to ensure uniformity and correct calculation.

Very long input string representing a large column number (e.g., "FXSHRXW")

How to Handle:

Ensure that the intermediate calculations do not result in integer overflow; use a 64-bit integer type if necessary.

Input string contains invalid characters (e.g., "A!C")

How to Handle:

Throw an exception or return an error value, as the problem statement defines the input string to only contain letters.

Input string "Z"

How to Handle:

The algorithm should correctly convert "Z" to 26.

Input string "AA"

How to Handle:

The algorithm should correctly convert "AA" to 27 (1 * 26 + 1).

Maximum possible input string (e.g., "XFD" which is 2^14 -1 )

How to Handle:

The algorithm should handle the largest column number and ensure no overflow; data type used to hold result must be large enough.