Skip to main content
Talentd

Maximum Walls Destroyed by Robots - Solution & Explanation

HardArrayBinary SearchDynamic ProgrammingSorting16 min readAsked at: Amazon, Microsoft, Infosys
Practice this problem

Problem Statement

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 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:

  • A wall and a robot may share the same position; the wall can be destroyed by the robot at that position.
  • Robots are not destroyed by bullets.

 

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.
  • Thus, the answer is 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.
  • Thus, the answer is 3.
Example 3:

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 <= 105
  • 1 <= walls.length <= 105
  • 1 <= robots[i], walls[j] <= 109
  • 1 <= distance[i] <= 105
  • All values in robots are unique
  • All values in walls are unique

Approach Overview

Problem 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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Recursive SearchO(2^n)O(n)Conceptual baseline or very small inputs
Memoized Search + Binary SearchO(n log n)O(n)General optimal solution with overlapping subproblems
Bottom-Up Dynamic ProgrammingO(n log n)O(n)When you prefer iterative DP over recursion

Video Solution

Maximum Walls Destroyed by Robots | Detailed | Build Intuition | Leetcode 3661 | codestorywithMIK • codestorywithMIK • 9,244 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Walls Destroyed by Robots easy or hard?
Maximum Walls Destroyed by Robots is classified as a Hard problem. It requires combining sorting, binary search, and dynamic programming to avoid exponential exploration. Recognizing overlapping subproblems and designing the correct DP state is the main challenge.
Maximum Walls Destroyed by Robots Python/Java solution
The typical implementation uses a memoized search function that stores results for each index. Python uses dictionaries or lists for memoization, while Java often uses arrays or HashMaps. The logic remains the same: sort inputs, apply binary search for transitions, and store computed DP results.
How to solve Maximum Walls Destroyed by Robots in O(n log n)?
First sort the walls or robot capabilities so transitions become monotonic. Then use a memoized recursive DP where each state represents the maximum walls destroyed starting from an index. Binary search identifies the next valid index that can be reached. Memoization ensures each state is computed once, giving O(n log n) time.
What is the best approach for Maximum Walls Destroyed by Robots?
The most effective solution uses sorting, binary search, and memoized dynamic programming. After sorting the relevant values, a DP function computes the maximum walls that can be destroyed starting from each position. Binary search finds the next valid transition efficiently. This reduces the overall complexity to O(n log n) with O(n) extra space.
Is Maximum Walls Destroyed by Robots asked at Google/Amazon/Meta?
Problems combining dynamic programming with binary search and sorting frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that require choosing optimal transitions while maximizing a count are especially common in system design and algorithm rounds.
What data structure is used in Maximum Walls Destroyed by Robots?
The solution primarily uses arrays along with a memoization table for dynamic programming. Sorting organizes the input for efficient processing, and binary search is used to locate the next valid state quickly. Together these structures support the O(n log n) optimized solution.
What is the time complexity of Maximum Walls Destroyed by Robots?
The optimized solution runs in O(n log n) time. Sorting the input contributes the log factor, and each DP state is computed once. Binary search is used for transitions, keeping each lookup at O(log n). Space complexity is O(n) for the memoization table.

Ready to solve this problem?

Practice Maximum Walls Destroyed by Robots with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays