Gang of Thieves Complete Solution

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

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

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)