Problem

A cell (r, c) of an excel sheet is represented as a string "<col><row>" where:

  • <col> denotes the column number c of the cell. It is represented by alphabetical letters.
    • For example, the 1st column is denoted by 'A', the 2nd by 'B', the 3rd by 'C', and so on.
  • <row> is the row number r of the cell. The rth row is represented by the integer r.

You are given a string s in the format "<col1><row1>:<col2><row2>", where <col1> represents the column c1, <row1> represents the row r1, <col2> represents the column c2, and <row2> represents the row r2, such that r1 <= r2 and c1 <= c2.

Return thelist of cells (x, y) such that r1 <= x <= r2 and c1 <= y <= c2. The cells should be represented as strings in the format mentioned above and be sorted in non-decreasing order first by columns and then by rows.

Examples

Example 1

1
2
3
4
5

Input: s = "K1:L2"
Output: ["K1","K2","L1","L2"]
Explanation:
The above diagram shows the cells which should be present in the list.
The red arrows denote the order in which the cells should be presented.

Example 2

1
2
3
4
5
6
7
8


    
Input: s = "A1:F1"
Output: ["A1","B1","C1","D1","E1","F1"]
Explanation:
The above diagram shows the cells which should be present in the list.
The red arrow denotes the order in which the cells should be presented.

Constraints

  • s.length == 5
  • 'A' <= s[0] <= s[3] <= 'Z'
  • '1' <= s[1] <= s[4] <= '9'
  • s consists of uppercase English letters, digits and ':'.

Solution

Method 1 – Brute Force Range Generation

Intuition: The problem is about generating all cell names in a rectangular range on an Excel sheet. Since the range is always valid and small, we can simply iterate over all columns and rows in the range and construct the cell names directly.

Approach:

  1. Parse the input string to extract the starting and ending columns and rows.
  2. Loop through all columns from start to end (using their ASCII values).
  3. For each column, loop through all rows from start to end.
  4. For each (column, row) pair, construct the cell name and add it to the result list.
  5. Return the result list sorted as required (columns first, then rows).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    vector<string> cellsInRange(string s) {
        vector<string> ans;
        char c1 = s[0], c2 = s[3];
        char r1 = s[1], r2 = s[4];
        for (char c = c1; c <= c2; ++c) {
            for (char r = r1; r <= r2; ++r) {
                ans.push_back(string(1, c) + r);
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9

func cellsInRange(s string) []string {
    var ans []string
    for c := s[0]; c <= s[3]; c++ {
        for r := s[1]; r <= s[4]; r++ {
            ans = append(ans, string([]byte{c, r}))
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public List<String> cellsInRange(String s) {
        List<String> ans = new ArrayList<>();
        char c1 = s.charAt(0), c2 = s.charAt(3);
        char r1 = s.charAt(1), r2 = s.charAt(4);
        for (char c = c1; c <= c2; ++c) {
            for (char r = r1; r <= r2; ++r) {
                ans.add("" + c + r);
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun cellsInRange(s: String): List<String> {
        val ans = mutableListOf<String>()
        val c1 = s[0]; val c2 = s[3]
        val r1 = s[1]; val r2 = s[4]
        for (c in c1..c2) {
            for (r in r1..r2) {
                ans.add("" + c + r)
            }
        }
        return ans
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def cellsInRange(self, s: str) -> list[str]:
        c1, r1, c2, r2 = s[0], s[1], s[3], s[4]
        ans = []
        for c in range(ord(c1), ord(c2)+1):
            for r in range(ord(r1), ord(r2)+1):
                ans.append(chr(c) + chr(r))
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn cells_in_range(s: String) -> Vec<String> {
        let (c1, r1, c2, r2) = (s.as_bytes()[0], s.as_bytes()[1], s.as_bytes()[3], s.as_bytes()[4]);
        let mut ans = Vec::new();
        for c in c1..=c2 {
            for r in r1..=r2 {
                ans.push(format!("{}{}", c as char, r as char));
            }
        }
        ans
    }
}

Complexity

  • ⏰ Time complexity: O((c2-c1+1) * (r2-r1+1))
  • 🧺 Space complexity: O((c2-c1+1) * (r2-r1+1))