Matrix probability problem

Approach

The approach is somewhat similar to Depth First Search (DFS Algorithm). Firstly, we will check the validity of the given vertex. If the matrix is invalid or has crossed the boundaries, the output straight away equals 0. If there is a surety that even after moving n steps, no boundaries would be crossed, that is, n is 0, then 1 will be the output.

We perform recursive traversing in each direction for each cell that comes in the way, w. As per the problem statement, each direction has an equal probability, so each direction will contribute ¼ of the total probability of that particular cell, that is, 0.25. The required probability is calculated with one less move so that necessary steps can be taken in case of an exception, such as stepping out of the matrix.

Algorithm

Prob(int i, int j, int x, int y, int n)

i,j = Order of Matrix

x,y = Coordinates of vertex

n = Shift in position

Start
   if x, y is not present inside matrix boundary i, j, return 0
   if n = 0 , return 1
   double prob = 0
   prob = prob + matProb(m, n, x-1, y, N-1) * 0.25
   prob = prob + matProb(m, n, x+1, y, N-1) * 0.25
   prob = prob + matProb(m, n, x, y+1, N-1) * 0.25
   prob = prob + matProb(m, n, x, y-1, N-1) * 0.25
   return prob
End

Implementation in Java

import java.io.*;
class Main
{
    public static void main (String[] args)
    {
        int i = 3, j = 4;
        int x = 2, y = 2;
        int n = 3;
        System.out.println(Prob(i, j, x, y, n));
    }
    static boolean Validity(int a, int b, int i, int j)
    {
        return (a >= 0 && a < i && b >= 0 && b < j);
    }
    static double Prob(int i, int j, int a, int b, int n)
    {
        if (! Validity(a, b, i, j))
            return 0.0;
        if (n == 0)
            return 1.0;
        double p = 0.0;
        p += Prob(i, j, a - 1, b, n - 1) * 0.25;
        p += Prob(i, j, a, b + 1, n - 1) * 0.25;
        p += Prob(i, j, a + 1, b, n - 1) * 0.25;
        p += Prob(i, j, a, b - 1, n - 1) * 0.25;
        return p;
    }
}

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
bool Validity(int a, int b, int x, int y)
{
    return (a >= 0 && a < x && b >= 0 && b < y);
}
double Prob(int x, int y, int a, int b, int n)
{
    if (!Validity(a, b, x, y))
        return 0.0;
    if (n == 0)
        return 1.0;
    double p = 0.0;
    p += Prob(x, y, a - 1, b, n - 1) * 0.25;
    p += Prob(x, y, a, b + 1, n - 1) * 0.25;
    p += Prob(x, y, a + 1, b, n - 1) * 0.25;
    p += Prob(x, y, a, b - 1, n - 1) * 0.25;
    return p;
}
int main()
{
    int x = 3, y = 4;
    int i = 2, j = 2;
    int n = 3;
    cout << Prob(x, y, i, j, n);
    return 0;
}

Input:

i=3, j=4, x=2, y=2, n=3

Output:

0.4375

Complexity Analysis

🌾 Time Complexity:

As you can see, no loops have been used, and the implementation seems simple. Hence we conclude that the time complexity for the code mentioned above will be: O(n).

🌾 Space Complexity:

Also, no extra space has been used in the solution above. Thus, the space complexity for the code mentioned above will be O(1).

Frequently Asked Questions

Which data structure is used to form a Matrix? Explain it.

A two-dimensional array is a data structure used to form a Matrix. Arrays within the arrays are called two-dimensional arrays, which are collections of rows and columns.

What is the need for a two-dimensional array?

Data that cannot be stored in a single-dimensional array, that is, the information that requires rows and columns to be stored, managed, and assessed in a one-dimensional array, are stored in two-dimensional arrays.

How are two-dimensional arrays stored in memory?

A two-dimensional array in the form of one row following another in the computer’s memory.

How can we obtain data from a two-dimensional array?

Like a one-dimensional array, we can obtain data from any individual cell of a two-dimensional array by using the indices of the cells. In two-dimensional arrays, two indices are attached to each cell. One index denotes row number, while the other denotes column number.

Conclusion

In a nutshell, we looked at the problem statement, had a look at every possible condition that could occur, understood the approach, went through the Algorithm, saw the implementations, tested the code against sample input, and did time and space complexities’ analysis.

We hope the above discussion helped you understand and solve the problem better, and now it is your turn to code the problem in your way.

For enthusiasts who want to solve more such questions, refer to the list below.

• Find the Good Matrix
• Ninja and the rows
• Set Matrix zeros
• Rotate Matrix clockwise

Enroll in our courses, go for mock tests, solve problems available, and interview puzzles. Also, you can focus on interview stuff- interview experiences and an interview bundle for placement preparations. Do upvote our blog to help other ninjas grow.

Happy Coding!