Corona infection in a gated community/society

Photo by Daniel Schludi on Unsplash

Given a 2D matrix, each cell is either an infected building 1 or a not infected 0 . Infected building can turn adjacent (up/down/left/right) building beings into infected every hour. Find out how many hours does it take to infect the entire society.

Example:

Input:
[0, 1, 1, 0, 1],
[0, 1, 0, 1, 0],
[0, 0, 0, 0, 1],
[0, 1, 0, 0, 0]
Output: 2
Explanation:
At the end of the 1st hour, the status of the society:
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
[0, 1, 0, 1, 1],
[1, 1, 1, 0, 1]
At the end of the 2nd hour, the status of the society:
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1]

Solution:

This is a typical task about graph problems. We should consider the society as a graph, where each building is a cell of the grid which connects by its edges to adjacent buildings.

Steps:

  1. Loop through entire society and add the already infected building position into Queue.
  2. We will keep a counter for already infected buildings , will use this counter to compare with the total available buildings in the society.

3. Find adjacent buildings around each dequeued infected building position.

4. Infect the adjacent buildings.

5. Add their position as well into the queue.

6. Increase the infected buildings counter.

7. Increase number of the hours.

8. Repeat from 2 until all buildings in the society infected.

9. At any time infected buildings count is equal total available buildings in the society will return the no of hours counter.

--

--

--

Full Stack Programmer, love to solve problem’s during free time.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

A comprehensive guide to downloading stock prices in Python

Feature Engineering Examples: Binning Numerical Features

Understanding the Mathematics behind Principal Component Analysis

Understanding Customer Churning using Spark for Big Data

Applied Behavior Analysis: Differences Between Response and Response Class

Charting a Course to Modernize Aeronautical Info

A collage of FAA aeronautical charts.

Helping the United Nations Infer Document Labels using Knowledge Graphs

Renko backtest: First higher low

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jaydeep

Jaydeep

Full Stack Programmer, love to solve problem’s during free time.

More from Medium

Time Based Key-Value Store

Leetcode Q210. Course Schedule II (Q202)

Leetcode 862. Shortest Subarray with Sum at Least K

Interview Preparation Series