DFS IV

More about dfs.

Article Language: English
Example Language: Java
Reading Time: 7min

N Queen

input: a integer n.
output: return all distinct solutions to the n-queens puzzle.

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Using dfs to try row by row to see which column is valid. If valid, go to next row, otherwise, continue. The index of the list represents the row, and the valud of the index is the number of column it can be put. Fom the top to current row, if column has a queen, or the absolute value between columns and rows are the same, then it is not a valid position. The time complexity is O(n!), the space complexity is O(n).

A little bit different from LeetCode 51.

public class NQueen {
    /**
     * @param n
     * @return
     */
    public List<List<Integer>> findNQueen (int n) {
        if (n <= 0) {
            return new ArrayList<>();
        }
        List<List<Integer>> result = new ArrayList<>();
        helper(n, new ArrayList<>(), result);
        return result;
    }

    private void helper(int input, List<Integer> subSol, List<List<Integer>> result) {
        if (subSol.size() == input) {
            result.add(new ArrayList<>(subSol));
            return;
        }

        for (int i = 0; i < input; i++) {
            if (isValid(i, subSol)) {
                subSol.add(i);
                helper(input, subSol, result);
                subSol.remove(subSol.size() - 1);
            }
        }
    }

    private boolean isValid(int column, List<Integer> subSol) {
        for (int i = 0; i < subSol.size(); i++) {
            if (subSol.get(i) == column || subSol.size() - i == Math.abs(column - subSol.get(i))) {
                return false;
            }
        }
        return true;
    }
}

Flood Fill

input: 2D array, start position, and int represent newColor.
output: 2D array after changing color.

This is a typical dfs. Traverse to 4 directions from a knwon start point. The time complexity is O(m + n) since it doesn’t need to return previous status. The space complexisty is O(max(m, n)) due to the usage of call stack.
The complexity is based on assuming changing input is possible, otherwise a separate data structure to record visited point is needed.

public class FloodFill {
    /**
     * @param image: a 2-D array
     * @param sr: an integer
     * @param sc: an integer
     * @param newColor: an integer
     * @return: the modified image
     */
    private int[][] dirs = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        if(image == null || image[0] == null || image.length == 0 || image[0].length == 0) {
            return image;
        }
        if (image[sr][sc] == newColor) {
            return image;
        }

        helper(image, sr, sc, newColor, image[sr][sc]);
        return image;
    }

    private void helper(int[][] image, int sr, int sc, int newColor, int initial) {
        image[sr][sc] = newColor;
        for (int[] dir : dirs) {
            int x = sr + dir[0];
            int y = sc + dir[1];
            if (x >= image.length || y >= image[0].length  || x < 0 || y < 0 || image[x][y] != initial) {
                continue;
            }
            image[x][y] = newColor;
            helper(image, x, y, newColor, initial);
        }
    }
}