Gang of Thieves Complete Solution

This article is part of the Scaler Topics Fortnightly Contest - 21

Transform Your Career

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

Solution Approach

• Initialize the necessary variables and data structures, including an array h to store the height of each node/district in the graph denoting the layout of the given city, a boolean array prob to track the probability of each district being included in the final result, and a boolean array is to mark the districts specified in the input vector C as affected districts.
• Prepare the graph by populating the adjacency list adj with the edges provided in the input vector A.
• Define a recursive function dfs to perform a depth-first search on the graph/city starting from a given district u and updating the height h of each visited district.
• Additionally, update the probability prob of each district/node based on its height and the value of B provided as input. Keep track of the deepest affected district R and its height D during the traversal.
• Initialize R and D with the first affected district from the input vector C.
• Call the dfs function three times starting from the deepest affected district R to update the values of R and D with the deepest affected district in the graph.
• Count the number of districts that have true value in the prob array, indicating that they are within the allowed height limit B.
• Return the count of such districts as the final result of the algorithm.

Time Complexity: O(N) Space Complexity: O(N)

C++ Implementation

Java Implementation

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Python Implementation