Can be solved without using DP in an iterative way


#1

Hi, instead of using DP and additional recursive stack memory we can use normal matrix traversal logic in 4 directions.

Horizontal
Vertical
Left_Diagonal
Right_Diaogonal

each of the above dimensions require 2 traversals at max as a future/ahead 1 may lead to increment for a previous 1/0…so at most we traverse an element twice.
So each dimension takes (m* n)*2.

Therefore 4 dimension traversal takes 4( (m * n) * 2) ===8 *(m * n).

Happy Coding!
:slight_smile:


#2

Can you please share your code?


#3

But this is a really cumbersome way.