Excel Sheet Column Title
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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| 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)
O(n)One increment per column number, each O(1) on average; far too slow for numbers near 2^31.O(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.
- Keep the letters least significant first, starting with ['A'].
- Repeat columnNumber - 1 times: from the front, turn every Z into A; if a letter remains, increment it, otherwise append a new A.
- 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();
}
}class Solution:
def convertToTitle(self, columnNumber: int) -> str:
rev = [0] # letter offsets, least significant first
for _ in range(columnNumber - 1):
i = 0
while i < len(rev) and rev[i] == 25:
rev[i] = 0
i += 1
if i == len(rev):
rev.append(0)
else:
rev[i] += 1
return "".join(chr(65 + d) for d in reversed(rev))class Solution {
public:
string convertToTitle(int columnNumber) {
string rev = "A";
for (int step = 1; step < columnNumber; step++) {
size_t i = 0;
while (i < rev.size() && rev[i] == 'Z') {
rev[i] = 'A';
i++;
}
if (i == rev.size()) rev.push_back('A');
else rev[i]++;
}
reverse(rev.begin(), rev.end());
return rev;
}
};function convertToTitle(columnNumber) {
const rev = [0]; // letter offsets, least significant first
for (let step = 1; step < columnNumber; step++) {
let i = 0;
while (i < rev.length && rev[i] === 25) {
rev[i] = 0;
i++;
}
if (i === rev.length) rev.push(0);
else rev[i]++;
}
return rev.reverse().map((d) => String.fromCharCode(65 + d)).join("");
}2Optimal (base 26 with digits 1 to 26)
O(log n)Each step divides n by 26, so there are at most 7 steps for a 32-bit int.O(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.
- While n > 0: n--, append 'A' + n % 26, then n /= 26.
- 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();
}
}class Solution:
def convertToTitle(self, columnNumber: int) -> str:
out = []
n = columnNumber
while n > 0:
n -= 1
out.append(chr(65 + n % 26))
n //= 26
return "".join(reversed(out))class Solution {
public:
string convertToTitle(int columnNumber) {
string out;
int n = columnNumber;
while (n > 0) {
n--;
out.push_back(char('A' + n % 26));
n /= 26;
}
reverse(out.begin(), out.end());
return out;
}
};function convertToTitle(columnNumber) {
const out = [];
let n = columnNumber;
while (n > 0) {
n--;
out.push(String.fromCharCode(65 + (n % 26)));
n = Math.floor(n / 26);
}
return out.reverse().join("");
}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.