NQueen optimized

Optimization Method: Improve valid position check to O(1)

High Level: use three boolean[] to check current column , leftDiagonal, and rightDiagonal

  public List<List<Integer>> nqueens(int n) {
    List<List<Integer>> result = new ArrayList<>();
    int[] cur = new int[n];
    boolean[] column = new boolean[n];
    boolean[] leftDiagonal = new boolean[2 * n - 1];
    boolean[] rightDiagonal = new boolean[2 * n - 1];

    helper(n, 0, cur, result, column, leftDiagonal, rightDiagonal);
    return result;
  }

  private void helper(int n, int row, int[] cur, List<List<Integer>> result, boolean[] column, boolean[] leftDiagonal ,boolean[] rightDiagonal){
    if (row == n){
      result.add(toList(cur));
      return;
    }
    for (int i = 0; i < n; i++){
      if (isValid(n, row, i, column, leftDiagonal, rightDiagonal)){
        mark(n, row, i, column, leftDiagonal, rightDiagonal);
        cur[row] = i;
        helper(n, row + 1, cur, result, column, leftDiagonal, rightDiagonal);
        unMark(n, row, i, column, leftDiagonal, rightDiagonal);
      }
    }
  }

  private boolean isValid(int n , int row, int col, boolean[] column, boolean[] leftDiagonal ,boolean[] rightDiagonal){
    return !column[col] && !leftDiagonal[col - row + n -1] && !rightDiagonal[col + row];
  }

  private void mark(int n , int row, int col, boolean[] column, boolean[] leftDiagonal ,boolean[] rightDiagonal){
    column[col] = true;
    leftDiagonal[col - row + n - 1] = true; //column - row range; -{n -1) -> (n - 1)
    rightDiagonal[col + row] = true; //0 -> (n -1) * 2
  }

  private void unMark(int n , int row, int col, boolean[] column, boolean[] leftDiagonal ,boolean[] rightDiagonal){
    column[col] = false;
    leftDiagonal[col - row + n - 1] = false; //column - row range; -{n -1) -> (n - 1)
    rightDiagonal[col + row] = false; //0 -> (n -1) * 2
  }

  private List<Integer> toList(int[] input){
    List<Integer> result = new ArrayList<>();
    for (int x: input){
      result.add(x);
    }
    return result;
  }

Time Complexity: O(N!) helper calls * O(1) valid check = O(N!)

Space Complexity: O(N) List cur * ~O(N) List result = O(N^2)