Allan Kiche's Blog

Leetcode 168 - Excel Sheet Column Title

Leetcode 168 - Excel Sheet Column Title

Allan N Kiche's photo
Allan N Kiche
·

4 min read

Table of contents

Hello, Welcome to my July Challenge of Problem Solving and finding solutions to Leetcode's Data Structures and Algorithm questions. Here, I choose a question daily and try to solve it, and finally pen down my process of flow in solving the question.

I hope you find it helpful. Today I will be solving Leetcode's question 168 - Excel Sheet Colum Title

Problem Statement

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

Thought Process/ Intuition

I had the following three thought processes:

  • The column titles in Excel are based on the English alphabet, so I knew that I would need to use some sort of algorithm to convert the column number to a string of letters.

  • I thought about using a recursive function to solve the problem. The function would start with the column number and then recursively divide the column number by 26 and add the corresponding letter to the string of letters.

  • I also thought about using a loop to solve the problem. The loop would start with the column number and then iterate while the column number is greater than 0. In each iteration, the loop would calculate the remainder of the column number divided by 26 and then add the corresponding letter to the string of letters.

To convert the column number to a column title, I would iterate through the digits from right to left. I would use the modulus operator to calculate the remainder when dividing the column number by 26, representing the rightmost character of the title. I would convert the remainder to its corresponding character and append it to the resulting title string. Then, I would update the column number by performing an integer division by 26 to move on to the next digit.

To handle the special case where the remainder is 0 (indicating 'Z'), I would subtract 1 from the column number before performing the division to ensure correct calculations for subsequent digits.

By repeating this process until the column number becomes 0, I would construct the column title in reverse order. Finally, I would reverse the resulting string to obtain the correct order of characters.

This approach ensures that each character is extracted correctly based on its positional value, allowing for the conversion of the integer column number to its corresponding Excel column title.

The Approach

To solve the problem of converting an integer column number to its corresponding column title in Excel, I would use a digit-by-digit conversion approach. Here is a step-by-step description of the approach:

  1. Initialize an empty string to store the column title.

  2. Iterate while the column number is greater than 0: a. Calculate the remainder when the column number is divided by 26. b. If the remainder is 0, set it to 26 and subtract 1 from the column number. c. Convert the remainder to its corresponding character using ASCII manipulation. d. Append the character to the beginning of the column title string. e. Divide the column number by 26 (integer division).

  3. Return the final column title string.

This approach leverages the fact that Excel column titles follow a base-26 system, where each digit represents a character from 'A' to 'Z'. By performing digit-by-digit conversion and mapping the remainders to characters, we can build the column title from right to left.

The algorithm handles the special case where the remainder is 0 (indicating 'Z') by subtracting 1 from the column number before the division. This ensures correct calculations for subsequent digits.

By following this approach, we can successfully convert the given integer column number to its corresponding column title as it appears in an Excel sheet.

Code snippet

class Solution:
    def convertToTitle(self, colunNumber: int) -> str:
        result = ""

        while colunNumber > 0:
            remainder = colunNumber % 26
            if remainder == 0:
                remainder = 26
                colunNumber -= 1

            character = chr(ord('A') + remainder - 1)
            result = character + result

            colunNumber //= 26

        return result

Time and Space Complexity

The time complexity of the code is O(log(columnNumber)) because the while loop iterates as many times as the number of digits in the columnNumber. In each iteration, we perform constant time operations such as modulus, addition, subtraction, character conversion, and integer division.

The space complexity of the code is O(log(columnNumber)) as well. This is because the space required to store the column title string depends on the number of digits in the columnNumber. In the worst case, the number of digits is log(columnNumber) (base 10), so the space complexity is logarithmic in terms of the input columnNumber.

excelPython