Accepted C++ code : 8 ms : Beats 62% of submissions


  • 0
    P

    Hello,
    Can anyone help, how can I make it 4ms solution ?

    class Solution {
        public:
            void solveNQueensUtil(int n, vector<vector<string> > & ans, vector<string> & status, vector<int> & row, vector<int> & col, vector<int> & sum, vector<int> & diff, int level)
            {
            	if(level == n)
            	{
            		vector<string> result;
            		for(int i=0; i<n; i++)
            		{
            			string temp;
            			for(int j=0; j<n; j++)
            				temp.push_back(status[i][j]);
            			result.push_back(temp);
            			temp.clear();
            		}
            		ans.push_back(result);
            		return ;
            	}
            	for(int i=0; i<n; i++)
            	{
            		if(level+i < 2*n-1 && n-1+(level-i) >= 0 && n-1+(level-i) < 2*n-1 && row[level] == 0 && col[i] == 0 && sum[level+i] == 0 && diff[n-1+(level-i)] == 0)
            		{
            			string temp(n,'.');
            			temp[i] = 'Q';
            			status.push_back(temp);
            			row[level] = 1;
            			col[i] = 1;
            			sum[level+i] = 1;
            			diff[n-1+(level-i)] = 1;
            			solveNQueensUtil(n, ans, status, row, col, sum, diff, level+1);
            			status.pop_back();
            			row[level] = 0;
            			col[i] = 0;
            			sum[level+i] = 0;
            			diff[n-1+(level-i)] = 0;
            		}
            	}
            	return ;
            }
            vector<vector<string> > solveNQueens(int n) {
                    vector<string> status;
                    vector<int> row(n, 0);
                    vector<int> col(n, 0);
                    vector<int> sum(2*n-1, 0);
                    vector<int> diff(2*n-1, 0);
                    vector<vector<string> > res;
                    solveNQueensUtil(n, res, status, row, col, sum, diff, 0);
                    status.clear();
                    row.clear();
                    col.clear();
                    sum.clear();
                    diff.clear();
                    return res;
            }
        };

Log in to reply
 

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