2194. Cells in a Range on an Excel Sheet

EasyString

Problem Description

The problem provides a way to represent the positions of cells in an Excel sheet, using a combination of columns denoted by alphabetical letters and rows denoted by integers. Here, we are given a range in the format <col1><row1>:<col2><row2> which refers to a rectangle on the spreadsheet. The <col1> and <col2> are the start and end column letters, and <row1> and <row2> are the start and end row numbers, respectively. The task is to list all cells within this range inclusively, sorted first by columns and then by rows. Each cell should be represented by its respective column letter followed by its row number.

Intuition

To solve this problem intuitively, consider how you would manually list all cells if given a range on a real Excel sheet; you would likely start from the top left cell and move horizontally until you reach the end of a row, and then move down to the next row and repeat until the entire range is covered.

The intuition behind the solution is derived from this manual process. Here's how we translate the process into the solution approach:

Convert the start and end columns from letter to their corresponding ASCII values using ord(). This will allow us to iterate over the columns numerically.
Convert the start and end row numbers to integers to iterate over them numerically.
Use a nested loop to generate all combinations of column letters and row numbers within the specified range. The outer loop iterates over the ASCII values for columns, converting them back to letters using chr(), while the inner loop iterates over the row numbers.
During each iteration, concatenate the column letter and row number to form the cell representation, such as 'A1', 'A2', etc.
The loops are ordered to match the expected sorting of the result, by columns first and then by rows.

By using this approach, we cover all cells within the specified range systematically, and construct the list in the required sorted order.

Solution Approach

The solution implements a simple but effective approach that leverages Python's list comprehension and character manipulation functions. No advanced data structures are needed as the problem only requires generating a range of string identifiers for Excel cells. The Python code provided uses nested loops inside a list comprehension to generate the result directly.

Here's the step-by-step walk-through of the implementation:

Extracting Column and Row Range Boundaries: The given string s, representing the cell range in the format <col1><row1>:<col2><row2>, is dissected to get the starting and ending characters for columns (s[0] and s[3], respectively) and integers for row numbers (s[1] and s[4]).
Iterating Over Column Characters (Alphabetical Letters):
- Convert the start column character s[0] and end column character s[3] to their ASCII values using ord(). This provides a numeric range that can be used in the loop.
- A for loop is constructed to iterate over this numeric range using for i in range(ord(s[0]), ord(s[3]) + 1). The + 1 is necessary to include the end column in the range.
Iterating Over Row Numbers (Integers):
- Similarly, the row numbers are parsed as integers.
- A nested for loop is used to iterate over the rows for each column, with for j in range(int(s[1]), int(s[4]) + 1), including the end row in the range.
Generating Cell Identifiers:
- Inside the nested loop, the code concatenates the current column letter and row number to form the cell identifier. It uses chr(i) to convert the ASCII value back to a letter and str(j) to convert the row number to string.
- The result of the concatenation chr(i) + str(j) is the cell identifier in the required format (e.g., 'A1').
List Comprehension:
- The entire process takes place within a list comprehension, allowing for concise representation and direct output of the full list of strings representing the cell range.

The algorithm's time complexity is O(N*M), where N is the number of columns within the range and M is the number of rows in the range, as it iterates once for each cell in the rectangular area defined by the input string.

The solution can be stated succinctly as: Generate all combinations of columns and rows in the given range using nested iterations, and construct the cell identifier for each combination in the correct format.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a small example to illustrate the solution approach. Suppose the range provided is "B2:C3". This denotes a rectangle on the spreadsheet that starts at column B, row 2, and ends at column C, row 3.

Here's how the solution approach is applied to this example:

Extracting Column and Row Range Boundaries: We dissect the string "B2:C3" to find the starting and ending characters for columns and integers for row numbers. In this case, col1 is 'B', row1 is '2', col2 is 'C', and row2 is '3'.
Iterating Over Column Characters (Alphabetical Letters):
- Convert 'B' and 'C' to their ASCII values using ord(), resulting in 66 for 'B' and 67 for 'C'.
- Construct a for loop to iterate over the ASCII range: for i in range(66, 68) (68 because we include 'C').
Iterating Over Row Numbers (Integers):
- Convert '2' and '3' to integers, getting 2 and 3.
- For each column letter in the outer loop, a nested for loop iterates over the row numbers: for j in range(2, 4) (4 because we include row 3).
Generating Cell Identifiers:
- In the nested loop, for every combination of column and row, concatenate the column letter (converted back from ASCII) and row number to form the cell identifier. For example, chr(66) + str(2) becomes 'B2'.
List Comprehension:
- All these steps take place within a list comprehension: [chr(i) + str(j) for i in range(66, 68) for j in range(2, 4)].

