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.
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 the list 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.
Example 1:
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:
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 ':'.Problem Overview: The input is a string like "A1:C3" representing a rectangular range on an Excel sheet. You need to return every cell coordinate inside that range in lexicographic order (column first, then row). Each coordinate is formatted like A1, B2, etc.
Approach 1: Iterate through Columns and Rows (Time: O(k), Space: O(1) excluding output)
The range always contains a starting column, starting row, ending column, and ending row. Extract these four values directly from the string. Then iterate column-by-column from the start column to the end column, and inside that loop iterate row-by-row from the start row to the end row. For every pair, construct the coordinate string using the column character and row digit. This works because Excel ranges expand in a simple grid pattern, so a nested loop naturally generates the correct order.
This approach is essentially a small grid traversal. The total work depends on the number of cells in the range (k). Since the problem guarantees single-letter columns and single-digit rows, parsing is constant time and the nested iteration is straightforward. This is the most direct and commonly used solution for problems involving string parsing and simple simulation.
Approach 2: Using Cartesian Product (Time: O(k), Space: O(k))
Another way to view the problem is as a Cartesian product between the column range and the row range. First generate the list of columns (for example A, B, C) and the list of rows (1, 2, 3). Then combine every column with every row to produce the final coordinates. Many languages provide helpers for Cartesian products (such as itertools.product in Python), which makes this approach concise.
The key idea is separating the two dimensions of the grid before combining them. While the time complexity is still O(k), this version often creates intermediate lists for rows and columns, which slightly increases auxiliary memory usage. It is conceptually clean and useful when solving broader combinatorial or grid enumeration problems.
Recommended for interviews: The nested column-row iteration is what interviewers typically expect. It demonstrates clear string parsing and controlled iteration without unnecessary abstractions. The Cartesian product approach is equally correct but may feel like overengineering unless the language provides a very concise helper.
This approach involves parsing the input string to extract the start and end columns and rows. We then use nested loops; the outer loop traverses through the column range, and the inner loop processes the row range. For each combination of column and row, we construct the cell name and add it to the result list.
This solution extracts the starting and ending columns and rows from the input string. We calculate the total number of cells and allocate memory accordingly. Using two nested loops, we generate the cell names and store them in the result array.
Time Complexity: O((c2 - c1 + 1) * (r2 - r1 + 1)) where c1 and c2 are the start and end columns, and r1 and r2 are the start and end rows.
Space Complexity: O((c2 - c1 + 1) * (r2 - r1 + 1)) as we store all cell names in a list.
This approach involves extracting the individual ranges for columns and rows and using a Cartesian product to generate all possible cell combinations within the range.
This code utilizes a basic Cartesian product logic by iterating over start and end ranges for both columns and rows, thus combining them into all possible combinations.
Time Complexity: O((c2 - c1 + 1) * (r2 - r1 + 1))
Space Complexity: O((c2 - c1 + 1) * (r2 - r1 + 1))
| Approach | Complexity |
|---|---|
| Iterate through Columns and Rows | Time Complexity: O((c2 - c1 + 1) * (r2 - r1 + 1)) where c1 and c2 are the start and end columns, and r1 and r2 are the start and end rows. |
| Using Cartesian Product | Time Complexity: O((c2 - c1 + 1) * (r2 - r1 + 1)) |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterate through Columns and Rows | O(k) | O(1) | Best general solution. Simple nested loops generate cells directly in lexicographic order. |
| Cartesian Product of Rows and Columns | O(k) | O(k) | Useful when a language provides product utilities or when modeling the grid as two independent sets. |
2194. Cells in a Range on an Excel Sheet || Leetcode Weekly Contest 283 || Leetcode 2194 • Bro Coders • 2,474 views views
Watch 9 more video solutions →Practice Cells in a Range on an Excel Sheet with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor