Jobs

Interviews

Discussions

Excel Sheet Column Title

#86 Most AskedEasy

Excel Sheet Column Title #86 Most Asked

Easy

DE Shaw

11 views

Topics:

MathStrings

Given an integer columnNumber, return its corresponding column title as it appears in an Excel sheet.

For example:

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

Example 1:

Input: columnNumber = 1
Output: "A"

Example 2:

Input: columnNumber = 28
Output: "AB"

Example 3:

Input: columnNumber = 701
Output: "ZY"

Constraints:

1 <= columnNumber <= 2³¹ - 1

Try coding it in LeetCode

Excel Sheet Column Title

#86 Most AskedEasy

Excel Sheet Column Title #86 Most Asked

Easy

DE Shaw

11 views

Topics:

MathStrings

Given an integer columnNumber, return its corresponding column title as it appears in an Excel sheet.

For example:

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

Example 1:

Input: columnNumber = 1
Output: "A"

Example 2:

Input: columnNumber = 28
Output: "AB"

Example 3:

Input: columnNumber = 701
Output: "ZY"

Constraints:

1 <= columnNumber <= 2³¹ - 1

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 valid range for the input `columnNumber`? Is there a maximum possible value?
Should I assume that the input `columnNumber` will always be a positive integer?
For very small input values like 1, what is the expected output?
Is the column numbering 0-indexed or 1-indexed (i.e., does 0 or 1 map to 'A')?
Could you provide a few examples of input and expected output to confirm my understanding of the conversion logic?

Brute Force Solution

Approach

We need to convert a number into its corresponding Excel column title. The brute force way is like trying to build the title character by character, exploring all possible letters for each position until we get the correct title for the given number.

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

Since each column title is made up of letters, start with the simplest cases: 'A', 'B', 'C', and so on.
Check if the given number matches the value of 'A' (which is 1), 'B' (which is 2), 'C' (which is 3), and so on, until 'Z' (which is 26).
If the number is larger than 26, it means the column title has at least two characters. Now try all possible two-letter combinations, like 'AA', 'AB', 'AC', and so on, checking each one against the input number.
If the number is still larger than any of the two-letter combinations, move on to trying all three-letter combinations, then four-letter combinations, and so on.
Keep going, testing all possible combinations of letters for the column title, until you find the combination that corresponds to the given number.

Code Implementation

def excel_sheet_column_title_brute_force(column_number):
    # Handle base cases first
    if column_number <= 0:
        return ""

    title = ""
    length = 0

    while True:
        length += 1
        start = 0

        # Calculate the starting number for the current length title
        for i in range(length - 1):
            start += 26 ** (i + 1)

        # Iterate through all possible combinations of letters for current length.
        for i in range(26 ** length):
            current_number = start + i + 1

            # If we found a match, return the title
            if current_number == column_number:
                temp_number = i
                temp_title = ""

                for _ in range(length):
                    temp_title = chr(65 + (temp_number % 26)) + temp_title
                    temp_number //= 26

                return temp_title

Big(O) Analysis

Time Complexity

O(26^k) – The described brute force algorithm explores all possible column titles until it finds the one corresponding to the input number n. The algorithm effectively tries all combinations of letters from A to Z for increasing lengths. In the worst case, it may need to generate titles up to length k, where k is the number of characters in the correct column title. Since each position can have 26 possibilities, this results in checking on the order of 26 to the power of k combinations. Therefore, the time complexity is O(26^k), where k represents the number of characters in the resulting Excel column title. Note that k is related to log base 26 of n.

Space Complexity

O(1) – The plain English explanation outlines a brute-force approach that essentially iterates through possible column titles ('A', 'B', ..., 'AA', 'AB', ...) until a match is found for the given number. While it conceptually explores combinations, it doesn't explicitly state that it stores all these combinations in memory. The described steps suggest the algorithm generates and checks titles one at a time. Therefore, only a fixed number of variables are needed to hold the current title being tested, regardless of the input number N. Hence, the auxiliary space used is constant.

Optimal Solution

Approach

We want to convert a number into its corresponding Excel column title (e.g., 1 -> A, 2 -> B, 27 -> AA). The key idea is to treat this as a base-26 conversion problem, similar to converting from decimal to binary, but with a slight twist due to the lack of a 'zero' digit.

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

