algoadvance

Leetcode 2194. Cells in a Range on an Excel Sheet

Problem Statement

You are given a string s that represents the column range in an Excel sheet and two integers row1 and row2 that represent the row range.

The string s is of the form "A1:C3", representing cells from the column represented by A to C and from row 1 to 3.

You need to return a list of all the cells in the range in sorted order.

Example

• Input:

    string s = "K1:L2";
    int row1 = 1;
    int row2 = 2;
  

• Output:

    vector<string> = {"K1", "K2", "L1", "L2"};
  

Clarifying Questions

1. Formatting of Output: Should the list be sorted in lexicographical order?
   • Yes, the list should naturally be in lexicographical order if we iterate from the start of the column and row ranges to the end.
2. Column Limits: How many columns can there be?
   • The column range seems to be from ‘A’ to ‘Z’, which ensures handling this problem within a single alphabet range.
3. Input Assumptions: Are inputs always valid and within expected ranges?
   • Yes, you can assume the inputs will be valid, within the ranges mentioned.

Strategy

To solve this problem:

1. Parse the input string s to extract the start and end columns.
2. Use the two integers row1 and row2 directly to iterate over the rows.
3. Construct the cell strings within the specified ranges and collect them into a vector.

Steps:

1. Get the substring before the colon (representing the start cell) and after (representing the end cell).
2. Extract the starting and ending columns and rows.
3. Iterate from the starting column to the ending column and within this loop, iterate from the starting row to the ending row to construct each cell.
4. Collect all constructed cells in a vector and return.

Code

#include <vector>
#include <string>
using namespace std;

vector<string> cellsInRange(string s, int row1, int row2) {
    vector<string> result;

    // Extract starting and ending column characters
    char startCol = s[0];
    char endCol = s[3];
    
    // Extract starting and ending rows
    int startRow = s[1] - '0';
    int endRow = s[4] - '0';
    
    // Iterate over columns from startCol to endCol
    for (char col = startCol; col <= endCol; ++col) {
        // Iterate over rows from startRow to endRow
        for (int row = row1; row <= row2; ++row) {
            // Construct the cell string
            string cell = string(1, col) + to_string(row);
            result.push_back(cell);
        }
    }
    
    return result;
}

Time Complexity

The time complexity is (O(C \times R)), where:

• (C) is the number of columns in the range (which is 26 - A + 1 at most = 26).
• (R) is the number of rows in the range.

In each iteration, you create one cell string and add it to the vector, leading to a linear complexity relative to the number of cells.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?