Choosing the right approach to solve a probability question in Data Structures and Algorithms (DSA) can be the difference between an efficient solution and a time-limit error. When we look at a matrix probability problem, we are essentially looking at a survival game. A point starts at a specific coordinate on a grid and moves in four or eight possible directions.
The challenge? Each move carries a risk of falling off the edge. This article breaks down the logic, the math, and the implementation of this classic matrix challenge.
Also Read – Advance Data Structure and Algorithms
What is a Matrix Probability Question?
In a typical probability-based question involving a matrix, you are given a grid of size M × N. You start at a specific cell (x, y). Your goal is to find the probability that you will remain inside the matrix boundaries after performing K steps.
At every step, you can move in four directions: North, South, East, and West. Since there are four possible directions, each move has a probability of 0.25 or 1/4. If a move takes you outside the grid, you are “gone” and can no longer return. The final answer is the sum of probabilities of being at any valid cell (i, j) after exactly K moves.
How To Solve a Probability Question?
To solve this question, we need to recognise that the state of the system depends on three variables: the current row, the current column, and the number of steps remaining.
- Base Case: If you are already outside the boundaries, the probability of staying inside is 0.
- Success Case: If you have completed K steps and are still inside, the probability for that specific path is 1.
- Recursive Step: From any cell (x, y), the probability of staying inside after N steps is the average of the probabilities of staying inside from its neighbours after N-1 steps.
Also Read – Introduction to Red-Black Tree
Recurrence Formula for Probability Question
To formalise the logic, we can express it as:
P(x,y,k)=14(P(x+1,y,k−1)+P(x−1,y,k−1)+P(x,y+1,k−1)+P(x,y−1,k−1))P(x, y, k) = \frac{1}{4} \Big( P(x+1, y, k-1) + P(x-1, y, k-1) + P(x, y+1, k-1) + P(x, y-1, k-1) \Big)P(x,y,k)=41(P(x+1,y,k−1)+P(x−1,y,k−1)+P(x,y+1,k−1)+P(x,y−1,k−1))
This equation ensures that each move contributes equally to the final probability.
Probability Calculation Table with Examples
This table illustrates how the probability shifts based on the number of directions available at any given step.
| Total Directions | Probability per Move | Formula for Next Step |
| 4 (N, S, E, W) | 0.25 | P(n) = \sum P(n-1) \times 0.25 |
| 8 (Include Diagonals) | 0.125 | P(n) = \sum P(n-1) \times 0.125 |
| Out of Bounds | 0.0 | Probability becomes 0 |
Recursive vs DP Approach for Probability Question
When you first encounter a question like this, recursion feels natural. You simply call a function for each direction. However, recursion leads to a massive amount of redundant work. For example, moving North then South brings you back to the same spot. A simple recursive tree would calculate the same cell multiple times for the same step count.
Why Dynamic Programming (DP) is Better:
- Memory of States: DP stores the result of each (x, y, steps) combination.
- Efficiency: It reduces the time complexity from exponential to polynomial (O(M \times N \times K)).
- Precision: By calculating bottom-up, we maintain better floating-point accuracy.
Top-Down DP for Probability Problems
Instead of recalculating the same states, we store results in a memo table.
- Use a 3D array: dp[x][y][steps]
- Before computing, check if already been calculated
- If yes → reuse stored value
- If no → compute and store
This reduces exponential recursion to O(M × N × K).
Also Read – Geometric Algorithms
Step by Step Guide to Solve Probability Problems
Solving probability questions and answers in competitive programming requires a structured method. Here is how you can implement the solution for a matrix probability problem.
1. Check for Boundaries
Before making any calculation, verify if the coordinates (x, y) are within 0 \leq x < M and 0 \leq y < N. If they aren’t, return 0.
2. Initialize the DP Table
Create a 3D array or a map where dp[x][y][steps] stores the probability. Alternatively, since each step only depends on the previous step, you can use two 2D matrices to save space.
3. Iterative Processing
For each step from 1 to K:
- Iterate through every cell in the matrix.
- For each cell, calculate the probability of reaching it from its neighbours.
- If a neighbour is out of bounds, that specific path contributes 0 to the “staying inside” probability.
4. Final Summation
After K steps, the value stored at your starting position (or the sum of all valid cells, depending on your DP direction) gives the final probability.
C++ Code for Probability-Based Question
#include <iostream>
#include <vector>
using namespace std;
double dp[50][50][50];
double probability(int x, int y, int m, int n, int k) {
if (x < 0 || y < 0 || x >= m || y >= n)
return 0.0;
if (k == 0)
return 1.0;
if (dp[x][y][k] != -1)
return dp[x][y][k];
double prob = 0.0;
prob += probability(x + 1, y, m, n, k – 1);
prob += probability(x – 1, y, m, n, k – 1);
prob += probability(x, y + 1, m, n, k – 1);
prob += probability(x, y – 1, m, n, k – 1);
return dp[x][y][k] = prob / 4.0;
}
int main() {
int m = 2, n = 2, x = 0, y = 0, k = 2;
for(int i=0;i<50;i++)
for(int j=0;j<50;j++)
for(int l=0;l<50;l++)
dp[i][j][l] = -1;
cout << probability(x, y, m, n, k);
return 0;
}
Probability Question Examples
Let’s take a look at a few examples to help you understand the topic better:
Example 1: 2 × 2 matrix, 1 step
Suppose the matrix is:
(0,0)(0,1)(1,0)(1,1)(0,0)(1,0)(0,1)(1,1)
Start at (0, 0) and take 1 move.
Possible moves:
- Up → out of bounds
- Left → out of bounds
- Down → (1, 0)
- Right → (0, 1)
Out of these 4 equally likely moves, 2 stay inside the matrix.
So, the probability of remaining inside after 1 move is:
Probability = 2/4 = 0.5
Example 2: 2 × 2 matrix, 2 steps
Now start again at (0, 0), but take 2 moves.
From (0, 0), only 2 valid first moves are possible:
- to (1, 0)
- to (0, 1)
Each of these first moves happens with probability 1/4.
Now check the second move:
From (1, 0):
- Up → (0, 0) inside
- Right → (1, 1) inside
- Down → out of bounds
- Left → out of bounds
So, probability of staying inside from (1, 0) for 1 more move = 2/4 = 0.5
From (0, 1):
- Down → (1, 1) inside
- Left → (0, 0) inside
- Up → out of bounds
- Right → out of bounds
So, probability of staying inside from (0, 1) for 1 more move = 2/4 = 0.5
Now combine both valid first moves:
Final probability = (1/4 × 0.5) + (1/4 × 0.5) = 0.25
So, the probability of staying inside the matrix after 2 moves is 0.25.
What this example shows
- boundary cells have a lower survival probability
- every move contributes only 1/4
- the answer is built from the probabilities of smaller subproblems
- this is exactly why recursion and DP work well for this question
Time and Space Complexity of the Probability Solution
For a matrix of size M × N and K steps:
- Time Complexity: O(M × N × K). We iterate through the whole grid for every step.
- Space Complexity: O(M × N × K) or O(M × N) if we only store the current and previous steps.
Common Mistakes in Probability Question
Many students fail this probability-based question because of minor logic errors. Here is what to watch out for:
- Integer Division: Ensure you use double or float for probabilities. If you divide ¼ as integers, you get 0.
- Off-by-One Errors: Remember that a matrix of size N usually has indices from 0 to N-1.
- Directional Consistency: Always ensure you account for all possible moves (usually 4 or 8) consistently.
FAQs
What is the main objective of a matrix probability-based question?
The goal is to determine the likelihood that a point remains within the defined boundaries of a grid after a specific number of random moves.
How do you handle out-of-bounds moves in these probability-based questions?
In most questions and answers of probability, an out-of-bounds move is treated as a "dead" state. The probability of returning from outside the grid is zero, effectively reducing the total survival probability.
Can I solve this using a simple BFS?
A Breadth-First Search (BFS) can track positions, but it is not ideal for calculating probabilities over many steps due to the overlapping paths. Dynamic programming is the standard approach for this probability-based question.
Does the starting position affect the final probability?
Absolutely. A starting position in the corner of a matrix has more immediate "out-of-bounds" neighbours than a cell in the centre, typically resulting in a lower survival probability after the first move.
What are some real-world probability-based question examples?
This logic is used in the "Random Walk" theory, which can model anything from gas molecule diffusion to the movement of a person in a confined space.