Imagine you're working with an alphabet from A to Z instead of digits 0 to 9.
If the number is perfectly divisible by 26, reduce the number by 1. This accounts for the fact that there's no 'zero' in Excel column titles.
Find the remainder when the number is divided by 26. This remainder will give you a value from 0 to 25.
Convert the remainder to the corresponding letter (0 becomes A, 1 becomes B, and so on up to 25 becoming Z).
Add this letter to the beginning of your column title string.
Divide the original number by 26 (integer division, ignoring any remainder).
Repeat steps 2-6 until the number becomes zero.
The column title string you have built is the result.

Code Implementation

def convert_to_title(column_number):
    column_title = ""

    while column_number > 0:
        # Adjust number if divisible by 26
        if column_number % 26 == 0:
            column_number -= 1

            # Get remainder
        remainder = column_number % 26

        # Convert remainder to character
        column_title = chr(65 + remainder) + column_title

        # Integer division to reduce the number
        column_number //= 26

    return column_title

Big(O) Analysis

Time Complexity

O(log n) – The algorithm's runtime is determined by how many times the input number n can be divided by 26. Each division reduces n, and the loop continues until n becomes zero. Therefore, the number of iterations is proportional to the base-26 logarithm of n. The operations inside the loop, such as modulo and character concatenation, take constant time. Hence, the overall time complexity is O(log n).

Space Complexity

O(log N) – The algorithm builds the Excel column title string iteratively. The number of iterations (and thus the length of the string) is proportional to the number of times we can divide the input number N by 26 until it becomes zero. This is logarithmic in nature. The space used is primarily for storing the resulting column title string, which has a maximum length of log base 26 of N. Therefore, the auxiliary space complexity is O(log N).

Edge Cases

