Add solution #1504

JoshCrozier · JoshCrozier · commit f66637ea092e · 2025-04-16T12:23:30.000-05:00
diff --git a/README.md b/README.md
@@ -1,4 +1,4 @@
-# 1,333 LeetCode solutions in JavaScript
+# 1,334 LeetCode solutions in JavaScript
 
 [https://leetcodejavascript.com](https://leetcodejavascript.com)
 
@@ -1149,6 +1149,7 @@
 1499|[Max Value of Equation](./solutions/1499-max-value-of-equation.js)|Hard|
 1502|[Can Make Arithmetic Progression From Sequence](./solutions/1502-can-make-arithmetic-progression-from-sequence.js)|Easy|
 1503|[Last Moment Before All Ants Fall Out of a Plank](./solutions/1503-last-moment-before-all-ants-fall-out-of-a-plank.js)|Medium|
+1504|[Count Submatrices With All Ones](./solutions/1504-count-submatrices-with-all-ones.js)|Medium|
 1507|[Reformat Date](./solutions/1507-reformat-date.js)|Easy|
 1512|[Number of Good Pairs](./solutions/1512-number-of-good-pairs.js)|Easy|
 1519|[Number of Nodes in the Sub-Tree With the Same Label](./solutions/1519-number-of-nodes-in-the-sub-tree-with-the-same-label.js)|Medium|
diff --git a/solutions/1504-count-submatrices-with-all-ones.js b/solutions/1504-count-submatrices-with-all-ones.js
@@ -0,0 +1,39 @@
+/**
+ * 1504. Count Submatrices With All Ones
+ * https://leetcode.com/problems/count-submatrices-with-all-ones/
+ * Difficulty: Medium
+ *
+ * Given an m x n binary matrix mat, return the number of submatrices that have all ones.
+ */
+
+/**
+ * @param {number[][]} mat
+ * @return {number}
+ */
+var numSubmat = function(mat) {
+  const rows = mat.length;
+  const cols = mat[0].length;
+  const heights = new Array(cols).fill(0);
+  let result = 0;
+
+  for (let i = 0; i < rows; i++) {
+    const stack = [];
+    for (let j = 0; j < cols; j++) {
+      heights[j] = mat[i][j] === 1 ? heights[j] + 1 : 0;
+
+      while (stack.length && heights[j] <= heights[stack[stack.length - 1]]) {
+        stack.pop();
+      }
+
+      stack.push(j);
+
+      for (let k = 0; k < stack.length; k++) {
+        const height = heights[stack[k]];
+        const width = k === 0 ? stack[k] + 1 : stack[k] - stack[k - 1];
+        result += height * width;
+      }
+    }
+  }
+
+  return result;
+};
