Add solution #1257

JoshCrozier · JoshCrozier · commit 3c3ed98dacd2 · 2025-06-29T23:20:28.000-05:00
diff --git a/README.md b/README.md
@@ -1166,6 +1166,7 @@
 1254|[Number of Closed Islands](./solutions/1254-number-of-closed-islands.js)|Medium|
 1255|[Maximum Score Words Formed by Letters](./solutions/1255-maximum-score-words-formed-by-letters.js)|Hard|
 1256|[Encode Number](./solutions/1256-encode-number.js)|Medium|
+1257|[Smallest Common Region](./solutions/1257-smallest-common-region.js)|Medium|
 1260|[Shift 2D Grid](./solutions/1260-shift-2d-grid.js)|Easy|
 1261|[Find Elements in a Contaminated Binary Tree](./solutions/1261-find-elements-in-a-contaminated-binary-tree.js)|Medium|
 1262|[Greatest Sum Divisible by Three](./solutions/1262-greatest-sum-divisible-by-three.js)|Medium|
diff --git a/solutions/1257-smallest-common-region.js b/solutions/1257-smallest-common-region.js
@@ -0,0 +1,56 @@
+/**
+ * 1257. Smallest Common Region
+ * https://leetcode.com/problems/smallest-common-region/
+ * Difficulty: Medium
+ *
+ * You are given some lists of regions where the first region of each list directly contains
+ * all other regions in that list.
+ *
+ * If a region x contains a region y directly, and region y contains region z directly, then
+ * region x is said to contain region z indirectly. Note that region x also indirectly contains
+ * all regions indirectly containd in y.
+ *
+ * Naturally, if a region x contains (either directly or indirectly) another region y, then x
+ * is bigger than or equal to y in size. Also, by definition, a region x contains itself.
+ *
+ * Given two regions: region1 and region2, return the smallest region that contains both of them.
+ *
+ * It is guaranteed the smallest region exists.
+ */
+
+/**
+ * @param {string[][]} regions
+ * @param {string} region1
+ * @param {string} region2
+ * @return {string}
+ */
+var findSmallestRegion = function(regions, region1, region2) {
+  const map = new Map();
+
+  for (const region of regions) {
+    const parent = region[0];
+    for (let i = 1; i < region.length; i++) {
+      map.set(region[i], parent);
+    }
+  }
+
+  const path1 = getPath(region1);
+  const path2 = getPath(region2);
+  const set = new Set(path1);
+
+  for (const ancestor of path2) {
+    if (set.has(ancestor)) {
+      return ancestor;
+    }
+  }
+
+  function getPath(region) {
+    const path = [];
+    let current = region;
+    while (current) {
+      path.push(current);
+      current = map.get(current);
+    }
+    return path;
+  }
+};
