#2194

Easy

auto_awesomeString-driven solution strategy

LeetCode Problem Workspace

Cells in a Range on an Excel Sheet

This problem requires extracting a range of cells from an Excel-like sheet based on a string input and returning them in a sorted list.

string

Problem Statement

You are given a string in the format "C1:D2" representing a range of cells on an Excel sheet. Here, the first part represents the column and row of the start cell, and the second part represents the column and row of the end cell. The task is to generate all the cells in the range such that the row and column indices are between the start and end values inclusive, and output them sorted first by column and then by row.

The cells should be returned in a list of strings, where each string corresponds to a cell in the format "". The list should be sorted by columns first, and then by rows within each column. For example, given "K1:L2", the output should be "K1", "K2", "L1", "L2".

Examples

Example 1

Input: s = "K1:L2"

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

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"]

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 Approach

Extract and Parse the Range

The first step is to extract the starting and ending column and row values from the input string. The column values (like 'A', 'K', etc.) need to be converted to numerical indices to iterate over them, while the row values can be treated directly as integers.

Iterate through the Range

Once the start and end values are identified, loop through each column in the range, and for each column, loop through the rows. For each combination of column and row, format the cell name as a string and add it to the result list.

Return the Sorted Result

The result should already be in sorted order due to the structure of the loop (columns first, then rows), so simply return the list once it’s populated with all the cell names.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this solution depends on the number of rows and columns in the given range, which is directly proportional to the difference between the start and end column/row values. Therefore, the time complexity is O(m * n), where m is the number of columns and n is the number of rows in the range. The space complexity is also O(m * n) as we need to store the list of cells.

What Interviewers Usually Probe

Can the candidate efficiently parse a string to extract multiple pieces of data?
Does the candidate account for the sorting requirement, ensuring the correct order of columns and rows?
Is the candidate aware of potential edge cases, such as minimal or maximal ranges?

Common Pitfalls or Variants

Common pitfalls

Forgetting to properly convert column letters to numeric values, which is critical for looping through columns.
Not handling the inclusive nature of the range properly, resulting in missing or extra cells.
Failing to consider that Excel columns are alphabetic (A, B, ..., Z, AA, AB, ...) rather than numeric, leading to incorrect column indexing.

Follow-up variants

Different representations of the input range (e.g., 'A1:B2' vs. 'A1:F5').
Modifying the format of the output (e.g., returning a 2D array instead of a 1D list).
Expanding the problem to support larger or dynamic Excel ranges with more rows/columns.

FAQ

What is the best way to parse the range string in this problem?

The most efficient way is to split the string based on the colon ':' to separate the starting and ending cells, then extract the individual column and row components from each part.

How should I handle columns like 'AA' or 'AZ'?

Columns in Excel follow an alphabetical pattern, so convert column letters to numbers by treating them like a base-26 numeral system (e.g., 'A' = 1, 'Z' = 26, 'AA' = 27).

What edge cases should I consider when solving the problem?

You should consider ranges with only one column or row, as well as ranges where the start and end cell are the same (e.g., 'A1:A1').

What if the input string has an invalid format?

The problem guarantees a valid format as per the constraints, so you don’t need to handle any invalid input scenarios.

How does GhostInterview help with solving this type of problem?

GhostInterview aids in understanding the parsing and iteration logic, ensures proper handling of sorting, and addresses common pitfalls, enhancing your overall problem-solving process.

terminal

Solution

Solution 1: Simulation

We directly traverse all the cells within the range and add them to the answer array.

1

2

3

4

5

6

7

class Solution:
    def cellsInRange(self, s: str) -> List[str]:
        return [
            chr(i) + str(j)
            for i in range(ord(s[0]), ord(s[-2]) + 1)
            for j in range(int(s[1]), int(s[-1]) + 1)
        ]

Continue Practicing

#2193 minimum number of moves to make palindrome #2186 minimum number of steps to make two strings anagram ii #2185 counting words with a given prefix