Solution in java for : Finding if a path exists from start to end cell in a maze | Back Tracking and Dynamic Programming

Hello Friends,

Today I am here with you with a recursion problem. Today we have a little tough problem.

Suppose we have a maze and we need to determine if a path exits from starting point  to the last point in the maze. Maze is represented by a 2-d-matrix. Lets call this matrix 'maze'. maze[0][0] represents the starting point and maze[rows-1][columns-1] be the end point. Any cell 'maze[i][j]' can be used as a part of the path if it contains 1 and can be reached from immediate top, left, right or bottom cells. Cells containing 0 are the ones which can not be used in the path.

Friends I have tried solving this using two Approaches.
    1. Recursion [Back Tracking] : Depth search First approach : DFS
    2. Dynamic Programming.

**Note that Dynamic programming approach will fail for few examples where path exists by traversing upwards or left side like below example

1 1 1 1 0 0 0 0
0 0 0 1 0 1 1 1
0 1 1 1 0 1 0 1
0 1 0 0 0 1 0 1
0 1 1 1 1 1 0 1


Friends please find below the code for this problem.

package com.recursion.backtracking;

public class Maze {
    public static void main(String[] args) {
        int mazeForDFS[][] = { 
                { 1, 1, 1, 1, 1, 0, 0 }, 
                { 0, 0, 1, 1, 1, 0, 0 }, 
                { 0, 0, 1, 0, 0, 0, 0 },
                { 0, 0, 1, 0, 0, 0, 0 }, 
                { 0, 0, 1, 0, 0, 0, 0 }, 
                { 0, 0, 1, 1, 1, 1, 0 }, 
                { 0, 0, 1, 1, 0, 1, 0 },
                { 1, 1, 0, 0, 0, 1, 1 } 
                
        };
        
        int mazeForDP[][] = { 
                { 1, 1, 1, 1, 1, 0, 0 }, 
                { 0, 0, 1, 1, 1, 0, 0 }, 
                { 0, 0, 1, 0, 0, 0, 0 },
                { 0, 0, 1, 0, 0, 0, 0 }, 
                { 0, 0, 1, 0, 0, 0, 0 }, 
                { 0, 0, 1, 1, 1, 1, 0 }, 
                { 0, 0, 1, 1, 0, 1, 0 },
                { 1, 1, 0, 0, 0, 1, 1 } 
                
        };
        
        boolean isPathAvailableDFS = isPathAvailable(mazeForDFS, 0, 0, mazeForDFS.length, mazeForDFS[0].length);
        boolean isPathAvailableDP = isPathAvailable(mazeForDP);
        System.out.println("DFS way : " + isPathAvailableDFS);
        System.out.println("DP  way : " + isPathAvailableDP);
    }

    public static final int VISITED = 0;

    /**
     * This is a recursive approach based upon recursion and Back tracking. If a
     * end point is reached then true is returned all the way up to the first
     * calling of the method, else false is returned. False is propagated  down
     * the call stack if all the options [top, left, right, down] are explored
     * and no other cell is left to explore.
     * 
     * @param maze
     * @param i
     * @param j
     * @param rows
     * @param columns
     * @return true if path exists else returns false;
     */
    public static boolean isPathAvailable(int[][] maze, int i, int j, int rows, int columns) {
        if (i == rows - 1 && j == columns - 1) {
            return true;
        }
        maze[i][j] = VISITED;
        if (j + 1 < columns && maze[i][j + 1] != VISITED) {
            if (isPathAvailable(maze, i, j + 1, rows, columns)) {
                return true;
            }
        }
        if (i + 1 < rows && maze[i + 1][j] != VISITED) {
            if (isPathAvailable(maze, i + 1, j, rows, columns)) {
                return true;
            }
        }
        if (j - 1 >= 0 && maze[i][j - 1] != VISITED) {
            if (isPathAvailable(maze, i, j - 1, rows, columns)) {
                return true;
            }
        }
        if (i - 1 >= 0 && maze[i - 1][j] != VISITED) {
            if (isPathAvailable(maze, i - 1, j, rows, columns)) {
                return true;
            }
        }
        return false;
    }

    /**
     * This method uses Dynamic programming to solve the problem. It exploits
     * the information for all the first row and column information and then
     * verifies the rest of the cells if they are reachable. In case they are
     * not reachable this method marks them as 0, as they are as good as cells
     * with value = 0;
     * 
     */
    public static boolean isPathAvailable(int[][] maze) {
        int rows = maze.length;
        int coloumns = maze[0].length;
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < coloumns; j++) {
                if (maze[i][j] == 1 && maze[i - 1][j] == 0 && maze[i][j - 1] == 0) {
                    maze[i][j] = 0;
                }
            }
        }
        return maze[rows - 1][coloumns - 1] == 1;
    }
}

Compute 'x' raised to power 'n' in O(logN) time using Java

Hello friends,

In  continuation to the recursive algorithms, I am here with you with another problem.

