Excel Sheet Column Title

Easy Arrays & Hashing Math / Number Theory Original on LeetCode

Reported atZohoOla

Excel Sheet Column Title is a easy arrays & hashing problem solved with the math / number theory pattern. The best approach, optimal (base 26 with digits 1 to 26), runs in O(log n) time and O(log n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (count up one column at a time) up.

Problem

Spreadsheet columns are labelled A, B, …, Z, then AA, AB, …, AZ, BA, …, ZZ, then AAA, and so on. Column 1 is A, column 26 is Z and column 27 is AA.

Given a positive integer columnNumber, return its column label.

Examples

Example 1

Input
columnNumber = 30
Output
"AD"
Why
Z is column 26, then AA = 27, AB = 28, AC = 29 and AD = 30.

Example 2

Input
columnNumber = 26
Output
"Z"
Why
There is no zero digit: 26 is the single letter Z, not "A0".

Example 3

Input
columnNumber = 1000
Output
"ALL"
Why
1000 = 1 · 26² + 12 · 26 + 12, and the digits 1, 12, 12 are A, L, L.

Constraints

  • 1 <= columnNumber <= 2^31 - 1

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (count up one column at a time)O(n)O(log n)
Optimal (base 26 with digits 1 to 26)O(log n)O(log n)

1Brute force (count up one column at a time)

TimeO(n)One increment per column number, each O(1) on average; far too slow for numbers near 2^31.
SpaceO(log n)The title has about log26(n) letters.

Start at "A" and increase the title one column at a time, exactly like an odometer with letters: the last letter goes up by one, a Z rolls over to A and carries into the letter on its left, and a carry out of the first letter adds a new A. After columnNumber - 1 steps, that is the title.

  1. Keep the letters least significant first, starting with ['A'].
  2. Repeat columnNumber - 1 times: from the front, turn every Z into A; if a letter remains, increment it, otherwise append a new A.
  3. Reverse the letters to get the title.
class Solution {
    public String convertToTitle(int columnNumber) {
        StringBuilder rev = new StringBuilder("A");
        for (int step = 1; step < columnNumber; step++) {
            int i = 0;
            while (i < rev.length() && rev.charAt(i) == 'Z') {
                rev.setCharAt(i, 'A');
                i++;
            }
            if (i == rev.length()) rev.append('A');
            else rev.setCharAt(i, (char) (rev.charAt(i) + 1));
        }
        return rev.reverse().toString();
    }
}

2Optimal (base 26 with digits 1 to 26)

TimeO(log n)Each step divides n by 26, so there are at most 7 steps for a 32-bit int.
SpaceO(log n)The output string.

Peel off letters from the right. Because the digits are 1..26 rather than 0..25, shift down by one first: the last letter is (n - 1) % 26 (0 = A, 25 = Z), and the remaining prefix is the title of (n - 1) / 26. Repeat until n becomes 0, then reverse.

  1. While n > 0: n--, append 'A' + n % 26, then n /= 26.
  2. Reverse the collected letters and return them.
class Solution {
    public String convertToTitle(int columnNumber) {
        StringBuilder sb = new StringBuilder();
        int n = columnNumber;
        while (n > 0) {
            n--;
            sb.append((char) ('A' + n % 26));
            n /= 26;
        }
        return sb.reverse().toString();
    }
}

Edge cases to test

  • Exact multiples of 26, such as 26 (Z), 52 (AZ) and 702 (ZZ)
  • The first column with more letters, such as 27 (AA) and 703 (AAA)
  • The largest input, 2^31 - 1

Hints

Hint 1

This is base 26, except the digits run from 1 (A) to 26 (Z) instead of 0 to 25.

Hint 2

Subtract 1 before taking the remainder: (n - 1) % 26 gives the last letter as 0..25.

Hint 3

Then continue with (n - 1) / 26 and build the letters from right to left.

FAQ

What is the best time complexity for Excel Sheet Column Title?

Optimal (base 26 with digits 1 to 26) runs in O(log n) time and O(log n) extra space. Each step divides n by 26, so there are at most 7 steps for a 32-bit int.

Which pattern does Excel Sheet Column Title use?

It is a arrays & hashing problem that uses the math / number theory pattern. Other problems with the same pattern: Bulb Switcher, Reaching Points, Water and Jug Problem.

Is there a brute force solution for Excel Sheet Column Title?

Yes. Brute force (count up one column at a time) takes O(n) time and O(log n) space. Start at "A" and increase the title one column at a time, exactly like an odometer with letters: the last letter goes up by one, a Z rolls over to A and carries into the letter on its left, and a carry out of the first letter adds a new A.

Which edge cases should I test for Excel Sheet Column Title?

Exact multiples of 26, such as 26 (Z), 52 (AZ) and 702 (ZZ); The first column with more letters, such as 27 (AA) and 703 (AAA); The largest input, 2^31 - 1.