LeetCode #749: Contain Virus, Wall the Most Dangerous Region First

Brute to Best: every LeetCode problem, from the naive solution to the optimal one. In this video: The problem: infected cells spread to their neighbours every night. Each day, you can put walls around one region. Return the total number of walls used. Brute force: wall regions in any order. Picking the wrong region lets the virus spread further and uses more walls. The key insight: the rules require walling the region that threatens the most uninfected cells each day, so the problem is a simulation done carefully. Each day, run a BFS or DFS on every region to find the cells it threatens and how many walls it needs. Wall the region that threatens the most cells and mark it as contained. Every other region spreads by one step. Dry run: on the 4 × 8 grid, the left region threatens 6 cells and takes 5 walls, then the right region takes 5, so the answer is 10. Complexity: O(R·C·D) time over D days and O(R·C) space. Problem: https://leetcode.com/problems/contain... Related: Number of Islands (200), Rotting Oranges (994), Surrounded Regions (130) Full Brute to Best playlist on the channel. Subscribe for a new LeetCode problem, solved from brute force to the best solution, every day. Hashtags #leetcode #leetcode749 #containvirus #simulation #bfs #dfs #matrix #grid #hard #coding #codinginterview #dsa #python #google #brutetobest