Executing this list comprehension, we should get the list of cell identifiers: ["B2", "B3", "C2", "C3"]. These are all the cells included in the Excel range "B2:C3", sorted by columns first and then by rows.

Solution Implementation

1from typing import List
2
3class Solution:
4    def cellsInRange(self, s: str) -> List[str]:
5        # Initialize an empty list to hold the cell range.
6        cell_range = []
7      
8        # Iterate over the character part of the range, from the start to the end character.
9        for col_char in range(ord(s[0]), ord(s[3]) + 1):
10            # Iterate over the numeric part of the range, from the start to the end number.
11            for row_num in range(int(s[1]), int(s[4]) + 1):
12                # Construct the cell label by combining the character and the number as a string,
13                # and append each cell label to the cell range list.
14                cell_range.append(chr(col_char) + str(row_num))
15      
16        # Return the list containing the range of cell labels.
17        return cell_range
18

1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5    // Method to return a list of cell labels in the range specified by the input string s
6    public List<String> cellsInRange(String s) {
7        // List to store the answer
8        List<String> cellRangeList = new ArrayList<>();
9      
10        // Start column character (e.g., 'A')
11        char startColumn = s.charAt(0);
12        // Start row character (e.g., '1')
13        char startRow = s.charAt(1);
14        // End column character (e.g., 'D')
15        char endColumn = s.charAt(3);
16        // End row character (e.g., '5')
17        char endRow = s.charAt(4);
18      
19        // Loop from start column to end column
20        for (char column = startColumn; column <= endColumn; ++column) {
21            // Nested loop from start row to end row
22            for (char row = startRow; row <= endRow; ++row) {
23                // Add the cell label (e.g., 'A1') to the list
24                cellRangeList.add("" + column + row);
25            }
26        }
27        // Return the list containing all cell labels in the range
28        return cellRangeList;
29    }
30}
31

1#include <vector>
2#include <string>
3
4class Solution {
5public:
6    // Function to generate all cell names in the range specified by the input string
7    std::vector<std::string> cellsInRange(const std::string& range) {
8        // Initialize a vector to store the result
9        std::vector<std::string> result;
10
11        // Loop over each column character from the starting column to the ending column
12        for (char col = range[0]; col <= range[3]; ++col) {
13            // Loop over each row character from the starting row to the ending row
14            for (char row = range[1]; row <= range[4]; ++row) {
15                // Combine the current column and row characters to form a cell name
16                std::string cellName = {col, row};
17              
18                // Add the generated cell name to the result vector
19                result.push_back(cellName);
20            }
21        }
22
23        // Return the generated list of cell names
24        return result;
25    }
26};
27

1// Import statements are not necessary in TypeScript for such a simple snippet of code.
2
3// Function to generate all cell names in the range specified by the input string
4function cellsInRange(range: string): string[] {
5    // Initialize an array to store the result
6    let result: string[] = [];
7
8    // Loop over each column character from the starting to the ending column
9    for (let col = range.charCodeAt(0); col <= range.charCodeAt(3); ++col) {
10        // Loop over each row character from the starting to the ending row
11        for (let row = range.charCodeAt(1); row <= range.charCodeAt(4); ++row) {
12            // Convert ASCII codes back to characters and combine them to form a cell name
13            let cellName = String.fromCharCode(col) + String.fromCharCode(row);
14          
15            // Add the generated cell name to the result array
16            result.push(cellName);
17        }
18    }
19
20    // Return the generated list of cell names
21    return result;
22}
23

Time and Space Complexity

The given Python code is a one-liner list comprehension that generates a list of cell labels within a given range in a spreadsheet. The range is described by a string s, where s[0] and s[1] represent the column letter and row number of the top-left corner, and s[-2] and s[-1] represent the column letter and row number of the bottom-right corner, respectively.

The time complexity of the code can be analyzed based on the number of iterations the list comprehension performs. It iterates through all the columns from s[0] to s[-2] and, for each column, iterates through all the rows from s[1] to s[-1]. If C is the number of columns and R is the number of rows in the range, the total iterations will be C * R.

The number of columns is ord(s[-2]) - ord(s[0]) + 1.
The number of rows is int(s[-1]) - int(s[1]) + 1.

So, the time complexity is O(C * R).

The space complexity of the code corresponds to the amount of space used to store the output list. Since the list comprehension generates a list with one item for every cell in the range, the space complexity is proportional to the number of cells in the output list, which is also C * R.

The space complexity is also O(C * R).

Hence, both the time complexity and space complexity of the code are O(C * R) where C is the number of columns spanned by the range and R is the number of rows spanned by the range.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know