Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Count All Paths from Top left to bottom right in Two Dimensional Array including Diagonal Paths

Objec­tive: Count all the paths from left top cor­ner to right bot­tom cor­ner in two dimen­sional array.

Input: Two Dimen­sional array

Out­put: No of paths.

Approach :

1. Recur­sive

Recur­sive solu­tion to this prob­lem is sim­i­lar to Print All Paths from Top left to bot­tom right in Two Dimen­sional Array

But the Time com­plex­ity will be expo­nen­tial because there will be many sub prob­lems which will be solved again and again to get the final solu­tion. read this : “Dynamic pro­gram­ming vs Recursion

2. Dynamic Pro­gram­ming (Bet­ter Solu­tion)

Cre­ate two dimen­sional result­Count array to store the num­ber of paths from top left corner.

Base Case: To reach to any cell in either first row or col­umn from first cell(top left at 0,0) will be 1.

You can reach to any cell from 3 dif­fer­ent ways, from left, from top, from diag­o­nal. So total no of paths to reach to that cell will be sum of all the paths to reach to left, top and diag­o­nal cell. see picture

Count Paths

Count Paths

Exam­ple:

Count All Paths Example

Count All Paths Example

Com­plete Code:


Out­put:

No of Paths By Recursion: 13
No of paths By Dynamic Programming: 13

You may also like...

  • Steffi Keran Rani J

    what is arrA.length? and what is arrA[0].length?