 # Number of Paths In a Matrix Problem

### Attend our Free Webinar on How to Nail Your Next Technical Interview

WEBINAR +LIVE Q&A

## How To Nail Your Next Tech Interview Hosted By
Ryan Valles
Founder, Interview Kickstart Our tried & tested strategy for cracking interviews How FAANG hiring process works The 4 areas you must prepare for How you can accelerate your learnings

Consider a maze mapped to a matrix with the upper left corner at coordinates (row, column) = (0, 0). You can only move towards the right or down from a cell. Determine the number of distinct paths through the maze. You must always start from the top-left position (0, 0) and end at the bottom-right (n-1, m-1)

For example, consider the following diagram where “1” indicates an open cell and “0” indicates a blocked cell. You can only travel through open cells, so no path can go through the cell (0, 2)

There are two possible paths from cell (0, 0) to cell (1, 3) in this matrix. Complete the function numberOfPaths, such that function returns the number of paths through the matrix, modulo (10^9 + 7).

Here are a couple of examples to get you started:

Example One

Input:

3

4

1 1 1 1

1 1 1 1

1 1 1 1

Output: 10

There are 10 possible paths from cell (0, 0) to cell (2, 3).

Example Two

Input:

2

2

1 1

0 1

Output: 1

There is one possible path from cell (0, 0) to cell (1, 1).

Notes:

Input Parameters: The function contains a single argument — a two-dimensional integer array called “matrix.”

Output: Return an integer — the number of possible paths from (0, 0) to (n-1, m-1).

Constraints:

• 1 <= n*m <= 2*10^6
• Each cell, matrix[i][j], contains 1, indicating it is accessible, or 0, indicating it is not accessible, where 0<=i<n and 0<=j<m

Solution 1: Brute Force (brute_force_solution.java)

We have a matrix with n rows and m columns, where each cell, matrix[A][B], denotes whether it is accessible or not.

We will use recursion to solve this problem.

We know that the number of ways to reach a cell is the sum of the number of ways to reach the cell to its left and the number of ways to reach the cell above it. Therefore:

No. of ways to reach matrix[i][j] =
No. of ways to reach matrix[i-1][j] + No. of ways to reach matrix[i][j-1]

This is because we can only go right or downward from any cell.

Now, we start from a cell and perform recursion to find the number of ways to reach cell (n-1, m-1):

recur(matrix, n-1, m-1) = recur(matrix, n-2, m-1) + recur(matrix, n-1, m-2)

For each cell, we will check if it is accessible or not. If it is not, we simply return 0, as there is no way to reach it. The base condition would be that if cell (0,0) is accessible, then the number of ways to reach it is 1.

Time Complexity:

O(2^(rows+columns))

In each recursion step, we will either reduce n by 1 or m by 1. Hence, the recurrence relation will be:

T(n + m) = T(n - 1 + m) + T(n + m - 1) + O(1)

T(n + m) = 2 * T(n - 1 + m) + O(1)

Therefore, it is O(2^(n+m)).

Auxiliary Space Used:

O(rows+columns)

We do not create any auxiliary array for the solution. We use recursion, which uses O(rows+columns) stack space as the maximum steps can be rows+columns at a time.

Space Complexity:

O(rows*columns)

Input takes O(rows*columns) space, the auxiliary space used is O(rows+columns), and the output takes O(1). Summing these up, we get O(rows*columns).

``````
// -------- START --------
public static int numberOfPaths(List> matrix){
int n = matrix.size(), m = matrix.get(0).size(), MOD = 1000000007;
int ans = recur(matrix, n-1, m-1, MOD);
return ans;
}

