Solution to "Unique Path III" on Leetcode

UniquePathsIII.java

class Solution {
    
    /*
    Approach:
    - Find start position
    - Count number of visitable nodes in the grids
    - A path is only valid if we read end node && all visitable nodes have been visited
    - Perform dfs, everytime we visit a cell, we mark as visited. 
    - We cannot visit a cell more than once
    - Handle boundary edge cases too
    */
    public int uniquePathsIII(int[][] grid) {
        int[] start = findStartPosition(grid);
        int nonObstacleCells = countNonObstacleCells(grid);

        boolean[][] seen = new boolean[grid.length][grid[0].length];
        seen[start[0]][start[1]] = true;
        int paths =  countUniquePaths(start[0] + 1, start[1], nonObstacleCells, grid, seen);
        paths +=  countUniquePaths(start[0] - 1, start[1], nonObstacleCells, grid, seen);
        paths +=  countUniquePaths(start[0], start[1] + 1, nonObstacleCells, grid, seen);
        paths +=  countUniquePaths(start[0], start[1] - 1, nonObstacleCells, grid, seen);

        return paths;
    }

    // sR = start row, sC = start col, eR = end row, eC = end col
    private int countUniquePaths(int sR, int sC, int nonObstacleCells, int[][] grid, boolean[][] seen) {
        if (sR < 0 || sR >= grid.length || sC < 0 || sC >= grid[0].length) {
            return 0;
        }

        if (grid[sR][sC] == 2 && nonObstacleCells == 0) {
            return 1;
        }

        if(grid[sR][sC] == 2){
            return 0;
        }


        if (grid[sR][sC] == -1 || seen[sR][sC]) {
            return 0;
        }


        seen[sR][sC] = true;
        int paths = countUniquePaths(sR + 1, sC, nonObstacleCells - 1, grid, seen);
        paths += countUniquePaths(sR - 1, sC, nonObstacleCells - 1, grid, seen);
        paths += countUniquePaths(sR, sC + 1, nonObstacleCells - 1, grid, seen);
        paths += countUniquePaths(sR, sC - 1, nonObstacleCells - 1, grid, seen);
        seen[sR][sC] = false;

        return paths;
    }

    private int[] findStartPosition(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    return new int[]{i, j};
                }
            }
        }

        return new int[]{-1, -1};
    }

    private int countNonObstacleCells(int[][] grid) {
        int nonObstacleCnt = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 0) {
                    nonObstacleCnt++;
                }
            }
        }

        return nonObstacleCnt;
    }
}