LeetCode 3661 | Maximum Walls Destroyed by Robots | Java | Hard | D P & Binary Search | CodeByTushu
Description: 🚀 Welcome Back to CodeByTushu!
In today’s video, we solve LeetCode 3661 — Maximum Walls Destroyed by Robots using Dynamic Programming and Binary Search in Java.
In this problem, we are given robots with fixed 1D coordinates and maximum bullet firing distances, alongside walls placed at distinct coordinates. Each robot can fire its single bullet either to the left or to the right up to its maximum distance. A bullet destroys every wall along its trajectory, but it is immediately blocked and stopped if it encounters another robot before reaching its destination. Our goal is to determine the optimal firing direction for each robot to maximize the total number of unique walls destroyed.
To solve this efficiently, we pair each robot with its distance and sort both robots and walls along the number line. Sorting allows us to determine the exact boundary truncation caused by adjacent robots, ensuring no bullet passes an obstacle. By maintaining two dynamic programming states for each robot—firing left or firing right—we use binary search on the sorted walls array to count walls within any interval in logarithmic time. When an adjacent robot fires right and the current robot fires left, we carefully calculate their overlapping union segment to prevent double-counting. This yields an optimal O((N + M) log M + N log N) time complexity with O(N) auxiliary space.
🔥 Problem Highlights
✅ Sorted coordinate representation for robots and walls to enable fast interval queries
✅ Boundary truncation where adjacent robots act as impenetrable obstacles
✅ Binary search lower_bound and upper_bound range counting in O(log M) time
✅ Overlap deduplication when robot i - 1 shoots right and robot i shoots left
✅ Clean two-state Dynamic Programming formulation with linear state transitions
✅ Optimal time complexity of O(N log N + M log M) and O(N) auxiliary space
⏱️ TIMESTAMPS
00:00 Introduction
00:50 CodeByTush & GitHub Information
01:12 Problem Understanding
01:48 Observation
02:32 Approach
03:15 Start Java Code
04:15 Run & Dry Run
04:34 All Cases
04:49 Time Complexity
05:06 Space Complexity
05:20 Final Summary
📂 Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/April/03-April/3661-Maximum-Walls-Destroyed-by-Robots
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/April/03-April/3661-Maximum-Walls-Destroyed-by-Robots/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/April/03-April/3661-Maximum-Walls-Destroyed-by-Robots/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/April/03-April/3661-Maximum-Walls-Destroyed-by-Robots/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/April/03-April/3661-Maximum-Walls-Destroyed-by-Robots/solution.js
🔗 LeetCode Source Code
📌 Admin type the link
🌐 All LeetCode Solutions
📌 https://codebytushu.com/Leetcode/
📱 Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
❤️ Donate
📌 https://codebytushu.com/Leetcode/donate.php
🔥 Perfect For
00:00 Intro & Daily Challenge Kickoff (Streak 98 Days)
01:30 Problem Understanding & Robot Obstacle Rules
03:32 Key Insights: Spatial Sorting & Overlap Reconciliation
05:21 Optimal Linear DP Recurrence & Binary Search
07:31 Clean Java Solution Walkthrough Line by Line
08:44 Test Cases Dry Run & Benchmark Verification (42 ms, Beats 98.4%)
11:25 Time Complexity Analysis (O(N log N + M log M) Time)
12:31 Space Complexity Analysis (O(N) Auxiliary Space)
13:25 Day 3 Wrap-up & Channel Resources
🌐 Follow CodeByTushu
▶️ YouTube: https://www.youtube.com/@codebytushu
📸 Instagram: https://instagram.com/codebytushu/
💼 LinkedIn: https://www.linkedin.com/company/codebytushu/
🌍 Website: https://codebytushu.com
🐙 GitHub: https://github.com/CodeByTushu
❤️ Don’t Forget To
👍 Like | 💬 Comment | 🔔 Subscribe
💬 Question of the Day
Why does a robot's bullet stop immediately when hitting another robot instead of penetrating through?
1️⃣ Robots absorb all bullets as fixed non-destructible obstacles
2️⃣ Bullets bounce back and reverse their direction
3️⃣ All subsequent walls are destroyed automatically
4️⃣ The bullet damages the robot and continues traveling
#LeetCode3661 #LeetCode #MaximumWallsDestroyedByRobots #Java #JavaDSA #DynamicProgramming #BinarySearch #Sorting #DSA #CodingInterview #ProblemSolving #LeetCodeHard #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description
In today’s video, we solve LeetCode 3661 — Maximum Walls Destroyed by Robots using Dynamic Programming and Binary Search in Java.
In this problem, we are given robots with fixed 1D coordinates and maximum bullet firing distances, alongside walls placed at distinct coordinates. Each robot can fire its single bullet either to the left or to the right up to its maximum distance. A bullet destroys every wall along its trajectory, but it is immediately blocked and stopped if it encounters another robot before reaching its destination. Our goal is to determine the optimal firing direction for each robot to maximize the total number of unique walls destroyed.
To solve this efficiently, we pair each robot with its distance and sort both robots and walls along the number line. Sorting allows us to determine the exact boundary truncation caused by adjacent robots, ensuring no bullet passes an obstacle. By maintaining two dynamic programming states for each robot—firing left or firing right—we use binary search on the sorted walls array to count walls within any interval in logarithmic time. When an adjacent robot fires right and the current robot fires left, we carefully calculate their overlapping union segment to prevent double-counting. This yields an optimal O((N + M) log M + N log N) time complexity with O(N) auxiliary space.
🔥 Problem Highlights
✅ Sorted coordinate representation for robots and walls to enable fast interval queries
✅ Boundary truncation where adjacent robots act as impenetrable obstacles
✅ Binary search lower_bound and upper_bound range counting in O(log M) time
✅ Overlap deduplication when robot i - 1 shoots right and robot i shoots left
✅ Clean two-state Dynamic Programming formulation with linear state transitions
✅ Optimal time complexity of O(N log N + M log M) and O(N) auxiliary space
⏱️ TIMESTAMPS
00:00 Introduction
00:50 CodeByTush & GitHub Information
01:12 Problem Understanding
01:48 Observation
02:32 Approach
03:15 Start Java Code
04:15 Run & Dry Run
04:34 All Cases
04:49 Time Complexity
05:06 Space Complexity
05:20 Final Summary
📂 Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/April/03-April/3661-Maximum-Walls-Destroyed-by-Robots
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/April/03-April/3661-Maximum-Walls-Destroyed-by-Robots/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/April/03-April/3661-Maximum-Walls-Destroyed-by-Robots/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/April/03-April/3661-Maximum-Walls-Destroyed-by-Robots/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/April/03-April/3661-Maximum-Walls-Destroyed-by-Robots/solution.js
🔗 LeetCode Source Code
📌 Admin type the link
🌐 All LeetCode Solutions
📌 https://codebytushu.com/Leetcode/
📱 Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
❤️ Donate
📌 https://codebytushu.com/Leetcode/donate.php
🔥 Perfect For
00:00 Intro & Daily Challenge Kickoff (Streak 98 Days)
01:30 Problem Understanding & Robot Obstacle Rules
03:32 Key Insights: Spatial Sorting & Overlap Reconciliation
05:21 Optimal Linear DP Recurrence & Binary Search
07:31 Clean Java Solution Walkthrough Line by Line
08:44 Test Cases Dry Run & Benchmark Verification (42 ms, Beats 98.4%)
11:25 Time Complexity Analysis (O(N log N + M log M) Time)
12:31 Space Complexity Analysis (O(N) Auxiliary Space)
13:25 Day 3 Wrap-up & Channel Resources
🌐 Follow CodeByTushu
▶️ YouTube: https://www.youtube.com/@codebytushu
📸 Instagram: https://instagram.com/codebytushu/
💼 LinkedIn: https://www.linkedin.com/company/codebytushu/
🌍 Website: https://codebytushu.com
🐙 GitHub: https://github.com/CodeByTushu
❤️ Don’t Forget To
👍 Like | 💬 Comment | 🔔 Subscribe
💬 Question of the Day
Why does a robot's bullet stop immediately when hitting another robot instead of penetrating through?
1️⃣ Robots absorb all bullets as fixed non-destructible obstacles
2️⃣ Bullets bounce back and reverse their direction
3️⃣ All subsequent walls are destroyed automatically
4️⃣ The bullet damages the robot and continues traveling
#LeetCode3661 #LeetCode #MaximumWallsDestroyedByRobots #Java #JavaDSA #DynamicProgramming #BinarySearch #Sorting #DSA #CodingInterview #ProblemSolving #LeetCodeHard #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description