public static int recur(List> matrix, int n, int m, int MOD) {
int ans = 0;
//stopping condition
if(n<0 || m<0) {
return 0;
}
//if a cell is restricted, there are 0 ways to reach there.
if(matrix.get(n).get(m)==0) {
return 0;
}
//base condition: if cell (0,0) is accessible, we have 1 way to reach it.
if(n==0 && m==0) {
return 1;
}
/*number of ways to reach cell
a[i][j] = number of ways to reach cell a[i-1][j] + number of ways to reach cell a[i][j-1]*/
ans += (recur(matrix, n-1, m, MOD) + recur(matrix, n, m-1, MOD))%MOD;
return ans;
}
// -------- END --------
``````

Solution 2: Optimal Solution Using Dynamic Programming (optimal_solution.java)

We have a matrix with n rows and m columns, where each cell, matrix[A][B], denotes whether it is accessible or not.

Solution 1 (recursive) was exponential. We are visiting multiple states over and over, and then recursing for them, which we can surely avoid. To avoid revisiting states that have already been visited, we can store them in a dp array, so that they can be accessed as and when needed. This approach is known as Dynamic Programming.

Here’s how we do it:

1. We know that for any cell (i, j), the number of paths to reach it would be the number of paths to reach cell (i-1, j) + the number of paths to reach cell (i, j-1).
2. For any accessible cell matrix[i][j], we maintain the count of number of paths to reach this cell in a separate two-dimensional array dp[i][j], where dp[i][j] = dp[i-1][j] + dp[i][j-1], given that cell (i, j) is accessible.
3. We return the value of dp[i][j] as the answer.

Time Complexity:

O(n*m), considering the number of rows is n and columns is m.

We traverse the entire array matrix once and simultaneously traverse the dp array to keep the number of ways to reach that cell from cell (0,0). So, we travel both arrays at most once, and hence, the time complexity is O(n*m).

Auxiliary Space Used:

O(n*m), considering the number of rows is n and columns is m

We create a two-dimensional array dp of size n*m to store the number of paths from cell (0,0) to the current cell. Hence, the auxiliary space used is O(n*m).

Space Complexity:

O(n*m), considering the number of rows is n and columns is m

#### Input complexity is O(n*m), auxiliary space used is O(n*m), and output space complexity is O(1). Hence, total complexity will be O(n*m).

