LeetCode Problem 3661

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Dynamic Programming, Sorting

Solution

LeetCode 3661 - Maximum Walls Destroyed by Robots

Problem Understanding

This problem takes place on a one dimensional number line. We are given positions of robots and positions of walls. Every robot owns exactly one bullet, and that bullet can be fired either to the left or to the right.

A robot located at position robots[i] can shoot at most distance[i] units away. If it shoots left, the bullet travels from robots[i] down to robots[i] - distance[i]. If it shoots right, the bullet travels from robots[i] up to robots[i] + distance[i].

Any wall located within the bullet's path is destroyed. However, there is an important restriction: robots act as obstacles. If a bullet encounters another robot before reaching its full distance, it immediately stops. The bullet cannot pass through robots.

The goal is to choose a shooting direction for every robot so that the total number of unique destroyed walls is maximized.

The word "unique" is important. If two robots could theoretically destroy the same wall, that wall only contributes one to the final answer.

The constraints are large:

• Up to 100,000 robots.
• Up to 100,000 walls.
• Positions can be as large as 10^9.

These constraints immediately rule out any solution that examines every robot-wall pair. An O(n * m) approach would require up to 10^10 operations, which is far too slow.

Several details make the problem tricky:

• Robots block bullets.
• A wall may exist at exactly the same position as a robot.
• Robots can shoot either left or right.
• Choices made for one robot affect what neighboring robots can safely destroy.
• We need the maximum possible count, which suggests an optimization problem rather than a simple simulation.

The problem guarantees that robot positions are unique and wall positions are unique. This simplifies range counting because we never need to deal with duplicate positions.

Approaches

Brute Force Approach

A natural first idea is to try every possible shooting direction assignment.

Each robot has two choices:

• Shoot left
• Shoot right

For n robots, this creates 2^n possible configurations.

For every configuration, we could:

1. Simulate every robot's bullet.
2. Determine its actual stopping range after accounting for blocking robots.
3. Collect all destroyed walls.
4. Count the number of unique destroyed walls.

This approach is correct because it explicitly checks every possible combination of decisions.

Unfortunately, it is completely impractical.

Even for only 30 robots, there would already be more than one billion configurations. The actual constraint allows up to 100,000 robots.

Key Observation

The important insight is that after sorting robots by position, interactions happen only between neighboring robots.

Consider robot i.

If it shoots left:

• Its bullet can never interfere with robots on the right.
• Its maximum reachable left boundary is limited by its own distance.
• Its bullet cannot pass through the previous robot.

If it shoots right:

• Its bullet is limited by the next robot.
• The exact stopping position depends on whether the next robot shoots left or right.

This dependency is local.

After sorting robots, the only information that matters when processing robot i is the behavior of robot i + 1.

That creates a very small state space suitable for dynamic programming.

We can define a DP state based on:

• Which robot we are processing.
• Whether the next robot shoots left or right.

Using binary search on the sorted wall positions allows us to count walls inside any interval in O(log m) time.

This reduces the problem from exponential complexity to nearly linear complexity.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n × (n + m))	O(m)	Tries every direction assignment
Optimal DP + Binary Search	O(n log m)	O(n)	Uses local dependencies and memoization

Algorithm Walkthrough

Step 1: Sort robots by position

Create pairs:

(position, distance)

and sort them by robot position.

Also sort the wall positions.

Sorting allows us to:

• Find neighboring robots efficiently.
• Count walls inside intervals using binary search.

Step 2: Define the DP state

Let:

dfs(i, nextDirection)

represent the maximum number of walls that can be destroyed using robots 0...i.

The parameter:

nextDirection

describes how robot i + 1 fires.

We need this information because robot i's rightward shot may be limited by robot i + 1.

Use:

0 = next robot shoots left
1 = next robot shoots right

Step 3: Base case

If:

i < 0

then there are no robots left to process.

Return:

0

Step 4: Compute the left-shooting option

If robot i shoots left:

leftBoundary = position - distance

However, it cannot shoot through the previous robot.

Therefore:

leftBoundary = max(
    position - distance,
    previousRobotPosition + 1
)

if a previous robot exists.

The destroyed walls lie in:

[leftBoundary, position]

Use binary search on the sorted wall array to count how many walls belong to this interval.

Then add:

dfs(i - 1, 0)

because robot i is now known to shoot left.

Step 5: Compute the right-shooting option

If robot i shoots right:

rightBoundary = position + distance

This boundary may be shortened by robot i + 1.

If robot i + 1 shoots right:

bullet stops before next robot

so:

rightBoundary =
    min(rightBoundary,
        nextRobotPosition - 1)

If robot i + 1 shoots left:

its bullet may already cover some territory to the left, so we further restrict:

rightBoundary =
    min(rightBoundary,
        nextRobotPosition - nextDistance - 1)

This prevents double-counting walls.

