algoadvance

Leetcode 2194. Cells in a Range on an Excel Sheet

Problem Statement

You are given a string s representing the coordinates of cells in an Excel sheet in the format "A1:B2", where A1 and B2 represent the cells in the first and last columns and rows of the range respectively.

Return a list of strings representing all the cells in the range "A1:B2" inclusive in order.

Example

  1. Input: s = "K1:L2" Output: ["K1","K2","L1","L2"]
  2. Input: s = "A1:F1" Output: ["A1","B1","C1","D1","E1","F1"]

Clarifying Questions

  1. Q: What are the constraints on the input string s? A: The coordinates follow the format specified and always contain valid Excel column and row identifiers.

  2. Q: Should the output be sorted in any specific order? A: Yes, the output should be in lexicographical order traversing column-wise first then row-wise.

  3. Q: Are the columns always represented by uppercase letters? A: Yes, columns are represented by uppercase letters from ‘A’ to ‘Z’.

Strategy

  1. Parse the start and end columns, and start and end rows from the given string s.
  2. Iterate over each column from the start column to the end column.
  3. For each column, iterate through the rows from start to end.
  4. Create the cell name by combining the column and row, then add it to the result list.
  5. Return the result list.

Code

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<String> cellsInRange(String s) {
        List<String> result = new ArrayList<>();
        char startCol = s.charAt(0);
        char endCol = s.charAt(3);
        int startRow = Character.getNumericValue(s.charAt(1));
        int endRow = Character.getNumericValue(s.charAt(4));
        
        for (char col = startCol; col <= endCol; col++) {
            for (int row = startRow; row <= endRow; row++) {
                result.add("" + col + row);
            }
        }
        
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.cellsInRange("K1:L2"));
        System.out.println(sol.cellsInRange("A1:F1"));
    }
}

Time Complexity

The time complexity of this solution is (O((n_2 - n_1 + 1) \times (c_2 - c_1 + 1))), where (n_1) and (n_2) are the start and end row numbers, and (c_1) and (c_2) are the ASCII values of the start and end column characters. This time complexity accounts for the nested loops iterating through the rows and columns specified in the range.

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