Solve How Many Steps is Required to Fill a 2 Dimensional Array

Problem

Given the array A , m rows x n columns of 0 and 1

0 0 0 0 0 0 0 
0 1 0 0 0 0 0
0 0 0 0 0 0 0
0 0 1 0 0 1 0
0 0 0 0 0 0 0

For each step, all 1 elements will make 4 elements around them becomes 1

Step 1 
 
0 1 0 0 0 0 0 
1 1 1 0 0 0 0
0 1 1 0 0 1 0
0 1 1 1 1 1 1
0 0 1 0 0 1 0
 
 
Step 2 
 
1 1 1 0 0 0 0 
1 1 1 1 0 0 0
1 1 1 1 1 1 1
1 1 1 1 1 1 1
0 1 1 1 1 1 1
 
Step 3
 
1 1 1 1 0 0 0 
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
 
Step 4
 
1 1 1 1 1 1 1 
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1

Write a program to answer how many steps is required to fill A with all 1

• a) Solve the problem for m,n <= 100
• b) Tell us the idea how to solve this problem for m,n <= 1,000,000

Test cases

Test 1

Input
a = [ [1,0,0,0], 
      [0,0,0,0], 
      [0,0,0,0], 
      [0,0,0,1] ]
Output
3

Test 2

Input
a = [ [0,0,0,0,0,0,0],
      [0,1,0,0,0,0,0],
      [0,0,0,0,0,0,0],
      [0,0,1,0,0,1,0],
      [0,0,0,0,0,0,0] ]
Output
4

Solution in Python

Brute-force

Solve how many steps required to fill a 2d array in Python Bruteforce

Efficient

Solve how many steps required to fill a 2d array in Python Efficient

Solution in Golang

Efficient

Benchmark

Python Brute-force (size: 100)

real 0m0.046s
user 0m0.033s
sys 0m0.013s

Python Brute-force (size: 1000)

real 0m4.339s
user 0m3.557s
sys 0m0.776s

Python Brute-force (size: 10000)

Killed
real 3m36.693s
user 1m27.774s
sys 2m8.164s

Python Efficient (size: 100)

real 0m0.091s
user 0m0.030s
sys 0m0.026s

Python Efficient (size: 1000)

real 0m3.994s
user 0m3.806s
sys 0m0.168s

Python Efficient (size: 10000)

Killed
real 2m49.018s
user 2m33.503s
sys 0m7.575s

Golang Efficient (size: 100)

real 0m 0.00s
user 0m 0.00s
sys 0m 0.00s

Golang Efficient (size: 1000)

real 0m 0.10s
user 0m 0.08s
sys 0m 0.05s

Golang Efficient (size: 10000)

real 0m 7.69s
user 0m 8.04s
sys 0m 1.82s

Takeaways

I hope this blog post helps someone struggling to solve this problem. Stay Tuned for more posts! Peace! ✌️