Count walls inside:

[position, rightBoundary]

using binary search.

Then add:

dfs(i - 1, 1)

because robot i is now shooting right.

Step 6: Take the better choice

For robot i:

answer =
max(
    leftOption,
    rightOption
)

Store it in memoization and return it.

Step 7: Start the recursion

The final answer is:

dfs(n - 1, 1)

The last robot has no robot to its right, so the value of the second parameter does not affect correctness.

Why it Works

After sorting robots, every robot only interacts with its immediate neighbors. A robot's leftward shot depends on the previous robot, while its rightward shot depends on the next robot.

The DP state captures exactly the information needed to resolve these interactions. Every state computes the best achievable answer for a prefix of robots, assuming a known behavior for the adjacent robot on the right.

Since every robot has only two possible directions and every state is solved once, the recursion explores all valid optimal configurations without redundant work. Therefore the algorithm always finds the maximum number of unique walls that can be destroyed.

Python Solution

from typing import List
from functools import cache
from bisect import bisect_left

class Solution:
    def maxWalls(self, robots: List[int], distance: List[int], walls: List[int]) -> int:
        robots_data = sorted(zip(robots, distance))
        walls.sort()

        n = len(robots_data)

        @cache
        def dfs(i: int, next_direction: int) -> int:
            if i < 0:
                return 0

            position, dist = robots_data[i]

            left_boundary = position - dist
            if i > 0:
                left_boundary = max(
                    left_boundary,
                    robots_data[i - 1][0] + 1
                )

            left_l = bisect_left(walls, left_boundary)
            left_r = bisect_left(walls, position + 1)

            shoot_left = dfs(i - 1, 0) + (left_r - left_l)

            right_boundary = position + dist

            if i + 1 < n:
                next_position, next_dist = robots_data[i + 1]

                if next_direction == 0:
                    right_boundary = min(
                        right_boundary,
                        next_position - next_dist - 1
                    )
                else:
                    right_boundary = min(
                        right_boundary,
                        next_position - 1
                    )

            right_l = bisect_left(walls, position)
            right_r = bisect_left(walls, right_boundary + 1)

            shoot_right = dfs(i - 1, 1) + (right_r - right_l)

            return max(shoot_left, shoot_right)

        return dfs(n - 1, 1)

The implementation begins by sorting robots according to position. This makes neighboring robot relationships easy to determine.

The walls array is also sorted. Since every robot destroys walls within a contiguous interval, binary search can count the number of walls in that interval efficiently.

The recursive function dfs(i, next_direction) implements the dynamic programming state. Memoization ensures each state is computed only once.

For each robot, the code evaluates both possible directions. It calculates the valid shooting interval, counts walls inside that interval using bisect_left, and combines the result with the best answer from previous robots.

Finally, the maximum of the left and right choices is stored and returned.

Go Solution

package main

import (
	"sort"
)

func maxWalls(robots []int, distance []int, walls []int) int {
	n := len(robots)

	type Pair struct {
		pos  int
		dist int
	}

	arr := make([]Pair, n)
	for i := 0; i < n; i++ {
		arr[i] = Pair{robots[i], distance[i]}
	}

	sort.Slice(arr, func(i, j int) bool {
		return arr[i].pos < arr[j].pos
	})

	sort.Ints(walls)

	memo := make([][2]int, n)
	seen := make([][2]bool, n)

	var dfs func(int, int) int

	dfs = func(i int, nextDirection int) int {
		if i < 0 {
			return 0
		}

		if seen[i][nextDirection] {
			return memo[i][nextDirection]
		}

		seen[i][nextDirection] = true

		position := arr[i].pos
		dist := arr[i].dist

		leftBoundary := position - dist
		if i > 0 {
			if arr[i-1].pos+1 > leftBoundary {
				leftBoundary = arr[i-1].pos + 1
			}
		}

		leftL := sort.SearchInts(walls, leftBoundary)
		leftR := sort.SearchInts(walls, position+1)

		shootLeft := dfs(i-1, 0) + (leftR - leftL)

		rightBoundary := position + dist

		if i+1 < n {
			nextPos := arr[i+1].pos
			nextDist := arr[i+1].dist

			if nextDirection == 0 {
				limit := nextPos - nextDist - 1
				if limit < rightBoundary {
					rightBoundary = limit
				}
			} else {
				limit := nextPos - 1
				if limit < rightBoundary {
					rightBoundary = limit
				}
			}
		}

		rightL := sort.SearchInts(walls, position)
		rightR := sort.SearchInts(walls, rightBoundary+1)

		shootRight := dfs(i-1, 1) + (rightR - rightL)

		if shootLeft > shootRight {
			memo[i][nextDirection] = shootLeft
		} else {
			memo[i][nextDirection] = shootRight
		}

		return memo[i][nextDirection]
	}

	return dfs(n-1, 1)
}

