Solution 2 for Scaler Topics Fortnightly Contest - 6

This article is part of the Scaler Topics Fortnightly Contest - 6.

Solution Approach

• After sorting the monsters and energy drinks according to their x - coordinate.
• Use a 2 pointer technique to iterate over all the monsters and energy drinks between you and your friend.
• Maintain a max heap to store the energy drinks available to you so far.
• If you are not able to destroy the current monster try to drink the energy drinks available so far by popping from the heap.
• Whenever you take an energy drink increase ans by 1.
• If you are not able to destroy the monster even after consuming all the available drinks return -1.

Time Complexity: O(NlogN + MlogM) Space Complexity: O(M) where M is number of energy drinks and N is number of monsters

C++ Implementation

Java Implementation

Python Implementation