Case	How to Handle
Input is 0	The problem specifies a positive integer input, so input 0 should either be considered invalid and throw an exception, or return an empty string if considered a valid but non-existent column.
Input is 1	The smallest valid input should correctly return 'A'.
Input is 26	The input representing the last single-letter column should correctly return 'Z'.
Input is 27	Input where the output requires two letters should return 'AA'.
Large input (e.g., 2147483647)	The algorithm should handle arbitrarily large positive integers (up to the limits of the system's integer representation) without integer overflow or excessive memory usage, likely by performing division and modulo operations repeatedly.
Inputs close to multiples of 26 (e.g., 52, 53)	Correctly handle cases where the last digit needs to 'borrow' from the previous digits during conversion, returning 'AZ' for 52, 'BA' for 53.
Negative input	Negative input is invalid based on the problem description and should throw an IllegalArgumentException or return an empty string.
Input close to integer maximum value	Ensure the calculations (specifically division and modulo operations related to base 26) do not overflow when dealing with values close to the maximum integer value supported by the language.

Input is 0

How to Handle:

The problem specifies a positive integer input, so input 0 should either be considered invalid and throw an exception, or return an empty string if considered a valid but non-existent column.

Input is 1

How to Handle:

The smallest valid input should correctly return 'A'.

Input is 26

How to Handle:

The input representing the last single-letter column should correctly return 'Z'.

Input is 27

How to Handle:

Input where the output requires two letters should return 'AA'.

Large input (e.g., 2147483647)

How to Handle:

The algorithm should handle arbitrarily large positive integers (up to the limits of the system's integer representation) without integer overflow or excessive memory usage, likely by performing division and modulo operations repeatedly.

Inputs close to multiples of 26 (e.g., 52, 53)

How to Handle:

Correctly handle cases where the last digit needs to 'borrow' from the previous digits during conversion, returning 'AZ' for 52, 'BA' for 53.

Negative input

How to Handle:

Negative input is invalid based on the problem description and should throw an IllegalArgumentException or return an empty string.

Input close to integer maximum value

How to Handle:

Ensure the calculations (specifically division and modulo operations related to base 26) do not overflow when dealing with values close to the maximum integer value supported by the language.

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 valid range for the input `columnNumber`? Is there a maximum possible value?
Should I assume that the input `columnNumber` will always be a positive integer?
For very small input values like 1, what is the expected output?
Is the column numbering 0-indexed or 1-indexed (i.e., does 0 or 1 map to 'A')?
Could you provide a few examples of input and expected output to confirm my understanding of the conversion logic?

Brute Force Solution

Approach

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

Since each column title is made up of letters, start with the simplest cases: 'A', 'B', 'C', and so on.
Check if the given number matches the value of 'A' (which is 1), 'B' (which is 2), 'C' (which is 3), and so on, until 'Z' (which is 26).
If the number is larger than 26, it means the column title has at least two characters. Now try all possible two-letter combinations, like 'AA', 'AB', 'AC', and so on, checking each one against the input number.
If the number is still larger than any of the two-letter combinations, move on to trying all three-letter combinations, then four-letter combinations, and so on.
Keep going, testing all possible combinations of letters for the column title, until you find the combination that corresponds to the given number.

Code Implementation

def excel_sheet_column_title_brute_force(column_number):
    # Handle base cases first
    if column_number <= 0:
        return ""

    title = ""
    length = 0

    while True:
        length += 1
        start = 0

        # Calculate the starting number for the current length title
        for i in range(length - 1):
            start += 26 ** (i + 1)

        # Iterate through all possible combinations of letters for current length.
        for i in range(26 ** length):
            current_number = start + i + 1

            # If we found a match, return the title
            if current_number == column_number:
                temp_number = i
                temp_title = ""

                for _ in range(length):
                    temp_title = chr(65 + (temp_number % 26)) + temp_title
                    temp_number //= 26

                return temp_title

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine you're working with an alphabet from A to Z instead of digits 0 to 9.
If the number is perfectly divisible by 26, reduce the number by 1. This accounts for the fact that there's no 'zero' in Excel column titles.
Find the remainder when the number is divided by 26. This remainder will give you a value from 0 to 25.
Convert the remainder to the corresponding letter (0 becomes A, 1 becomes B, and so on up to 25 becoming Z).
Add this letter to the beginning of your column title string.
Divide the original number by 26 (integer division, ignoring any remainder).
Repeat steps 2-6 until the number becomes zero.
The column title string you have built is the result.

Code Implementation

def convert_to_title(column_number):
    column_title = ""

    while column_number > 0:
        # Adjust number if divisible by 26
        if column_number % 26 == 0:
            column_number -= 1

            # Get remainder
        remainder = column_number % 26

        # Convert remainder to character
        column_title = chr(65 + remainder) + column_title

        # Integer division to reduce the number
        column_number //= 26

    return column_title

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input is 0	The problem specifies a positive integer input, so input 0 should either be considered invalid and throw an exception, or return an empty string if considered a valid but non-existent column.
Input is 1	The smallest valid input should correctly return 'A'.
Input is 26	The input representing the last single-letter column should correctly return 'Z'.
Input is 27	Input where the output requires two letters should return 'AA'.
Large input (e.g., 2147483647)	The algorithm should handle arbitrarily large positive integers (up to the limits of the system's integer representation) without integer overflow or excessive memory usage, likely by performing division and modulo operations repeatedly.
Inputs close to multiples of 26 (e.g., 52, 53)	Correctly handle cases where the last digit needs to 'borrow' from the previous digits during conversion, returning 'AZ' for 52, 'BA' for 53.
Negative input	Negative input is invalid based on the problem description and should throw an IllegalArgumentException or return an empty string.
Input close to integer maximum value	Ensure the calculations (specifically division and modulo operations related to base 26) do not overflow when dealing with values close to the maximum integer value supported by the language.

Input is 0

How to Handle:

The problem specifies a positive integer input, so input 0 should either be considered invalid and throw an exception, or return an empty string if considered a valid but non-existent column.

Input is 1

How to Handle:

The smallest valid input should correctly return 'A'.

Input is 26

How to Handle:

The input representing the last single-letter column should correctly return 'Z'.

Input is 27

How to Handle:

Input where the output requires two letters should return 'AA'.

Large input (e.g., 2147483647)

How to Handle:

Inputs close to multiples of 26 (e.g., 52, 53)

How to Handle:

Correctly handle cases where the last digit needs to 'borrow' from the previous digits during conversion, returning 'AZ' for 52, 'BA' for 53.

Negative input

How to Handle:

Negative input is invalid based on the problem description and should throw an IllegalArgumentException or return an empty string.

Input close to integer maximum value

How to Handle:

Ensure the calculations (specifically division and modulo operations related to base 26) do not overflow when dealing with values close to the maximum integer value supported by the language.

0/126 DE Shaw questions completed

0/126 completed