The Go version follows the same algorithm as the Python solution.

Instead of Python's @cache, Go uses explicit memoization arrays:

memo[i][direction]
seen[i][direction]

Binary search is implemented through:

sort.SearchInts

All arithmetic safely fits inside Go's int type because the largest coordinate value is only 10^9.

Worked Examples

Example 1

Input:

robots = [4]
distance = [3]
walls = [1, 10]

Sorted data:

robots_data = [(4, 3)]
walls = [1, 10]

For robot 0:

Choice	Interval	Walls Destroyed
Left	[1, 4]	{1}
Right	[4, 7]	{}

Results:

shoot_left = 1
shoot_right = 0

Answer:

1

Example 2

Input:

robots = [10, 2]
distance = [5, 1]
walls = [5, 2, 7]

Sorted robots:

[(2,1), (10,5)]

Sorted walls:

[2,5,7]

Robot at position 2:

Direction	Interval	Walls
Left	[1,2]	{2}
Right	[2,3]	{2}

Robot at position 10:

Direction	Interval	Walls
Left	[5,10]	{5,7}
Right	[10,15]	{}

Optimal combination:

Robot 2 -> Left
Robot 10 -> Left

Destroyed walls:

{2,5,7}

Answer:

3

Example 3

Input:

robots = [1,2]
distance = [100,1]
walls = [10]

Sorted robots:

[(1,100), (2,1)]

Robot at position 1 can theoretically reach wall 10.

However:

1 ---- 2 ---- 10

The robot at position 2 blocks all rightward shots.

Maximum right boundary:

2 - 1 = 1

Therefore wall 10 is unreachable.

Destroyed walls:

0

Answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log m)	Each DP state performs binary searches on walls
Space	O(n)	Memoization stores 2 states per robot

There are exactly 2 * n DP states because each robot can be evaluated with two possible values of nextDirection.

Each state performs a constant number of binary searches on the sorted wall array, costing O(log m) time.

Therefore the total complexity is:

O(n log m)

The memoization table stores two values per robot, giving:

O(n)

additional memory usage.

Test Cases

sol = Solution()

assert sol.maxWalls([4], [3], [1, 10]) == 1  # Example 1

assert sol.maxWalls(
    [10, 2],
    [5, 1],
    [5, 2, 7]
) == 3  # Example 2

assert sol.maxWalls(
    [1, 2],
    [100, 1],
    [10]
) == 0  # Example 3

assert sol.maxWalls(
    [5],
    [10],
    [5]
) == 1  # Wall shares robot position

assert sol.maxWalls(
    [1],
    [1],
    [100]
) == 0  # Wall out of range

assert sol.maxWalls(
    [1, 100],
    [50, 50],
    [10, 20, 80, 90]
) == 4  # Independent robots

assert sol.maxWalls(
    [1, 3],
    [100, 100],
    [50]
) == 0  # Blocking robot prevents access

assert sol.maxWalls(
    [10, 20, 30],
    [10, 10, 10],
    [5, 15, 25, 35]
) == 4  # Multiple separated intervals

assert sol.maxWalls(
    [1000000000],
    [100000],
    [999950000]
) == 1  # Large coordinates

assert sol.maxWalls(
    [2, 8],
    [10, 10],
    [2, 3, 4, 8]
) == 4  # Walls at robot positions

Test Summary

Test	Why
[4], [3], [1,10]	Basic single robot case
[10,2], [5,1], [5,2,7]	Multiple robots destroying disjoint walls
[1,2], [100,1], [10]	Robot blocking behavior
Wall at robot position	Validates special rule
Out-of-range wall	Ensures unreachable walls are ignored
Independent robots	Checks separated intervals
Strong blocking case	Verifies robot obstacle logic
Three robots	Tests larger interactions
Large coordinates	Verifies no coordinate-size issues
Walls at robot locations	Ensures inclusive intervals work correctly

Edge Cases

One important edge case occurs when a wall and a robot occupy the same position. It is easy to mistakenly exclude the robot position from the shooting interval and fail to count that wall. The implementation uses inclusive interval boundaries, so a wall located exactly at the robot's position is correctly counted.

Another important case is robot blocking. A naive solution may assume that a bullet always travels its full distance. That is incorrect because another robot can stop the bullet early. The algorithm explicitly limits shooting ranges using neighboring robot positions, ensuring bullets never pass through robots.

A third edge case occurs when a robot's distance is very large but another robot stands immediately next to it. Even though the distance would normally allow the bullet to reach far away walls, the neighboring robot may completely eliminate that possibility. The DP state captures the neighboring robot's behavior and adjusts the valid interval accordingly, preventing overcounting.

A final edge case involves extremely large coordinates, up to 10^9. Any solution based on building arrays indexed by position would be impossible. This implementation relies only on sorting and binary search over the existing positions, so coordinate magnitude has no impact on memory usage.