LeetCode 2194 - Cells in a Range on an Excel Sheet

This problem is asking us to generate all the Excel-style cell references within a rectangular range given in string format. Each cell is identified by a column letter and a row number, for example "A1" or "K2".

leetcodeeasystring

LeetCode Problem 2194

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

This problem is asking us to generate all the Excel-style cell references within a rectangular range given in string format. Each cell is identified by a column letter and a row number, for example "A1" or "K2". The input string is formatted as "<col1><row1>:<col2><row2>", where <col1> and <col2> are uppercase letters indicating the starting and ending columns, and <row1> and <row2> are digits indicating the starting and ending rows. The constraints ensure that r1 <= r2 and c1 <= c2, so the range is always valid and non-empty.

The output must be a list of strings representing all cells within this rectangle, sorted first by column and then by row. This ordering is important because a naive iteration over rows first could produce an incorrect sequence. The problem guarantees a fixed, small input size (s.length == 5), so performance is not an issue, but correctness and ordering matter.

Edge cases include ranges that are single rows, single columns, or just a single cell. For example, "A1:A1" or "B2:B2" must return a single-element list. Since columns are letters, a common bug could be treating them numerically without converting from ASCII.

Approaches

The brute-force approach is straightforward: iterate over all possible columns from col1 to col2 and all possible rows from row1 to row2, constructing the cell string for each combination. Because the constraints are very small, this brute-force method is efficient enough, but it can be improved in clarity and simplicity by leveraging Python or Go’s range and character arithmetic.

The optimal approach is essentially the same as brute-force but with clean iteration using ASCII arithmetic for columns and integer arithmetic for rows. This ensures the cells are added in the required sorted order naturally, without any additional sorting step. Because the input is always guaranteed to have col1 <= col2 and row1 <= row2, this approach is simple, direct, and correct.

Approach Time Complexity Space Complexity Notes
Brute Force O((c2-c1+1)*(r2-r1+1)) O((c2-c1+1)*(r2-r1+1)) Iterates over all columns and rows, building strings
Optimal O((c2-c1+1)*(r2-r1+1)) O((c2-c1+1)*(r2-r1+1)) Iterates in column-major order using ASCII arithmetic

Algorithm Walkthrough

  1. Extract the start column (col1) and row (row1) from the first part of the string.
  2. Extract the end column (col2) and row (row2) from the second part of the string.
  3. Initialize an empty list to store the result cells.
  4. Loop over columns starting from col1 to col2. Convert letters to ASCII integers to make iteration easy.
  5. Inside the column loop, iterate over rows from row1 to row2.
  6. For each column-row combination, concatenate the column letter with the row number to form a cell string.
  7. Append each constructed cell string to the result list.
  8. After both loops complete, return the result list.

Why it works: By iterating over columns first and rows second, we guarantee the required sorting order. ASCII arithmetic ensures the column letters increment correctly, and integer iteration handles row numbers. Because the loops cover all values in the inclusive range, no cells are skipped.

Python Solution

from typing import List

class Solution:
    def cellsInRange(self, s: str) -> List[str]:
        col1, row1 = s[0], s[1]
        col2, row2 = s[3], s[4]
        
        result = []
        for c in range(ord(col1), ord(col2) + 1):
            for r in range(int(row1), int(row2) + 1):
                result.append(chr(c) + str(r))
        return result

Explanation: The code first extracts the start and end column letters and row digits from the input string. ord() converts letters to ASCII codes to facilitate iteration. Nested loops iterate over columns and rows, constructing each cell string by converting the column ASCII back to a character and concatenating the row. The resulting list naturally respects column-first order.

Go Solution

func cellsInRange(s string) []string {
    col1, row1 := s[0], s[1]
    col2, row2 := s[3], s[4]
    
    var result []string
    for c := col1; c <= col2; c++ {
        for r := row1; r <= row2; r++ {
            result = append(result, string(c)+string(r))
        }
    }
    return result
}

Go-specific notes: Go allows iteration over bytes, which works because the input uses ASCII letters and digits. string(c) converts a byte to a string. Unlike Python, Go strings are immutable, so each concatenation creates a new string. The result slice dynamically grows with append.

Worked Examples

Example 1: "K1:L2"

Column Loop Row Loop Cell Added
K 1 K1
K 2 K2
L 1 L1
L 2 L2

Result: ["K1","K2","L1","L2"]

Example 2: "A1:F1"

Column Loop Row Loop Cell Added
A 1 A1
B 1 B1
C 1 C1
D 1 D1
E 1 E1
F 1 F1

Result: ["A1","B1","C1","D1","E1","F1"]

Complexity Analysis

Measure Complexity Explanation
Time O((c2-c1+1)*(r2-r1+1)) Two nested loops over the column and row ranges.
Space O((c2-c1+1)*(r2-r1+1)) Storing each cell string in the result list.

Since the column and row ranges are always very small (single letters and single-digit rows), this is effectively O(1) in practice.

Test Cases

# Provided examples
assert Solution().cellsInRange("K1:L2") == ["K1","K2","L1","L2"]  # multiple columns and rows
assert Solution().cellsInRange("A1:F1") == ["A1","B1","C1","D1","E1","F1"]  # single row

# Single cell range
assert Solution().cellsInRange("C3:C3") == ["C3"]  # single cell

# Single column multiple rows
assert Solution().cellsInRange("B2:B5") == ["B2","B3","B4","B5"]

# Single row multiple columns
assert Solution().cellsInRange("D4:G4") == ["D4","E4","F4","G4"]

# Full range in smallest letters and rows
assert Solution().cellsInRange("A1:B2") == ["A1","A2","B1","B2"]
Test Why
"K1:L2" Validates multiple rows and columns, checks ordering
"A1:F1" Validates single row, multiple columns
"C3:C3" Single cell edge case
"B2:B5" Single column, multiple rows
"D4:G4" Single row, multiple columns
"A1:B2" Smallest range with multiple cells

Edge Cases

The first edge case is a range that consists of a single cell, such as "C3:C3". A naive implementation might try to loop beyond the start value, but the correct handling is to include exactly that cell. The solution correctly handles it because the loop boundaries are inclusive.

The second edge case is a single column with multiple rows, like "B2:B5". Here, it is important that the column does not increment and only the rows do. The implementation ensures this by keeping the column loop fixed over a single value and iterating the inner row loop normally.

The third edge case is a single row with multiple columns, for example "D4:G4". In this situation, it is important that the row remains constant while the columns increment. The nested loop structure of iterating columns in the outer loop and rows in the inner loop guarantees this is handled correctly. These three cases cover the potential pitfalls of off-by-one errors, incorrect ordering, and boundary handling.