Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Approach
2.1.
PseudoCode
3.
Implementation in C++
3.1.
Complexity Analysis
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

Path exists in the matrix with the addition of element is at most K.

Author Urwashi Priya
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

In this blog, we will discuss a backtracking problem that has been asked frequently in Interviews.

The problem is to check if a path exists in the matrix with the addition of element is at most K.

Before we proceed, we must know what backtracking is?

Backtracking is an algorithmic technique for solving the recursive problem by building every possible solution incrementally and removing those answers that fail to satisfy the problem’s constraints at any time.

Now let’s look at the problem.

Recommended topic about, kth largest element in an array, and Euclid GCD Algorithm

Problem Statement

We are given an M X N matrix, a coordinate, and a sum. We need to check for a path from the given coordinate to any boundary element of the matrix on the condition that the sum of the paths should not exceed the value K.

Sample Example

Say, for example, our matrix of order 3 X 4 is given below:

Given coordinate = (1,2)

Sum = 6

The answer will be Yes because we can reach boundary element 1 at (1,0) position by moving from 3 to 2 and then to 1.

Approach

Now to check if a path exists in the matrix with the addition of element is at most K, the following approach is followed.

Define a base case. Our base case will include the condition of whether our given coordinates are out of the matrix.

The sum given to us should be greater than the value at the coordinate given. If this exists then, follow the below steps.

Store the value of the coordinates given in a variable. 

Mark the current cell as visited.

Start visiting all its adjacent cells and return true.

If the path does not exist, mark the cell unvisited and return false.

This is the most optimised approach using backtracking. The total number of elements in the matrix is N*M. Each element has three directions to move. Therefore, time complexity will be O(3^(N * M)) and space complexity will be O(N*M)

Till now, I guess you must have got the basic idea of what has been asked in the problem statement. So, I strongly recommend you first give it a try. Coding Ninjas Studio

If you were not able to solve it, don’t be sad.

Please have a look at the algorithm, and then again, you must give it a try.

PseudoCode

Algorithm

To check if a path exists in the matrix with the addition of element is at most K:

___________________________________________________________________

procedure findWay(vector<vector<int> >& board, int X, int Y, int M, int N, int K):

___________________________________________________________________

1.  If X < 0 || X == M || Y < 0 || Y == N:

        return true

2. if validity(board, X, Y, K):

        board_XY = board[X][Y]

        board[X][Y] = INT_MAX

3.     if findWay(board, X + 1, Y, M, N, K - board_XY) or findWay(board, X - 1, Y, M, N, K - board_XY) or findWay(board, X, Y + 1, M, N, K - board_XY) or findWay(board, X, Y - 1, M, N, K - board_XY)): return true

4.     board[X][Y] = board_XY;

5.  Return false

6. end procedure

___________________________________________________________________

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Implementation in C++

// C++ program to  Check if a path exists in the matrix with the addition of element is at most K.
#include <bits/stdc++.h>
using namespace std;

// Function to check validity on moving to the next index
bool validity(vector<vector<int>> &board, int i, int j, int K)
{
    if (board[i][j] <= K)
    {
        return true;
    }
    // else
    return false;
}

// Checking if a path exists from the given cell having coordinate (X, Y) of the matrix to any boundary cell with the sum of elements at most K.
bool findWay(vector<vector<int>> &board, int X, int Y, int M, int N, int K)
{
    if (X < 0 || X == M || Y < 0 || Y == N)
    {
        return true;
    }

    if (validity(board, X, Y, K))
    {
        // Storing the current element in a variable
        int board_XY = board[X][Y];

        // Marking the current(present) cell as visited
        board[X][Y] = INT_MAX;

        // Visiting all the adjacent cells and returning true
        if (findWay(board, X + 1, Y, M, N, K - board_XY) || findWay(board, X - 1, Y, M, N, K - board_XY) || findWay(board, X, Y + 1, M, N, K - board_XY) || findWay(board, X, Y - 1, M, N, K - board_XY))
        {
            return true;
        }

        // Marking the cell unvisited if above case does not hold.
        board[X][Y] = board_XY;
    }

    return false;
}

int main()
{
    vector<vector<int>> grid = {
        {2, 3, 4, 5},
        {1, 2, 3, 4},
        {1, 4, 5, 7}};

    int K;
    cin >> K;
    int M = grid.size();
    int N = grid[0].size();
    int X, Y;
    cin >> X >> Y;

    if (findWay(grid, X, Y, M, N, K))
        cout << "Yes";
    else
        cout << "No";

    return 0;
}

 

Output:

Sample Input: 
6
1  2
Sample Output:
Yes

 

Complexity Analysis

Time Complexity: O(3^(N * M)).

Analysing Time Complexity:

The total number of elements in the matrix = N*M.

Each element has three directions to move.

Space complexityO(N*M).

FAQs

  1. What are boundary elements?
    Elements present in the leftmost, rightmost, topmost or bottommost side are boundary elements.
     
  2. What are the different types of backtracking problems? 
    There are 3 different types of backtracking problems:
    (i) Decision problem-These problems demands for a feasible solution.
    (ii) Optimization problem-These problems demands for the best possible solution.
    (iii) Enumeration problem-These problems demands for all possible feasible solution.
     
  3. Is backtracking the same as recursion?
    Recursion keeps on calling function till a base case is reached whereas backtracking uses a recursive approach to explore and exhaust all the possible results till we get the best result possible for the problem.

Key Takeaways

This article taught us to check if a path exists in the matrix with the addition of element is at most K by approaching the problem using the backtracking method. We discussed its implementation using illustrations, pseudocode and then optimised proper code.

We hope you could take away all critical techniques like analysing problems by walking over the execution of the examples and finding out the recursive pattern followed in most backtracking problems.

Check out this problem - Root To Leaf Path

Now, we recommend you practice problem sets based on backtracking to master your fundamentals. You can get a wide range of questions similar to this problem on CodeStudio

Previous article
Least count of words required to construct a target String
Next article
Generate all possible combinations of K numbers that sum to N
Live masterclass