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

Data Anonymization And GDPR

Dimensionality reduction with PCA: from basic ideas to full derivation.

Algorithms can leave anyone biased, including you

Computer with display of data — Photo by Markus Spiske on Unsplash

Performing Analysis of Meteorological Data

Sentiment Analysis for Stock Price Prediction in Python

Starbuck-s-Data-Analysis-Capstone-Project-

World Cities Ranked by Average Annual Sunshine Hours

Predicting Who’s going to Survive on Titanic Dataset

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

Cognizant Interview Experience

Longest Increasing Subsequence Coding Question

Validate Stack Sequences ( Daily Leetcode )

Engineering Journal: SDC