Solution 2 for Scaler Topics Fortnightly Contest - 6

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

Build an AI-First Career, Master the Complete Skillset

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

NSDC Certified

AI Forward Deployed Engineer Program

Full-stack engineering, production AI and client-facing consulting

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

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

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Python Implementation