D
DevExCode

LeetCode 631: Design Excel Sum Formula Solution

Master LeetCode problem 631 (Design Excel Sum Formula), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation:

To design Excel sum formula, we can use a two-dimensional array to store the values of cells in the Excel grid. We can also maintain a mapping from cell names to their corresponding row and column indices for easy access. When a cell's value is updated, we need to recursively update all the dependent cells that reference the updated cell in their formulas.

Algorithm:

  1. Create a two-dimensional array to store cell values.
  2. Create a mapping from cell names to their corresponding row and column indices.
  3. Implement a function to update cell value:
    • If the cell contains a number, update its value.
    • If the cell contains a formula, evaluate the formula by recursively calculating the values of referenced cells.
  4. Implement a function to get the value of a cell:
    • If the cell contains a number, return the number.
    • If the cell contains a formula, evaluate the formula by recursively calculating the values of referenced cells.

Time Complexity:

  • Updating a cell: O(N), where N is the number of cells dependent on the updated cell.
  • Getting the value of a cell: O(1).

Space Complexity:

  • O(R * C) for storing cell values, where R is the number of rows and C is the number of columns.
  • O(N) for maintaining the mapping of cell names to indices.

: :

Solution Code

class Excel {
    private int[][] grid;
    private Map<String, List<String>> formulaMap;

    public Excel(int H, char W) {
        grid = new int[H][W - 'A' + 1];
        formulaMap = new HashMap<>();
    }

    public void set(int r, char c, int v) {
        grid[r - 1][c - 'A'] = v;
        updateDependents(r, c);
    }

    private void updateDependents(int r, char c) {
        String cellName = "" + c + r;
        if (formulaMap.containsKey(cellName)) {
            for (String dependent : formulaMap.get(cellName)) {
                int dependentR = dependent.charAt(1) - '0';
                char dependentC = dependent.charAt(0);
                grid[dependentR - 1][dependentC - 'A'] = evaluateFormula(dependentR, dependentC);
                updateDependents(dependentR, dependentC);
            }
        }
    }

    private int evaluateFormula(int r, char c) {
        int sum = 0;
        String cellName = "" + c + r;
        for (String reference : formulaMap.get(cellName)) {
            int refR = reference.charAt(1) - '0';
            char refC = reference.charAt(0);
            if (Character.isDigit(refC))
                sum += Integer.parseInt(reference);
            else
                sum += grid[refR - 1][refC - 'A'];
        }
        return sum;
    }

    public int get(int r, char c) {
        return grid[r - 1][c - 'A'];
    }

    public void set(String r, char c, String[] strs) {
        String cellName = "" + c + r;
        formulaMap.put(cellName, new ArrayList<>(Arrays.asList(strs)));
        grid[r - 1][c - 'A'] = evaluateFormula(r, c);
        updateDependents(r, c);
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 631 (Design Excel Sum Formula)?

This page provides optimized solutions for LeetCode problem 631 (Design Excel Sum Formula) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 631 (Design Excel Sum Formula)?

The time complexity for LeetCode 631 (Design Excel Sum Formula) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 631 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 631 in Java, C++, or Python.

Back to LeetCode Solutions