commit d17fc79d3731489167a983ead40b150499cbd415
parent 3e752654e7d84fcec7519f719088757f74c0ded4
Author: Jack Sangdahl <jack@pngu.org>
Date: Thu, 2 Apr 2026 21:06:27 -0600
3661. maximum walls destroyed by robots
Diffstat:
2 files changed, 218 insertions(+), 0 deletions(-)
diff --git a/max_walls_destroy_robots.c b/max_walls_destroy_robots.c
@@ -0,0 +1,166 @@
+// 3661. Maximum Walls Destroyed by Robots
+#include "leetcode.h"
+
+/*
+ * there is an endless straight line populated with some robots and walls. you
+ * are given integer arrays 'robots', 'distance', and 'walls'. 'robots[i]' is
+ * the position of the i'th robot, 'distance[i]' is the maximum distance the
+ * i'th robot's bullet can travel, and 'walls[j]' is the position of the j'th
+ * wall. every robot has one bullet that can either fire to the left or right at
+ * most 'distance[i]'. a bullet destroys every wall in its path that lies within
+ * its range. robots are fixed obstacles. if a bullet hits another robot before
+ * reaching a wall, it immediately stops at that robot and cannot continue.
+ * return the maximum number of unique walls that can be dstroyed by the robots.
+ */
+
+struct hash_item {
+ int key;
+ int val;
+ UT_hash_handle hh;
+};
+
+struct hash_item *hash_find_item(struct hash_item **obj, int key) {
+ struct hash_item *p = NULL;
+ HASH_FIND_INT(*obj, &key, p);
+ return p;
+}
+
+bool hash_add_item(struct hash_item **obj, int key, int val) {
+ if (hash_find_item(obj, key))
+ return false;
+ struct hash_item *p = (struct hash_item *)malloc(sizeof(struct hash_item));
+ p->key = key;
+ p->val = val;
+ HASH_ADD_INT(*obj, key, p);
+ return true;
+}
+
+bool hash_set_item(struct hash_item **obj, int key, int val) {
+ struct hash_item *p = hash_find_item(obj, key);
+ if (!p)
+ hash_add_item(obj, key, val);
+ else
+ p->val = val;
+ return true;
+}
+
+int hash_get_item(struct hash_item **obj, int key, int def_val) {
+ struct hash_item *p = hash_find_item(obj, key);
+ if (!p)
+ return def_val;
+ return p->val;
+}
+
+void hash_free(struct hash_item **obj) {
+ struct hash_item *curr = NULL, *tmp = NULL;
+ HASH_ITER(hh, *obj, curr, tmp) {
+ HASH_DEL(*obj, curr);
+ free(curr);
+ }
+}
+
+int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); }
+
+int lower_bound(int *arr, int n, int target) {
+ int left = 0, right = n;
+ while (left < right) {
+ int mid = left + (right - left) / 2;
+ if (arr[mid] < target)
+ left = mid + 1;
+ else
+ right = mid;
+ }
+ return left;
+}
+
+int upper_bound(int *arr, int n, int target) {
+ int left = 0, right = n;
+ while (left < right) {
+ int mid = left + (right - left) / 2;
+ if (arr[mid] <= target)
+ left = mid + 1;
+ else
+ right = mid;
+ }
+ return left;
+}
+
+int maxWalls(int *robots, int robotsSize, int *distance, int distanceSize,
+ int *walls, int wallsSize) {
+ int n = robotsSize;
+ int *left = (int *)calloc(n, sizeof(int));
+ int *right = (int *)calloc(n, sizeof(int));
+ int *num = (int *)calloc(n, sizeof(int));
+ struct hash_item *robot_dist = NULL;
+ for (int i = 0; i < n; i++)
+ hash_add_item(&robot_dist, robots[i], distance[i]);
+ int *sorted_robots = (int *)malloc(n * sizeof(int));
+ memcpy(sorted_robots, robots, n * sizeof(int));
+ qsort(sorted_robots, n, sizeof(int), cmp);
+ int *sorted_walls = (int *)malloc(wallsSize * sizeof(int));
+ memcpy(sorted_walls, walls, wallsSize * sizeof(int));
+ qsort(sorted_walls, wallsSize, sizeof(int), cmp);
+ for (int i = 0; i < n; i++) {
+ int p1 = upper_bound(sorted_walls, wallsSize, sorted_robots[i]), lp;
+ if (i >= 1) {
+ int lb = fmax(sorted_robots[i] -
+ hash_get_item(&robot_dist, sorted_robots[i], 0),
+ sorted_robots[i - 1] + 1);
+ lp = lower_bound(sorted_walls, wallsSize, lb);
+ } else
+ lp = lower_bound(sorted_walls, wallsSize,
+ sorted_robots[i] -
+ hash_get_item(&robot_dist, sorted_robots[i], 0));
+ left[i] = p1 - lp;
+ int rp;
+ if (i < n - 1) {
+ int rb = fmin(sorted_robots[i] +
+ hash_get_item(&robot_dist, sorted_robots[i], 0),
+ sorted_robots[i + 1] - 1);
+ rp = upper_bound(sorted_walls, wallsSize, rb);
+ } else
+ rp = upper_bound(sorted_walls, wallsSize,
+ sorted_robots[i] +
+ hash_get_item(&robot_dist, sorted_robots[i], 0));
+ int p2 = lower_bound(sorted_walls, wallsSize, sorted_robots[i]);
+ right[i] = rp - p2;
+ if (!i)
+ continue;
+ int p3 = lower_bound(sorted_walls, wallsSize, sorted_robots[i - 1]);
+ num[i] = p1 - p3;
+ }
+ int sl = left[0], sr = right[0];
+ for (int i = 1; i < n; i++) {
+ int cl = fmax(sl + left[i],
+ sr - right[i - 1] + fmin(left[i] + right[i - 1], num[i]));
+ int cr = fmax(sl + right[i], sr + right[i]);
+ sl = cl;
+ sr = cr;
+ }
+ int ans = fmax(sl, sr);
+ free(left);
+ free(right);
+ free(num);
+ free(sorted_robots);
+ free(sorted_walls);
+ hash_free(&robot_dist);
+ return ans;
+}
+
+int main() {
+ int r1[] = {4}, d1[] = {3}, w1[] = {1, 10};
+ int r2[] = {10, 2}, d2[] = {5, 1}, w2[] = {5, 2, 7};
+ int r3[] = {1, 2}, d3[] = {100, 1}, w3[] = {10};
+ int mw1 =
+ maxWalls(r1, ARRAY_SIZE(r1), d1, ARRAY_SIZE(d1), w1, ARRAY_SIZE(w1));
+ int mw2 =
+ maxWalls(r2, ARRAY_SIZE(r2), d2, ARRAY_SIZE(d2), w2, ARRAY_SIZE(w2));
+ int mw3 =
+ maxWalls(r3, ARRAY_SIZE(r3), d3, ARRAY_SIZE(d3), w3, ARRAY_SIZE(w3));
+ printf("%d\n", mw1);
+ assert(mw1 == 1);
+ printf("%d\n", mw2);
+ assert(mw2 == 3);
+ printf("%d\n", mw3);
+ assert(mw3 == 0);
+}
diff --git a/max_walls_destroy_robots.py b/max_walls_destroy_robots.py
@@ -0,0 +1,52 @@
+# 3661. Maximum Walls Destroyed by Robots
+import bisect
+from typing import List
+
+"""
+there is an endless straight line populated with some robots and walls. you
+are given integer arrays 'robots', 'distance', and 'walls'. 'robots[i]' is
+the position of the i'th robot, 'distance[i]' is the maximum distance the
+i'th robot's bullet can travel, and 'walls[j]' is the position of the j'th
+wall. every robot has one bullet that can either fire to the left or right at
+most 'distance[i]'. a bullet destroys every wall in its path that lies within
+its range. robots are fixed obstacles. if a bullet hits another robot before
+reaching a wall, it immediately stops at that robot and cannot continue.
+return the maximum number of unique walls that can be dstroyed by the robots.
+"""
+
+
+class Solution:
+ def maxWalls(self, robots: List[int], distance: List[int], walls: List[int]) -> int:
+ sorted_robots = sorted(zip(robots, distance))
+ n = len(sorted_robots)
+ walls.sort()
+
+ def count(l, r):
+ if l > r:
+ return 0
+ return bisect.bisect_right(walls, r) - bisect.bisect_left(walls, r)
+
+ avail = 0
+ used = count(sorted_robots[0][0] - A[0][1], A[0][0] - 1)
+ sorted_robots.append([float("inf"), 0])
+ for i in range(n):
+ l, dl = sorted_robots[i]
+ r, dr = sorted_robots[i + 1]
+ l1, r1 = l + 1, min(l + dl, r - 1)
+ l2, r2 = max(r - dr, l + 1), r - 1
+ left = count(l1, r1)
+ right = count(l2, r2)
+ both = left + right - count(max(l1, l2), min(r1, r2))
+ navail = max(avail + left, used)
+ nused = max(avail + both, used + right)
+ avail, used = navail, nused
+ for x in set(x for x, _ in sorted_robots):
+ used += count(x, x)
+ return used
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maxWalls(robots=[4], distance=[3], walls=[1, 10]))
+ print(obj.maxWalls(robots=[10, 2], distance=[5, 1], walls=[5, 2, 7]))
+ print(obj.maxWalls(robots=[1, 2], distance=[100, 1], walls=[10]))
