c++recursionbacktrackingpush-backn-queens

Vector push_back() and direct assignment using [] give different results


I'm trying to do this nQueens problem and my code looks like this:

 class Solution {
public:
    vector<vector<string>> ans;
    
    bool canPlace(vector<string> &board, int row, int col, int n){
        //upper left diagonal
        int rowIndex = row;
        int colIndex = col;
        while(rowIndex >= 0 and colIndex >= 0){
            if(board[rowIndex][colIndex] == 'Q'){
                return false;
            }
            rowIndex--;
            colIndex--;
        }
        
        // left side
        rowIndex = row;
        colIndex = col;
        while(colIndex >= 0){
            if(board[rowIndex][colIndex] == 'Q'){
                return false;
            }
            colIndex--;
        }
        
        // left side
        rowIndex = row;
        colIndex = col;
        while(rowIndex < n and colIndex >= 0){
            if(board[rowIndex][colIndex] == 'Q'){
                return false;
            }
            rowIndex++;
            colIndex--;
        }
        
        return true;
    }
    
    void nQueens(vector<string> &board, int col, int n){
        if(col == n){
            ans.push_back(board);
            for(int i = 0; i < n; i++){
                cout<<board[i]<<", ";
            }
            cout<<endl;
            return;
        }
        
        for(int row = 0; row < n; row++){
            if(canPlace(board, row, col, n)){
                cout<<"Changing board from: "<<board[row][col]<<endl;
                board[row][col] = 'Q';
                nQueens(board, col+1,n);
                board[row][col] = '.';
            }
        }
    }
    
    vector<vector<string>> solveNQueens(int n) {
        vector<string> board(n);
        string s(n, '.');

        for(int i = 0; i < n; i++){
            board[i] = s;
            // push_back gives weird result
        }
        
        nQueens(board, 0, n);
        return ans;
    }
};

In the last solveNQueens function. Inside the for loop, if I use board.push_back(s) instead of board[i] = s, leetcode throws a Wrong Answer error and the output when using cout shows weird random symbols. Why is this? Shouldn't push_back give the same results? I'd love to know why this happens.

Here's the link to the leetcode problem: https://leetcode.com/problems/n-queens


Solution

  • vector<string> board(n);
    

    fills the vector already with n elements. If you now add additional! elements with push_back, you have a vector with two times elements. The first half are already in from the constructor of std::vector and the second half pushed in later.

    If you use the default constructor

    vector<string> board;
    

    in combination with push_back, you will get the same results as with your example code.

    For large vectors the solution with upfront initialization of n elements and access via operator[] can be much faster, because there is no need of reallocation and copy operations inside the vector. If speed is important: measure!