Suppose we have a number 'x' a another positive Integer 'n'. We need to find the value of 'x' raised to power to 'n'.

Friends please find below the code in java for this.

package com.recursion.power;

import java.util.Scanner;

/**
*
* @author krishna.k
*
*         This class computes the value of 'x' raised to power of 'n' in time
*         complexity of O(log n). 'x' is Integer, and n is a positive Integer
*         including 0.
*
*
*
*
*/
public class PowerComputation {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the value of x (base)");
        int x = sc.nextInt();
        System.out.println("Enter a positve integer n (power)");
        int n = sc.nextInt();
        System.out.println("Value of " + x + " raised to power " + n + " is " + computePower(x, n));
    }

    public static int computePower(int x, int n) {
        if (x == 0 || x == 1 || n == 1) {
            return x;
        }
        if (n == 0) {
            return 1;
        }
        int temp = computePower(x, n / 2);
        if (n % 2 == 0) {
            return temp * temp;
        } else {
            return x * temp * temp;
        }
    }
}

Print the elements of the array in straight order and in reverse order using Recursion in Java

Hello friends,

I am here with another question in continuation to our simple recursive algorithm based questions.

If we have an array of numbers, we need to print the elements of the array in straight order and in reverse order. 

We can easily do this using iteration but for learning purpose lets try doing this using recursion.

Note that to print the elements in the reverse order I have used two methods, one uses simple index based manipulation but lets observe the other method : printReverseInterestingWay(). While other method prints the elements as it visits the element first time but this method prints the element during re-visit (following the recurrence method calls in stack)

Friends Please find the code below.

package com.recursion.printarray;

public class StraightReversePrintArray {
    public static void main(String[] args) {
        int[] input = { 1, 2, 3, 4, 6, 8 };
        int size = input.length;
        System.out.println("Straight printing of the Array: ");
        printStraight(input, size, 0);
        System.out.println("Reverse printing of the Array: ");
        printReverse(input, size, 0);
        System.out.println("Reverse printing of the Array using interesting way: ");
        printReverseInterestingWay(input, size, 0);
    }

    public static void printStraight(int[] input, int size, int i) {
        if(i < size){
            System.out.println(input[i]);
            printStraight(input, size, i+1);
        }
    }

    public static void printReverse(int[] input, int size, int i) {
        if(i < size){
            System.out.println(input[size-i-1]);
            printReverse(input, size, i+1);
        }
    }
    
    public static void printReverseInterestingWay(int[] input, int size, int i){
        if(i < size){
            printReverseInterestingWay(input, size, i+1);
            System.out.println(input[i]);
        }
    }
}

Sum of first N natural numbers by recursion in Java

Dear Friends,

I am here with you with another simple problem.

If we have a natural number, N then we need to find the sum of first N natural numbers.

This has a simple solution which can be simply printing the value of N*(N+1)/2. For learning purpose lets try this problem using recursion. Friends please find below the code using recursion.

package com.recursion.sum.numbers;

import java.util.Scanner;

/**
 * This can be solved using simple formula for sum of first n natural numbers
 * but for learning purpose we are solving it using Recursion
 * 
 * @author krishna.k
 *
 */
public class SumOfFirstNNumbers {
    public static void main(String[] args) {
        System.out.println("Enter the Number");
        Scanner sc = new Scanner(System.in);
        int number = sc.nextInt();
        System.out.println("Sum of first "+ number+" numbers is "+computeSum(number));
    }

    public static int computeSum(int number) {
        if(number == 1){
            return 1;
        }
        return number + computeSum(number-1);
    }
}

Sum of digits of a number N using recursion in Java

Hello friends,

I am here with you with an easy problem.

Given a number N , we need to output the sum of the digits of the number N.

This can be solved using iteration but for learning purpose lets do it using recursion.

Friends, please find the code below for this problem.

package com.recursion.sumofdigits;

import java.util.Scanner;

public class SumOfDigitsOfNumN {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the Number: ");
        int number = sc.nextInt();
        System.out.println("Sum of digits is "+getSum(number));
    }
    
    public static int getSum(int number){
        int lsd = number%10; // least significant digit
        int remainingNum = number/10;
        if(remainingNum == 0){
            return lsd;
        }
        return lsd+getSum(remainingNum);
    }
}

Detecting if a binary tree is a Binary Seach Tree: Java implementation

Hello Friends,

Today I am with you with another algorithm. Its about detecting if a Binary tree is a BST or not. A regular binary tree is a tree for which each node has number of children equal to 0, 1 or 2. A binary search tree has same properties as of regular binary tree with an additional property according to which any node has data  smaller than the data in its right child and greater data than the data in its left child.


We have two binary trees below.







Friends Lets look at the Java implementation solving this problem statement.

[Note that tree[] holds actual tree node values, left[] holds the index in tree[] corresponding to the left child of the each index and right[] holds the index in tree[] corresponding to the right child of the each index]

