Why am I getting TLE in python?


  • 0
    C

    This is definitely on the slow side compared to others, but it does ok on my pc.

    class Solution(object):
        def test_col(self, arr, r,c):
            for i in range(r):
                if arr[i][c] == "Q":
                    return False
            return True
            
        def test_diagonal(self, arr,  r,c):
            #left diagonal
            i, j = r-1, c-1
            while i >= 0 and j >=0:
                if arr[i][j] == "Q":
                    return False
                i -= 1
                j -= 1
            #right diagonal
            i, j = r-1, c+1
            while i in range(self.n) and j in range(self.n):
                if arr[i][j] == "Q":
                    return False
                i -= 1
                j += 1
            return True
                
        def test_pos(self, arr,  r,c):
            if self.test_col(arr,r,c) and self.test_diagonal(arr,r,c):
                return True
            else:
                return False
        def placeQueenRow(self, arr, r, col):
            row = r
            for c in range(self.n):
                if c not in col:
                    board = copy.deepcopy(arr)
                    if self.test_pos(board,r,c):
                        board[row] = "."*c +"Q" + "."*(self.n - 1 - c)
                        if row == self.n - 1:
                            self.ans.append(board)
                        self.placeQueenRow(board, row + 1, copy.deepcopy(col))
    
        def solveNQueens(self, n):
            """
            :type n: int
            :rtype: List[List[str]]
            """
            self.ans = []
            self.n = n
            arr = ["."*n for y in range(n)]
            
            self.placeQueenRow(arr, 0, [])
    
            return self.ans
    

Log in to reply
 

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