``````
// -------- START --------
public static int numberOfPaths(List> matrix){
int n = matrix.size(), m = matrix.get(0).size(), MOD = 1000000007;
if(matrix.get(0).get(0)== 0 || matrix.get(n-1).get(m-1)==0) {
return 0;
}
int[][] dp = new int[n][m];
//if cell (0,0) is accessible, number of ways to reach it is 1
dp = 1;
//filling for the cells in first row.
for(int i = 1; i < m ;i++){
if(matrix.get(0).get(i)==1 && dp[i-1] == 1){
dp[i] = 1;
}
}
//filling for the cells in the first column
for(int i = 1; i < n ;i++){
if(matrix.get(i).get(0)==1 && dp[i-1] == 1){
dp[i] = 1;
}
}
/*number of ways to reach
cell(i,j) = number of ways to reach cell(i-1,j) + number of ways to reach cell (i,j-1)*/
for(int i = 1; i < n; i++){
for(int j = 1; j``````

### `Attend our Free Webinar on How to Nail Your Next Technical Interview`

`WEBINAR +LIVE Q&A`

## `How To Nail Your Next Tech Interview`

` Hosted ByRyan VallesFounder, Interview Kickstart`
` Our tried & tested strategy for cracking interviews`
` How FAANG hiring process works`
` The 4 areas you must prepare for`
` How you can accelerate your learnings`
`Register for Webinar`

#### `Recommended Posts`

`Longest Common Prefix (LCP)`
`Design and Implement an LFU Cache`
`Maximum Depth of a Binary Tree`
`All Posts`
``` window.cookieconsent.initialise({palette:{popup:{background:"#3996d2",text:"#ffffff"},button:{background:"#00d1b4",text:"#ffffff"}},theme:"classic",content:{message:"We use cookies to enable the best possible experience on our site and to optimize the content for you. If you continue surfing you agree.",href:"https://www.interviewkickstart.com/privacy-policy"}}); function getAllUrlParams(url) { var queryString = url ? url.split('?') : window.location.search.slice(1); var utmobj = {}; if (queryString) { queryString = queryString.split('#'); var arr = queryString.split('&'); for (var i = 0; i < arr.length; i++) { var a = arr[i].split('='); var paramName = a; var paramValue = typeof (a) === 'undefined' ? true : a; paramName = paramName.toLowerCase(); if (paramName.match(/\[(\d+)?\]\$/)) { var key = paramName.replace(/\[(\d+)?\]/, ''); if (!utmobj[key]) utmobj[key] = []; if (paramName.match(/\[\d+\]\$/)) { var index = /\[(\d+)\]/.exec(paramName); utmobj[key][index] = paramValue; } else { utmobj[key].push(paramValue); } } else { if (!utmobj[paramName]) { utmobj[paramName] = paramValue; } else if (utmobj[paramName] && typeof utmobj[paramName] === 'string'){ utmobj[paramName] = [utmobj[paramName]]; utmobj[paramName].push(paramValue); } else { utmobj[paramName].push(paramValue); } } } } return utmobj; } function create_UUID() { function _p8(s) { var p = (Math.random().toString(16)+"000000000").substr(2,8); return s ? "-" + p.substr(0,4) + "-" + p.substr(4,4) : p ; } return _p8() + _p8(true) + _p8(true) + _p8(); } var visitor_id = getCookie("unique_visitor_id6"); var expdate = new Date(); expdate.setTime(expdate.getTime()+(365*24*60*60*1000)); if(visitor_id == ""){ setCookie("unique_visitor_id6",create_UUID()); visitor_id = getCookie("unique_visitor_id6"); } var referrer = document.referrer; var cta_lp = window.location.pathname; if((referrer != "") && (referrer.indexOf(window.location.host.toString()) == -1)){ setCookie("ik-landingpage",window.location.pathname); } var utm_params_url; let calendly_param = getAllUrlParams(); \$("#iksiteurl").val(iksite_url); if(calendly_param['invitee_first_name'] != undefined){ \$("#invitee_first_name").val(decodeURIComponent(calendly_param['invitee_first_name'])); \$("#invitee_last_name").val(decodeURIComponent(calendly_param['invitee_last_name'])); \$("#invitee_email").val(decodeURIComponent(calendly_param['invitee_email'])); \$("#answer_1").val(decodeURIComponent(calendly_param['answer_1'])); \$("#utm_source").val(decodeURIComponent(calendly_param['utm_source'])); \$("#utm_medium").val(decodeURIComponent(calendly_param['utm_medium'])); \$("#utm_campaign").val(decodeURIComponent(calendly_param['utm_campaign'])); \$("#salesforce_uuid").val(decodeURIComponent(calendly_param['salesforce_uuid'])); \$("#gclid").val(decodeURIComponent(calendly_param['gclid'])); \$("#msclkid").val(decodeURIComponent(calendly_param['msclkid'])); \$("#fbclid").val(decodeURIComponent(calendly_param['fbclid'])); \$("#event_start_time").val(decodeURIComponent(calendly_param['event_start_time'])); \$("#event_end_time").val(decodeURIComponent(calendly_param['event_end_time'])); \$("#user_id").val(visitor_id); \$("#user_country").val(v_country); \$("#client_timezone").val(v_timezone); utm_params_url = {}; } else{ utm_params_url = getAllUrlParams(); } if(utm_params_url['gh_jid'] != undefined){ utm_params_url = {}; \$('.careers-sec1, .careers-sec2, .careers-sec3, .careers-sec4,.section.hero-careers-sec, .career-section, .life-ik, .we-were-here-section, .ik-member, .ik-talks, .careers-imgages, .our-values, .careers-sec7, .who-we-are, .careers-sec6, .careers-sec5, .careers-sec4, .life-ik, .careers-sec3, .careers-sec2, .careers-sec1').hide(); } let isEmpty = jQuery.isEmptyObject(utm_params_url); let r_visit = read_cookie("v_latest"); if(isEmpty && (r_visit == null)){ bake_organic_cookie(); } else if(!isEmpty && (r_visit == null)){ bake_cookie("v_latest", utm_params_url); if(referrer == null || referrer.indexOf(window.location.host.toString()) == -1) bake_cookie_history("v_history", utm_params_url); } else if(isEmpty && (r_visit != null)){ if(r_visit['utm_source'] != "Organic") { bake_organic_cookie(); } } else{ if(!isDuplicateCookie(utm_params_url, r_visit)){ bake_cookie("v_latest", utm_params_url); if(referrer == null || referrer.indexOf(window.location.host.toString()) == -1) bake_cookie_history("v_history", utm_params_url); } } function isCookieSizeExceeded(){ let c_size = 15; var h_cookie = read_cookie("v_history"); if (h_cookie == null) return; if(h_cookie.length >= c_size){ h_cookie.shift(); bake_cookie("v_history", h_cookie); } } function isDuplicateCookie(utm_params, recent_visit){ if((utm_params['utm_source'] == recent_visit['utm_source']) && (utm_params['utm_medium'] == recent_visit['utm_medium']) && (utm_params['utm_campaign'] == recent_visit['utm_campaign']) && (utm_params['utm_adset'] == recent_visit['utm_adset']) && (utm_params['utm_content'] == recent_visit['utm_content']) && (utm_params['utm_term'] == recent_visit['utm_term']) && (utm_params['fbclid'] == recent_visit['fbclid'])) { return true; } else{return false;} } function bake_cookie_history(name, value) { isCookieSizeExceeded(); var visits_history = []; var iksutmhistory = read_cookie(name); if(iksutmhistory == "" || iksutmhistory == null){ var utmstring = value; utmstring.timestamp = \$.now(); visits_history.push(utmstring); var cookie = [name, '=', JSON.stringify(visits_history), ';expires','=', expdate.toGMTString(), '; domain=.', window.location.host.toString(), '; path=/;'].join(''); document.cookie = cookie; } else { var result = document.cookie.match(new RegExp(name + '=([^;]+)')); result && (result = JSON.parse(result)); var newhistoryobj = result.push(value); var cookie = [name, '=', JSON.stringify(result), ';expires','=', expdate.toGMTString(), '; domain=.', window.location.host.toString(), '; path=/;'].join(''); document.cookie = cookie; } } function bake_organic_cookie(){ var organicobj = { "utm_source":"Organic", "utm_medium":"", "utm_campaign":"", "utm_adset":"", "utm_content":"", "utm_term":"", "timestamp":\$.now()}; if(referrer == null || referrer.indexOf(window.location.host.toString()) == -1){ bake_cookie_history("v_history", organicobj); bake_cookie("v_latest", organicobj); } } function bake_cookie(name, value) { var utmstring = value; utmstring.timestamp = \$.now(); var cookie = [name, '=', JSON.stringify(utmstring), ';expires','=', expdate.toGMTString(),'; domain=.', window.location.host.toString(), '; path=/;'].join(''); document.cookie = cookie; } function read_cookie(name) { var result = document.cookie.match(new RegExp(name + '=([^;]+)')); result && (result = JSON.parse(result)); return result; } function setCookie(cname, cvalue) { var d = new Date(); d.setTime(d.getTime() + (365*24*60*60*1000)); var expires = "expires="+ d.toUTCString(); document.cookie = cname + "=" + cvalue + ";" + expires + ";path=/"; } function getCookie(cname) { var name = cname + "="; var ca = document.cookie.split(';'); for(var i = 0; i < ca.length; i++) { var c = ca[i]; while (c.charAt(0) == ' ') { c = c.substring(1); } if (c.indexOf(name) == 0) { return c.substring(name.length, c.length); } } return ""; } function showCalendly(){ var curl = generateCalendlyLink()+"&hide_event_type_details=1"; Calendly.initPopupWidget({ url: curl }); } \$('.request-info-close').click(function(e){ \$('.request-info-wrap').css("display","none"); \$('.request-info-wrap').css("opacity",0); }); \$('.form-to-calendly').click(function(e) { e.preventDefault(); var active_visit = read_cookie("v_latest"); var full_phone_number = int_phone.getNumber(intlTelInputUtils.numberFormat.E164); \$("input[name='phone_number[full]'").val(full_phone_number); var formstr = '&first_name=' + \$("#wcalendly-fname").val() + '&last_name=' + \$("#wcalendly-lname").val() + '&a1=' + full_phone_number + '&email=' + encodeURIComponent(\$("#wcalendly-email").val()) + '&salesforce_uuid=' + v_timezone; \$('#wc_utm_source').val(active_visit['utm_source']); \$('#wc_utm_medium').val(active_visit['utm_medium']); \$('#wc_utm_campaign').val(active_visit['utm_campaign']); \$('#wc_gclid').val(active_visit['gclid']); \$('#wc_msclkid').val(active_visit['msclkid']); \$('#wc_timezone').val(v_timezone); \$('#wc_page_url').val(window.location.pathname); \$('#wc_user_id').val(visitor_id); var name_regex = new RegExp("^[a-zA-Z ]+\$"); var email_regex = /^([a-zA-Z0-9_\.\-\+])+\@(([a-zA-Z0-9\-])+\.)+([a-zA-Z0-9]{2,4})+\$/; var phone_regex = /^(\+\d{1,2}\s?)?1?\-?\.?\s?\(?\d{3}\)?[\s.-]?\d{3}[\s.-]?\d{4}\$/gm; \$( "#wcalendly-fname" ).keypress(function() { \$('.fname-error').addClass('hide'); }); \$( "#wcalendly-lname" ).keypress(function() { \$('.lname-error').addClass('hide'); }); \$( "#wcalendly_pnumber" ).keypress(function() { \$('.mobile-error').addClass('hide'); }); \$( "#wcalendly-email" ).keypress(function() { \$('.email-error').addClass('hide'); }); \$( "#wcalendly-fname, #wcalendly-lname, #wcalendly-email, #wcalendly_pnumber" ).focus(function() { \$('.fname-error, .lname-error, .email-error, .mobile-error').addClass('hide'); }); if( (\$("#wcalendly-fname").val().length == 0) && (\$("#wcalendly-lname").val().length == 0) && (\$("#wcalendly-email").val().length == 0) && (\$("#wcalendly_pnumber").val().length == 0)){ \$('.fname-error, .lname-error, .email-error, .mobile-error').removeClass('hide'); } else if (!name_regex.test(\$("#wcalendly-fname").val()) || \$("#wcalendly-fname").val().length == 0){ \$('.fname-error').removeClass('hide'); }else if (!name_regex.test(\$("#wcalendly-lname").val()) || \$("#wcalendly-lname").val().length == 0){ \$('.lname-error').removeClass('hide'); }else if (!email_regex.test(\$("#wcalendly-email").val()) || \$("#wcalendly-email").val().length == 0){ \$('.email-error').removeClass('hide'); }else if(!phone_regex.test(\$("#wcalendly_pnumber").val()) || \$("#wcalendly_pnumber").val().length == 0){ \$('.mobile-error').removeClass('hide'); }else{ \$(".leadcapturing-form").submit(); calendlySignup(true,formstr); } }); function generateCalendlyLink(platform){ var calendlyurl; if(platform == "hubspot"){ calendlyurl = "https://meetings.hubspot.com/ik/requestacallback?embed=true&"; }else{ calendlyurl = "https://calendly.com/interviewkickstart/enrollment-workshop?"; } var active_visit = read_cookie("v_latest"); var visit_history = read_cookie("v_history"); var gaid = getCookie("_ga"); visitor_id = visitor_id + gaid; var utm_medium_str = "utm_medium="; for (const property in active_visit) { if (`\${property}` == "utm_medium") { utm_medium_str = utm_medium_str + `\${active_visit[property]}`; } } utm_medium_str = utm_medium_str + ":"; for (const property in active_visit) { if (`\${property}` == "gclid") { utm_medium_str = utm_medium_str + "gclid:" + `\${active_visit[property]}`; } else if (`\${property}` == "msclkid") { utm_medium_str = utm_medium_str + "msclkid:" + `\${active_visit[property]}`; } else if (`\${property}` == "fbclid") { utm_medium_str = utm_medium_str + "fbclid:" + `\${active_visit[property]}`; } } if ( (utm_medium_str.indexOf("gclid") == -1) && (utm_medium_str.indexOf("msclkid") == -1) && (utm_medium_str.indexOf("fbclid") == -1)){ utm_medium_str = utm_medium_str + ":"; } utm_medium_str = utm_medium_str + ":" + visitor_id; utm_medium_str = utm_medium_str + ":" + v_country; for (const property in active_visit) { var ptyn = `\${active_visit[property]}`; if( (`\${property}` != "utm_medium") && (`\${property}` != "msclkid") && (`\${property}` != "fbclid") && (`\${property}` != "gclid") ){ calendlyurl = calendlyurl+`\${property}`+"="+`\${active_visit[property]}`+"&"; } } utm_medium_str = utm_medium_str + "&salesforce_uuid="+v_timezone; //utm_medium_str = utm_medium_str + "&salesforce_uuid="+v_timezone +":"+cta_lp+":"+getCookie("ik_landingpage"); calendlyurl = calendlyurl + utm_medium_str; return calendlyurl; } function calendlySignup(isthisForm,formstr) { \$('.loading-overlay').css('display', 'flex'); let calendlyurl = generateCalendlyLink(); var visit_history = read_cookie("v_history"); if(isthisForm){ calendlyurl = calendlyurl + formstr; } let page_url = window.location.pathname; var jsonData = {"unique_visitor_id": visitor_id.toString().replace(/"/g, ""), "device_name": "", "page_url": page_url, "visitor_city": v_city, "click_history":JSON.stringify(visit_history)}; \$.ajax({ type: "POST", url: "https://hooks.zapier.com/hooks/catch/9555768/ong6g6o/", data: jsonData, success: function (e) { if(e.status == "success"){ bake_cookie("v_history",""); bake_cookie("v_latest",""); } setTimeout(function(){ location.href = calendlyurl; \$('.loading-overlay').css('display', 'none'); }, 100); } }); } \$( document ).ready(function() { \$('a').each(function() { var reg_exp = new RegExp('/' + window.location.host + '/'); if (!reg_exp.test(this.href)) { // External Link Found \$(this).attr('rel','nofollow'); } }); var active_visit_cookie = read_cookie("v_latest"); \$('.utm_source').val(active_visit_cookie['utm_source']); \$('.utm_medium').val(active_visit_cookie['utm_medium']); \$('.utm_campaign').val(active_visit_cookie['utm_campaign']); \$('.utm_term').val(active_visit_cookie['utm_term']); \$('.utm_content').val(active_visit_cookie['utm_content']); \$('.fbclid').val(active_visit_cookie['gclid']); \$('.gclid').val(active_visit_cookie['gclid']); \$('.msclkid').val(active_visit_cookie['msclkid']); \$('.timezone').val(v_timezone); \$('.page_url').val(window.location.href); \$('.user_id').val(visitor_id); \$('.hostname').val(window.location.hostname); \$('.user_country').val(v_country); }); ```