public class BSTDetector {
    // tree holds actual tree node values
    Integer tree[];
    // holds the index in tree[] corresponding to the left child of the each index
    Integer left[];
    // holds the index in tree[] corresponding to the right child of the each index
    Integer right[];

    public boolean isBinaryTreeBST(Integer tree[], Integer left[], Integer right[]) {
        this.tree = tree;
        this.left = left;
        this.right = right;
        return detectBST(Integer.MIN_VALUE, Integer.MAX_VALUE, 0);
    }

    private boolean detectBST(int leftRange, int rightRange, int currentIndex) {
        boolean isLeftChildvalid = true;
        boolean isRightChildValid = true;
        if (left[currentIndex] != null) {
            isLeftChildvalid = tree[currentIndex] >= tree[left[currentIndex]];
        }
        if (right[currentIndex] != null) {
            isRightChildValid = tree[currentIndex] <= tree[right[currentIndex]];
        }
        boolean isInRange = leftRange <= tree[currentIndex] && tree[currentIndex] <= rightRange;
        if (!isRightChildValid || !isLeftChildvalid || !isInRange) {
            return false;
        }
        boolean isLeftTreeBST = true;
        boolean isRightTreeBST = true;
        if (left[currentIndex] != null) {
            isLeftTreeBST = detectBST(leftRange, tree[currentIndex], left[currentIndex]);
        }
        if (right[currentIndex] != null) {
            isRightTreeBST = detectBST(tree[currentIndex], rightRange, right[currentIndex]);
        }

        return isLeftTreeBST && isRightTreeBST;
    }

    public static void main(String[] args) {
        Integer tree[] = { 10, 8, 6, 22, 12, 14 };
        Integer left[] = { 1, null, null, null, null, 2 };
        Integer right[] = { 4, null, null, null, 5, 3 };
        BSTDetector bstDetector = new BSTDetector();
        boolean isBST = bstDetector.isBinaryTreeBST(tree, left, right);
        System.out.println(isBST);

        Integer anotherInputTree[] = { 10, 8, 14, 22, 12, 15 };
        Integer anotherInputLeft[] = { 1, null, null, null, null, 2 };
        Integer anotherInputRight[] = { 4, null, null, null, 5, 3 };
        isBST = bstDetector.isBinaryTreeBST(anotherInputTree, anotherInputLeft, anotherInputRight);
        System.out.println(isBST);
    }
}

 

Root to Leaf Sum in a Binary tree : java Implementation

Hello friends,

Suppose we have a binary tree (not necessary a binary search tree), whose each node represent an Integer. We have a number: SUM. We need to find if there exist a path from Root to any Leaf such that sum of all the nodes equals the SUM. The path should contain full path from Root to a Leaf node.



If we have a binary tree as above and SUM as 26 then the Valid path comprises of (11,5,10) and not 10 and 16 as 10 and 16 is not a complete path from root to leaf but (11,5,10) nodes create a path from root (10) to leaf (11).


Friends, please find below the java code solving this problem. Please note that for representing the binary tree three arrays have been used. :
1. tree[] : This holds the actual values of the tree. This is 0 indexed array.
2. left[] : This  holds index of left child for the current index.
3. right[] : This holds index of right child for the current index.

public class RootToLeafSumInBinaryTree {
    
    // tree holds actual tree node values
    static Integer tree[] = { 10, 16, 5, -3, 6, 11 };
    // holds the index in tree[] corresponding to the left child of the each index
    static Integer left[] = { 1, null, 4, null, null, null };
    // holds the index in tree[] corresponding to the right child of the each index
    static Integer right[] = { 2, 3, 5, null, null, null };
    static Integer result[] = new Integer[tree.length];
    static int resultIndex = 0;

    public static void main(String[] args) {

        Integer sum = 21;
        boolean isSuccess = rootToSum(0, sum);
        for (int i = 0; isSuccess &&  i < resultIndex; i++) {
            System.out.println(result[i]);
        }
    }

    public static boolean rootToSum(int currentIndex, Integer sum) {
        if (left[currentIndex] == null && right[currentIndex] == null) {
            if (sum - tree[currentIndex] == 0) {
                result[resultIndex++] = tree[currentIndex];
                return true;
            } else {
                return false;
            }
        }
        boolean isLeftSuccess = false;
        boolean isRightSuccess = false;
        sum = sum - tree[currentIndex];
        if (left[currentIndex] != null) {
            isLeftSuccess = rootToSum(left[currentIndex], sum);
        }
        if (right[currentIndex] != null) {
            isRightSuccess = rootToSum(right[currentIndex], sum);
        }
        // be careful here we need to see if we get success from Either of Left
        // or Right branch we need to return Success as we have a path where the
        // sum is equal to the provided sum. 
        if (isLeftSuccess || isRightSuccess) {
            result[resultIndex++] = tree[currentIndex];
            return true;
        }
        return false;
    }
}