Problem Statement in English

You’re given three 0-indexed integer arrays robots, distance, and walls of length n. The i-th robot is initially at position robots[i] and can destroy walls in either direction within the range [robots[i] - distance[i], robots[i] + distance[i]].

If a robot destroys a wall, it can continue to destroy other walls in the same direction until it reaches the end of its range or encounters another robot. If a robot encounters another robot, it cannot destroy any more walls in that direction.

Return the maximum number of walls that can be destroyed by the robots.

Approach

There are a couple things we need to calculate:

  • left[i]: The number of walls that the i-th robot can destroy to its left.
  • right[i]: The number of walls that the i-th robot can destroy to its right.
  • num[i]: The number of walls between the i-th robot and the (i-1)-th robot.

To calculate these, we can sort the robots and walls arrays. But since we then lose the range of each robot we need to first save that.

Then, we can use binary search to find the positions of the walls that are within the range of each robot.

To find left[i], we can find the position of the rightmost wall that is less than or equal to robots[i] and the position of the leftmost wall that is greater than or equal to robots[i] - distance[i]. The number of walls that the i-th robot can destroy to its left is the difference between these two positions.

To find right[i], we can find the position of the leftmost wall that is greater than or equal to robots[i] and the position of the rightmost wall that is less than or equal to robots[i] + distance[i]. The number of walls that the i-th robot can destroy to its right is the difference between these two positions.

To find num[i], we can find the position of the rightmost wall that is less than or equal to robots[i] and the position of the leftmost wall that is greater than or equal to robots[i - 1]. The number of walls between the i-th robot and the (i-1)-th robot is the difference between these two positions.

Now for the final part, we can use dynamic programming to find the maximum number of walls that can be destroyed by the robots. For each robot, we have 2 options:

  • Fire to the left
  • Fire to the right

But our answer until the robot will depend on the previous robot’s answer. So we can maintain two variables sub_left and sub_right to keep track of the maximum number of walls that can be destroyed to the left and right of the current robot, respectively.

We can maintain two variables sub_left (max walls destroyed if the previous robot fired to the left) and sub_right (max walls destroyed if the previous robot fired to the right) to keep track of the maximum number of walls that can be destroyed to the left and right of the current robot, respectively.

If the previous robot fired to the left, then:

  • The current robot fires to the left and destroys left[i] walls, the total would be sub_left + left[i], and there’s no overlap with the previous robot
  • The current robot fires to the right and destroys right[i] walls, the total would be sub_left + right[i], and there’s no overlap with the previous robot

If the previous robot fired to the right, then:

  • The current robot can fire to the left and destroy left[i] walls, but there would be an overlap of right[i - 1] walls with the previous robot, so the total would be sub_right - right[i - 1] added with the minimum of left[i] + right[i - 1] and num[i] (since we can’t destroy more walls than the number of walls between the two robots)
  • The current robot can fire to the right and destroy right[i] walls, the total would be sub_right + right[i], and there’s no overlap with the previous robot

As we iterate through the robots, we can update sub_left and sub_right with the maximum values calculated above. Finally, we can return the maximum of sub_left and sub_right as the answer.

And we’re done!

Solution in Python


class Solution:
    def maxWalls(
        self, robots: List[int], distance: List[int], walls: List[int]
    ) -> int:
        n = len(robots)
        left = [0] * n
        right = [0] * n
        num = [0] * n
        robots_to_distance = {}

        for i in range(n):
            robots_to_distance[robots[i]] = distance[i]

        robots.sort()
        walls.sort()

        for i in range(n):
            pos1 = bisect_right(walls, robots[i])

            if i >= 1:
                left_bound = max(
                    robots[i] - robots_to_distance[robots[i]], robots[i - 1] + 1
                )
                left_pos = bisect_left(walls, left_bound)
            else:
                left_pos = bisect_left(
                    walls, robots[i] - robots_to_distance[robots[i]]
                )

            left[i] = pos1 - left_pos

            if i < n - 1:
                right_bound = min(
                    robots[i] + robots_to_distance[robots[i]], robots[i + 1] - 1
                )
                right_pos = bisect_right(walls, right_bound)
            else:
                right_pos = bisect_right(
                    walls, robots[i] + robots_to_distance[robots[i]]
                )

            pos2 = bisect_left(walls, robots[i])
            right[i] = right_pos - pos2

            if i == 0:
                continue

            pos3 = bisect_left(walls, robots[i - 1])
            num[i] = pos1 - pos3

        sub_left, sub_right = left[0], right[0]
        for i in range(1, n):
            current_left = max(
                sub_left + left[i],
                sub_right - right[i - 1] + min(left[i] + right[i - 1], num[i]),
            )
            current_right = max(sub_left + right[i], sub_right + right[i])
            sub_left, sub_right = current_left, current_right

        return max(sub_left, sub_right)

Complexity

  • Time: $O(n \log n)$
    Since we sort the arrays and use binary search to find the positions of the walls.

  • Space: $O(n)$
    Since we use additional arrays to store the number of walls that can be destroyed to the left and right of each robot, and the number of walls between each pair of robots.

Mistakes I Made

I had to look this one up :(

And we are done.