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

ProblemGiven the array A , m rows x n columns of 0 and 10 0 0 0 0 0 0 0 1 0 0 0 0 00 0 0 0 0 0 00 0 1 0 0 1 00 0 0 0 0 0 0For each step, all 1 elements will make 4 elements around them becomes 1Step 1 0 1 0 0 0 0 0 1 1 1 0 0 0 00 1 1 0 0 1 00 1 1 1 1 …


This content originally appeared on Level Up Coding - Medium and was authored by Leonard Yeo

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

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! ✌️

Solve How Many Steps is Required to Fill a 2 Dimensional Array was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.


This content originally appeared on Level Up Coding - Medium and was authored by Leonard Yeo


Print Share Comment Cite Upload Translate Updates
APA

Leonard Yeo | Sciencx (2021-10-03T12:16:36+00:00) Solve How Many Steps is Required to Fill a 2 Dimensional Array. Retrieved from https://www.scien.cx/2021/10/03/solve-how-many-steps-is-required-to-fill-a-2-dimensional-array/

MLA
" » Solve How Many Steps is Required to Fill a 2 Dimensional Array." Leonard Yeo | Sciencx - Sunday October 3, 2021, https://www.scien.cx/2021/10/03/solve-how-many-steps-is-required-to-fill-a-2-dimensional-array/
HARVARD
Leonard Yeo | Sciencx Sunday October 3, 2021 » Solve How Many Steps is Required to Fill a 2 Dimensional Array., viewed ,<https://www.scien.cx/2021/10/03/solve-how-many-steps-is-required-to-fill-a-2-dimensional-array/>
VANCOUVER
Leonard Yeo | Sciencx - » Solve How Many Steps is Required to Fill a 2 Dimensional Array. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2021/10/03/solve-how-many-steps-is-required-to-fill-a-2-dimensional-array/
CHICAGO
" » Solve How Many Steps is Required to Fill a 2 Dimensional Array." Leonard Yeo | Sciencx - Accessed . https://www.scien.cx/2021/10/03/solve-how-many-steps-is-required-to-fill-a-2-dimensional-array/
IEEE
" » Solve How Many Steps is Required to Fill a 2 Dimensional Array." Leonard Yeo | Sciencx [Online]. Available: https://www.scien.cx/2021/10/03/solve-how-many-steps-is-required-to-fill-a-2-dimensional-array/. [Accessed: ]
rf:citation
» Solve How Many Steps is Required to Fill a 2 Dimensional Array | Leonard Yeo | Sciencx | https://www.scien.cx/2021/10/03/solve-how-many-steps-is-required-to-fill-a-2-dimensional-array/ |

Please log in to upload a file.



There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.

Related Posts