Missing Test Case - 2126. Destroying Asteroids #19137
Description
Username
Problem number, title, and link
Category of the bug
- Problem description
- Solved examples
- Problem constraints
- Problem hints
- Incorrect or missing "Related Topics"
- Incorrect test Case (Output of test case is incorrect as per the problem statement)
- Missing test Case (Incorrect/Inefficient Code getting accepted because of missing test cases)
- Editorial
- Programming language support
Description of the bug
The following solution (the optimal approach) by Shivansu_7 works but it shouldn't. His/Hers approach is as follows:
class Solution:
def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
new_mass = mass
stack = []
for val in asteroids:
stack.append(val)
while stack and stack[-1] <= new_mass:
new_mass += stack.pop()
return not stackThis approach should fail but it doesn't, see the expected behavior section for an explanation.
Language used for code
Python
Code used for Submit/Run operation
https://leetcode.com/submissions/detail/1137574479/
class Solution:
def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
stack = []
for asteroid in asteroids:
stack.append(asteroid)
while stack and mass >= stack[-1]:
mass += stack.pop()
return not stackExpected behavior
The problem with the approach is that you only check the top item. The problem arises if there is an asteroid I can't beat initially which is followed by an asteroid even larger which I only can beat when first beating the asteroid before.
An example of this is:
asteroids: [2, 5, 1, 1]
mass: 1
Here we first need to beat the two 1's then the two, after which we have enough to beat the five. But the two is on the bottom of the stack where we never look, meaning we fail even though it could be solved.
Screenshot
The same code as in my submission
