Accepted : auxillary space O(n) , using dfs , cpp


  • 24
    L

    Space complexity : Instead of using a 2D array to represent the chess board, i am using a 1D array , the index of which would represent the row number and the value of arr at row index will be the column number for the correct position of the queen.

    i.e

           Instead of doing  arr[row][col]=1
           i am using arr[row]=col ;               where queen is positioned at (row,col);
    

    Logic : DFS for every column number ,ranging from 0 to n-1, for all the rows from 0 to n-1 and check the validity of queen position for every row,col combination(using isSafe function)

    isSafe function : It checks whether the queen in current position(r,c) is being attacked by any of the r-1 queens positioned in row numbers 0 through r-1.

     class Solution {
        public:
            vector < vector <string> > sol;
            int limit;
            
            vector<string> toChessString(vector<int> arr) 
              {
                string s(arr.size(),'.');
                vector<string> ans(arr.size(),s);
        
                for(int i=0 ; i<arr.size() ; i++)
                  ans[i][arr[i]]='Q';
        
                  return ans;
              }
        
        
            bool isSafe(vector<int> arr, int r , int c )
             {
                int check;
                for(int row=r-1,ldia=c-1,rdia=c+1 ; row>=0 ; row--,ldia--,rdia++)
                {
                    check=arr[row];
        
                    if(check==c || check==ldia || check==rdia)
                     return false;
                }
                return true;
             }
        
            void solveNqueen(vector<int> arr , int r , int c)
            {
                if(r==limit)
                 sol.push_back(toChessString(arr));
                    
                else
                 {
                     for(int col=c ; col<limit ; col++)
                     {
                        arr[r]=col;
        
                        if(isSafe(arr,r,col))
                          solveNqueen(arr,r+1,0);
                     }
                 }
            }
        
        
            vector<vector<string> > solveNQueens(int n) {
                vector<int> arr(n,0);
                limit=n;
                solveNqueen(arr,0,0);
              
                return sol;
            }
        };

  • 0
    K

    Very good answer and very clear analysis


  • 0
    J

    use reference will be faster, like vector<int> &arr


  • 0
    H

    just curious, if you have never heard this problem before, how long can you come up with a solution?


  • 0
    M

    is arr parsing in the recursive call is the same? example, 2x2, when

    1. r=0, arr[0]=0, solveNqueen(arr,1,0)
    2. r=1, arr[1]=0 (not safe), arr[1]=1, solveNqueen(arr,2,0)
    3. 2==limit, sol.push_back(arr)
      3 terminated, back to 2, 2 terminated, back to 1. at that time, what is arr value?

  • 0

    arr is equal to the value when it enters the recursion.


  • 3

    Hi, leet_nik. Good idea to replace the 2d record by the nice 1d record arr[row] = col.

    I have reorganized your code below. I hope it is Ok.

    class Solution { 
    public:
        vector<vector<string>> solveNQueens(int n) {
            vector<vector<string> > queens;
            vector<int> colPos(n, 0);
            solve(colPos, n, 0, queens);
            return queens;
        }
    private:
        bool noAttack(vector<int>& colPos, int row, int col) {
            for (int r = row - 1, ld = col - 1, rd = col + 1; r >= 0; r--, ld--, rd++)
                if (colPos[r] == col || colPos[r] == ld || colPos[r] == rd)
                    return false;
            return true;
        }
        vector<string> queenStr(vector<int>& colPos) {
            int n = colPos.size();
            vector<string> queen(n, string(n, '.'));
            for (int i = 0; i < n; i++)
                queen[i][colPos[i]] = 'Q';
            return queen;
        }
        void solve(vector<int>& colPos, int n, int row, vector<vector<string> >& queens) {
            if (row == n) {
                queens.push_back(queenStr(colPos));
                return;
            }
            for (int col = 0; col < n; col++) {
                colPos[row] = col;
                if (noAttack(colPos, row, col))
                    solve(colPos, n, row + 1, queens);
            }
        }
    };

  • 0
    M

    got it, the solveNqueen is parsing value of arr, not pointer. so each function will have its own arr. once function call completed, the arr in previews func kept the value before enter the recursion. 2 question,

    1. arr[r]=col is outside isSafe check, so there will be lots of false value in arr. should it be inside "if"?
    2. int c, every rec call parsing "0". is it need ? i think it can be removed.

  • 0
    M

    take back my q1. since arr[r]=col, if not safe, it will be overwritten. inside ,outside check is the same.


  • 0

    Hi, mifowa. The parameter c in solveNqueen is actually unnecessary and can be safely removed.


  • 0
    Z

    Great one! classic coding style for backtracking problems


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.