Java code giving TLE. Why?


  • 0
    S
    public class Solution {
        ArrayList<List<String>> lists = null;
        public List<List<String>> solveNQueens(int n) {
            lists = new ArrayList<List<String>>();
            
            if (n == 0) {
                return lists;
            }
            
            char[][] qPlace = new char[n][n];
            boolean[][] dangerous = new boolean[n][n];
            
            for (int i = 0; i < n; ++i) {
                Arrays.fill(qPlace[i], '.');
            }
            for (int i = 0; i < n; ++i) {
                solve(0, i, n, qPlace, dangerous);
            }
            
            return lists;
        }
        
        void solve(int r, int c, int n, char[][] qPlace, boolean[][] dangerous) {
            if (r == n) {
                List<String> list = new ArrayList<String>();
                for (int i = 0; i < n; ++i) {
                    list.add(new String(qPlace[i]));
                }
                lists.add(list);
            }
            else {
                int k = c;
                do {
                    if (!dangerous[r][k]) {
                        qPlace[r][k] = 'Q';
                        int add = 0;
                        while (r+add < n && c+add < n) {
                            dangerous[r+add][c+add] = true;
                            add++;
                        }
                        add = 0;
                        while (r+add < n && c-add >= 0) {
                            dangerous[r+add][c-add] = true;
                            add++;
                        }
                        add = 0;
                        while (r+add < n) {
                            dangerous[r+add][c] = true;
                            add++;
                        }
                        solve(r+1, (c+2)%n, n, qPlace, dangerous);
                        add = 0;
                        while (r+add < n && c+add < n) {
                            dangerous[r+add][c+add] = false;
                            add++;
                        }
                        add = 0;
                        while (r+add < n && c-add >= 0) {
                            dangerous[r+add][c-add] = false;
                            add++;
                        }
                        add = 0;
                        while (r+add < n) {
                            dangerous[r+add][c] = false;
                            add++;
                        }
                        qPlace[r][k] = '.';
                    }
                    k++;
                    k %= n;
                } while(k != c);
            }
        }
    }

  • 0
    K

    If you are still looking for an answer, your code is using 2d array. That might just not be needed.


Log in to reply
 

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