Too slow

  • 0
        def pacificAtlantic(self, matrix):
            :type matrix: List[List[int]]
            :rtype: List[List[int]]
            if not matrix:
                return []
            result = []
            num_rows = len(matrix)
            num_cols = len(matrix[0])
            for index_row in range(num_rows):
                for index_col in range(num_cols):
                    if self.check(matrix, index_row, index_col):
                        result.append([index_row, index_col])
            return result
        def check(self, matrix, row, col):
            to_check = []
            left_up = False
            right_down = False
            input_set = set((row, col))
            to_check.append(([row, col], input_set)) # Current position and visited list
            while to_check:
                current_pos, explored = to_check.pop()
                row = current_pos[0]
                col = current_pos[1]
                current_val = matrix[row][col]
                row_min, row_max, col_min, col_max = False, False, False, False
                if row == 0:
                    left_up = True
                    row_min = True
                if col == 0:
                    left_up = True
                    col_min = True
                if row == len(matrix)-1:
                    right_down = True
                    row_max = True
                if col == len(matrix[0])-1:
                    right_down = True
                    col_max = True
                if left_up and right_down:
                    return True
                if not row_min and matrix[row-1][col] <= current_val and (row-1, col) not in explored:
                    explored.add((row-1, col))
                    to_check.append(([row-1, col], explored))
                if not col_min and matrix[row][col-1] <= current_val and (row, col-1) not in explored:
                    explored.add((row, col-1))
                    to_check.append(([row, col-1], explored))
                if not col_max and matrix[row][col+1] <= current_val and (row, col+1) not in explored:
                    explored.add((row, col+1))
                    to_check.append(([row, col+1], explored))
                if not row_max and matrix[row+1][col] <= current_val and (row+1, col) not in explored:
                    explored.add((row+1, col))
                    to_check.append(([row+1, col], explored))
            return False```
    I think my solution works but is too slow (TLE). Any ideas on how I can make it faster?

Log in to reply

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