Watch 5 video solutions for Maximum Walls Destroyed by Robots, a hard level problem involving Array, Binary Search, Dynamic Programming. This walkthrough by CodeWithMeGuys has 725 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |