robots, distance, and walls:robots[i] is the position of the ith robot.distance[i] is the maximum distance the ith robot's bullet can travel.walls[j] is the position of the jth wall.Every robot has one bullet that can either fire to the left or the right at most distance[i] meters.
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 destroyed by the robots.
Notes:
Example 1:
Input: robots = [4], distance = [3], walls = [1,10]
Output: 1
Explanation:
robots[0] = 4 fires left with distance[0] = 3, covering [1, 4] and destroys walls[0] = 1.Example 2:
Input: robots = [10,2], distance = [5,1], walls = [5,2,7]
Output: 3
Explanation:
robots[0] = 10 fires left with distance[0] = 5, covering [5, 10] and destroys walls[0] = 5 and walls[2] = 7.robots[1] = 2 fires left with distance[1] = 1, covering [1, 2] and destroys walls[1] = 2.Input: robots = [1,2], distance = [100,1], walls = [10]
Output: 0
Explanation:
In this example, only robots[0] can reach the wall, but its shot to the right is blocked by robots[1]; thus the answer is 0.
Constraints:
1 <= robots.length == distance.length <= 1051 <= walls.length <= 1051 <= robots[i], walls[j] <= 1091 <= distance[i] <= 105robots are uniquewalls are uniqueProblem Overview: You are given robots with certain capabilities and a sequence of walls with constraints on when they can be destroyed. The task is to determine the maximum number of walls robots can destroy while respecting the ordering and capability limits. The challenge is choosing the optimal sequence of robot actions without violating constraints.
Approach 1: Brute Force Recursive Search (Exponential Time, O(n) Space)
The most direct way is to try every possible assignment of robots to walls. For each wall, recursively decide whether the current robot destroys it or skip to another option. This forms a decision tree exploring all combinations. While easy to reason about, the state space grows exponentially because each decision branches into multiple possibilities. Time complexity is O(2^n) in the worst case with recursion depth using O(n) space.
Approach 2: Memoized Search with Sorting and Binary Search (O(n log n) Time, O(n) Space)
The optimized solution relies on sorting the walls or robot capabilities to process them in a consistent order. Once sorted, a recursive dynamic programming function explores the maximum number of walls that can be destroyed starting from a given index. Instead of recomputing states, results are cached in a memo table. When deciding the next valid wall or robot transition, binary search quickly finds the next feasible position, avoiding a linear scan.
This reduces repeated exploration of identical states. Each wall index is solved once, and transitions are located with binary search. The recursion essentially becomes a top‑down dynamic programming solution where the state represents the best result starting from a particular wall or robot index.
Approach 3: Bottom-Up Dynamic Programming (O(n log n) Time, O(n) Space)
A bottom‑up DP variant processes walls from right to left. For each position, compute the maximum walls that can be destroyed if you start from that wall. Binary search finds the next valid index that a robot can reach, and the DP array stores previously computed optimal results. This removes recursion overhead and produces the same complexity as the memoized approach.
Recommended for interviews: The memoized search with sorting and binary search is the expected approach. It demonstrates control over state reduction, efficient lookups, and DP optimization. Explaining the brute force approach first shows understanding of the problem space, but the optimized DP solution proves you can scale it to large inputs.
We first store each robot with its range in an array and sort them by robot position. We also sort the wall positions. Next, we use depth-first search (DFS) to calculate the number of walls each robot can destroy, and use memoized search to avoid redundant calculations.
We design a function dfs(i, j), where i represents the index of the current robot being considered, and j represents the firing direction of the next robot (0 for left, 1 for right), and returns the number of walls that can be destroyed. The answer is dfs(n - 1, 1), where j can be 0 or 1 in the boundary state.
The execution logic of function dfs(i, j) is as follows:
If i \lt 0, it means all robots have been considered, return 0.
Otherwise, for the current robot, there are two firing directions to choose from.
If choosing to fire left, we need to calculate the left range [left, robot[i][0]], and use binary search to calculate the number of walls that can be destroyed in this range. In this case, a total of dfs(i - 1, 0) + count walls can be destroyed, where count is the number of walls destroyed when the current robot fires left.
If choosing to fire right, we need to calculate the right range [robot[i][0], right], and use binary search to calculate the number of walls that can be destroyed in this range. In this case, a total of dfs(i - 1, 1) + count walls can be destroyed, where count is the number of walls destroyed when the current robot fires right.
The return value of the function is the maximum number of walls that can be destroyed by the two firing directions.
Time complexity O(n times log n + m times log m), space complexity O(n). Where n and m are the numbers of robots and walls respectively.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Recursive Search | O(2^n) | O(n) | Conceptual baseline or very small inputs |
| Memoized Search + Binary Search | O(n log n) | O(n) | General optimal solution with overlapping subproblems |
| Bottom-Up Dynamic Programming | O(n log n) | O(n) | When you prefer iterative DP over recursion |
Leetcode 3661 | Maximum Walls Destroyed by Robots | Dynamic programming | weekly contest 464 • CodeWithMeGuys • 725 views views
Watch 4 more video solutions →Practice Maximum Walls Destroyed by Robots with our built-in code editor and test cases.
Practice on FleetCode