algoadvance

You are given a string s that represents a range of cells in an Excel sheet, such as “K1:L2”. The range indicates that your task is to cover cells from the top-left cell to the bottom-right cell.

Return the list of cell names in order from the top-left to the bottom-right.

Example:

• Input: s = "K1:L2"
• Output: ["K1", "K2", "L1", "L2"]

Constraints:

• The input s will always be a valid range, formatted as two cell names separated by a colon (“:”).
• The starting cell will be the top-left cell, and the ending cell will be the bottom-right cell.

Clarifying Questions

1. Input Format:
   • Will there be single cells as well as ranges, or always ranges?
   • Will s always be a valid Excel range format?
2. Cell Range:
   • The specified range will always be rectangular, correct?
3. Column Names:
   • Are the column names always single English letters (A to Z)? Or do they extend to two letters (AA, AB, etc.)?

Assuming constraints generally imply:

• Single-column letters (A-Z).

Strategy

1. Parsing the Input:
   • Extract start and end cell references. For example, for s = "K1:L2", we separate it into start = "K1" and end = "L2".
2. Determining Ranges:
   • Identify the range of columns and rows.
   • Column letters need to be converted to ASCII values to determine the range.
   • Convert back to characters for the result.
   • Rows are straightforward numeric ranges.
3. Generating the List:
   • Use nested loops to cover all combinations of columns and rows between the start and end.

Code

def cellsInRange(s: str) -> List[str]:
    # Split the input
    start, end = s.split(':')
    
    # Extract column letters and row numbers
    start_col, start_row = start[0], int(start[1:])
    end_col, end_row = end[0], int(end[1:])
    
    # Generate the list of cells
    result = []
    for col in range(ord(start_col), ord(end_col) + 1):
        for row in range(start_row, end_row + 1):
            cell = f"{chr(col)}{row}"
            result.append(cell)
    
    return result

Time Complexity

• The time complexity of this algorithm is (O((n \times m))), where (n) is the number of columns and (m) is the number of rows in the specified range. This is because we generate all possible cells by iterating through every combination of columns and rows.

Explanation

1. Extract Columns and Rows:
   • start_col and end_col are the starting and ending columns in character form, converted to ASCII using ord.
   • start_row and end_row are the starting and ending rows in integer form.
2. Nested Loops:
   • First loop runs through columns from start_col to end_col.
   • Second nested loop runs through rows from start_row to end_row.
3. Result Generation:
   • Construct cell names using chr for columns and string concatenation for rows.
   • Append each constructed cell to the result list.

This approach ensures all cells within the specified range are covered correctly and efficiently.

Try our interview co-pilot at AlgoAdvance.com

• 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?