Design excel sum formula

Array Hash Table String Graph Theory Design Topological Sort Matrix

39.9% acceptance

Mar 31, 2026

281

296

Design the basic function of Excel and implement the function of the sum formula. Implement the Excel class: Excel(int height, char width) Initializes the object with the height and the width of the sheet. The sheet is an integer matrix mat of size height x width with the row index in the range [1, height] and the column index in the range ['A', width]. All the values should be zero initially. void set(int row, char column, int val) Changes the value at mat[row][column] to be val. int get(int row, char column) Returns the value at mat[row][column]. int sum(int row, char column, List numbers) Sets the value at mat[row][column] to be the sum of cells represented by numbers and returns the value at mat[row][column]. This sum formula should exist until this cell is overlapped by another value or another sum formula. numbers[i] could be on the format: "ColRow" that represents a single cell. For example, "F7" represents the cell mat[7]['F']. "ColRow1:ColRow2" that represents a range of cells. The range will always be a rectangle where "ColRow1" represent the position of the top-left cell, and "ColRow2" represents the position of the bottom-right cell. For example, "B3:F7" represents the cells mat[i][j] for 3 <= i <= 7 and 'B' <= j <= 'F'. Note: You could assume that there will not be any circular sum reference. For example, mat[1]['A'] == sum(1, "B") and mat[1]['B'] == sum(1, "A").

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

use std::collections::HashMap;

struct Excel {
  mat: Vec<Vec<i32>>,
  formulas: HashMap<(usize, usize), Vec<(usize, usize)>>,
}

impl Excel {
  fn new(height: i32, width: char) -> Self {
    let h = height as usize;
    let w = (width as u8 - b'A' + 1) as usize;
    Excel {
      mat: vec![vec![0; w]; h],
      formulas: HashMap::new(),
    }
  }

  fn set(&mut self, row: i32, column: char, val: i32) {
    let r = (row - 1) as usize;
    let c = (column as u8 - b'A') as usize;
    self.formulas.remove(&(r, c));
    self.mat[r][c] = val;
  }

  fn get(&self, row: i32, column: char) -> i32 {
    let mut cache = HashMap::new();
    self.get_cached(row, column, &mut cache)
  }

  fn get_cached(&self, row: i32, column: char, cache: &mut HashMap<(usize, usize), i32>) -> i32 {
    let r = (row - 1) as usize;
    let c = (column as u8 - b'A') as usize;
    if let Some(&v) = cache.get(&(r, c)) {
      return v;
    }
    let val = if let Some(refs) = self.formulas.get(&(r, c)) {
      let refs = refs.clone();
      refs.iter().map(|&(rr, cc)| self.get_cached(rr as i32 + 1, (b'A' + cc as u8) as char, cache)).sum()
    } else {
      self.mat[r][c]
    };
    cache.insert((r, c), val);
    val
  }

  fn sum(&mut self, row: i32, column: char, numbers: Vec<String>) -> i32 {
    let r = (row - 1) as usize;
    let c = (column as u8 - b'A') as usize;
    let refs = Self::parse_refs(&numbers);
    self.formulas.insert((r, c), refs);
    let val = self.get(row, column);
    self.mat[r][c] = val;
    val
  }

  fn parse_refs(numbers: &[String]) -> Vec<(usize, usize)> {
    let mut refs = Vec::new();
    for num in numbers {
      if let Some(idx) = num.find(':') {
        let (r1, c1) = Self::parse_cell(&num[..idx]);
        let (r2, c2) = Self::parse_cell(&num[idx + 1..]);
        for r in r1..=r2 {
          for c in c1..=c2 {
            refs.push((r, c));
          }
        }
      } else {
        refs.push(Self::parse_cell(num));
      }
    }
    refs
  }

  fn parse_cell(s: &str) -> (usize, usize) {
    let col = (s.as_bytes()[0] - b'A') as usize;
    let row: usize = s[1..].parse::<usize>().unwrap() - 1;
    (row, col)
  }
}