# Design Excel Sum Formula

This page explains Java solution to problem `Design Excel Sum Formula` using `HashMap` data structure.

## Problem Statement

Your task is to design the basic function of Excel and implement the function of sum formula. Specifically, you need to implement the following functions:

• `Excel(int H, char W)`: This is the constructor. The inputs represents the height and width of the Excel form. `H` is a positive integer, range from `1` to `26`. It represents the height. `W` is a character range from `A` to `Z`. It represents that the width is the number of characters from `A` to `W`. The Excel form content is represented by a height * width `2D` integer array `C`, it should be initialized to zero. You should assume that the first row of `C` starts from `1`, and the first column of `C` starts from `A`.
• `void Set(int row, char column, int val)`: Change the value at `C(row, column)` to be val.
• `int Get(int row, char column)`: Return the value at `C(row, column)`.
• `int Sum(int row, char column, List of Strings : numbers)`: This function calculate and set the value at `C(row, column)`, where the value should be the sum of cells represented by numbers. This function return the sum result at `C(row, column)`. This sum formula should exist until this cell is overlapped by another value or another sum formula.

`numbers` is a list of strings that each string represent a cell or a range of cells. If the string represent a single cell, then it has the following format : ColRow. For example, `"F7"` represents the cell at `(7, F)`.

If the string represent a range of cells, then it has the following format : ColRow1:ColRow2. The range will always be a rectangle, and ColRow1 represent the position of the top-left cell, and ColRow2 represents the position of the bottom-right cell.

Example 1:

Input:
Excel(3,"C");
construct a 3 * 3 2D array with all zero.
A B C
1 0 0 0
2 0 0 0
3 0 0 0

Set(1, "A", 2);
set C(1,"A") to be 2.
A B C
1 2 0 0
2 0 0 0
3 0 0 0

Sum(3, "C", ["A1", "A1:B2"]);
set C(3,"C") to be the sum of value at C(1,"A") and the values sum of the rectangle range whose top-left cell is C(1,"A") and bottom-right cell is C(2,"B"). Return 4.
A B C
1 2 0 0
2 0 0 0
3 0 0 4

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.*;

class DesignExcelSumFormula {

private Cell[][] excel;

class Cell {
//A Cell can have a value
int val = 0;

//Or Cell can have formula
//key  : Cell Reference
//value: How many times Cell Reference has occurred in formula
HashMap<Cell, Integer> sumFormulaMap = new HashMap<>();

//Assigns
Cell(int val) {
setValue(val);
}

//Converts String Formula to Cell Reference
Cell(String[] formula) {
setFormula(formula);
}

public void setValue(int val) {
sumFormulaMap.clear();
this.val = val;
}

//Converts String Formula to Cell Reference
public void setFormula(String[] formulas) {
sumFormulaMap.clear();
for(String formula: formulas) {
int index = formula.indexOf(":");
if(index < 0) {
int[] pos = getPos(formula);
int row = pos;
int col = pos;
if(excel[row][col] == null) {
excel[row][col] = new Cell(0);
}
sumFormulaMap.put(excel[row][col], sumFormulaMap.getOrDefault(excel[row][col], 0) + 1);
}
else {
String[] range = formula.split(":");
int[] from = getPos(range);
int[] to = getPos(range);
for(int row = from; row <= to; row++) {
for(int col = from; col <= to; col++) {
if(excel[row][col] == null) {
excel[row][col] = new Cell(0);
}
sumFormulaMap.put(excel[row][col],
sumFormulaMap.getOrDefault(excel[row][col], 0) + 1);
}
}
}
}
}

public int getValue() {
if(sumFormulaMap.size() == 0) return val;
else {
int sum = 0;
for(Map.Entry<Cell, Integer> entry: sumFormulaMap.entrySet()) {
int cellValue = entry.getKey().getValue();
int ocurrance = entry.getValue();
sum += cellValue * ocurrance;
}
return sum;
}
}

private int[] getPos(String formula) {
int col = formula.charAt(0) - 'A';
int row = Integer.parseInt(formula.substring(1));
return new int[]{row, col};
}
}

public DesignExcelSumFormula(int H, char W) {
this.excel = new Cell[H + 1][W - 'A' + 1];
}

public void set(int r, char c, int v) {
if(excel[r][c - 'A'] == null) excel[r][c - 'A'] = new Cell(v);
else excel[r][c - 'A'].setValue(v);
}

public int get(int r, char c) {
if(excel[r][c - 'A'] == null) return 0;
else return excel[r][c - 'A'].getValue();
}

public int sum(int r, char c, String[] strs) {
if(excel[r][c - 'A'] == null) excel[r][c - 'A'] = new Cell(strs);
else excel[r][c - 'A'].setFormula(strs);
return excel[r][c - 'A'].getValue();
}
}

/**
* Your Excel object will be instantiated and called as such:
* Excel obj = new Excel(H, W);
* obj.set(r,c,v);
* int param_2 = obj.get(r,c);
* int param_3 = obj.sum(r,c,strs);
*/
``````

## Time Complexity

Set(int row, char column, int val) takes O(1)
Get(int row, char column) takes O(N)
int Sum(int row, char column, List of Strings : numbers) takes O(L)
Where N is total number Cell references we have in a formula
L is length of input list which has formulas

## Space Complexity

O(H, W) Where
H is number of rows in an excel
W is number of cols in an excel