sprintly 10!!

sprintly10.js

// iterative solution --> time complexity O(width * height * height) aka n^3
const gridSum = (grid) => {
  const upsideDownGrid = grid.reverse();
  let maxSum = 0;

  for (let i = 0; i < upsideDownGrid.length; i++) {
    let currSum = 0;
    let maxForRow = 0;
    for (let j = 0; j < upsideDownGrid[i].length; j++) {
      if (upsideDownGrid[i][j] === 1) {
        let colSum = 0;
        for (let k = i; k < upsideDownGrid.length; k++) {
          if (upsideDownGrid[k][j] === 1) {
            colSum++
          } else {
            break;
          }
        }
        currSum += colSum;
      } else {
        maxForRow = maxForRow > currSum ? maxForRow : currSum;
        currSum = 0;
      }
    }
    if (maxForRow > maxSum) {
      maxSum = maxForRow;
    }
  }

  return maxSum;
};

const transFormColumn = (matrix, xIdx) => {
  const recurse = (yIdx) => {
    if (yIdx > matrix.length - 1) return 0;
    if (matrix[yIdx][xIdx] === 0) {
      recurse(yIdx + 1);
      return 0;
    }

    let sumForIdx = 1 + recurse(yIdx + 1);
    matrix[yIdx][xIdx] = sumForIdx;
    return sumForIdx;
  };

  recurse(0);
  return matrix;
};

const gridSumDynamic = (grid) => {
  const deepCopy = grid.map(row => [...row]);

  let upsideDownGrid = deepCopy.reverse();
  const gridWidth = deepCopy[0].length;
  for (let i = 0; i < gridWidth; i++) {
    upsideDownGrid = transFormColumn(upsideDownGrid, i);
  }

  const dynamicGrid = upsideDownGrid.reverse();
  const largestGroupInEachRow = dynamicGrid.map((row) => {
    const largestSumEachRow = row.reduce(({ currentSum, maxSum }, val) => {
      if (val !== 0) {
        currentSum += val;
        maxSum = maxSum > currentSum ? maxSum : currentSum;
      } else {
        currentSum = 0;
      }

      return { currentSum, maxSum };
    }, { currentSum: 0, maxSum: 0 });
    return largestSumEachRow.maxSum;
  });
  return largestGroupInEachRow.reduce((acc, cv) => acc > cv ? acc : cv, 0);
};

const grid1 = [
  [1, 0, 1],
  [0, 1, 1],
  [1, 1, 1],
];

const grid2 = [
  [0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1],
  [1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0],
  [1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0],
  [1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0],
  [0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1],
  [0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1],
  [0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0],
  [1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1],
  [0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0],
  [1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1],
  [1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1],
  [0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0],
  [0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
  [0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1],
  [0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0],
  [0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1],
  [0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0],
  [1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1],
  [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0],
];

console.log(gridSumDynamic(grid2)); // 20
console.log(gridSum(grid2)); // 20