1958. Check if Move Is Legal - Explanation

Problem Link



1. Iteration - I

class Solution:
    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:
        ROWS, COLS = len(board), len(board[0])
        direction = [[1, 0], [-1, 0], [0, 1], [0, -1],
                     [1, 1], [-1, -1], [1, -1], [-1, 1]]

        board[rMove][cMove] = color

        def legal(row, col, color, direc):
            dr, dc = direc
            row, col = row + dr, col + dc
            length = 1

            while 0 <= row < ROWS and 0 <= col < COLS:
                length += 1
                if board[row][col] == ".":
                    return False
                if board[row][col] == color:
                    return length >= 3
                row, col = row + dr, col + dc
            return False

        for d in direction:
            if legal(rMove, cMove, color, d):
                return True
        return False

Time & Space Complexity

  • Time complexity: O(1)O(1)
  • Space complexity: O(1)O(1)

2. Iteration - II

class Solution:
    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:
        ROWS, COLS = len(board), len(board[0])
        direction = [0, 1, 0, -1, 0, 1, 1, -1, -1, 1]

        board[rMove][cMove] = color

        for d in range(9):
            length = 1
            row, col = rMove, cMove
            while True:
                row += direction[d]
                col += direction[d + 1]

                if row < 0 or col < 0 or row >= ROWS or col >= COLS or board[row][col] == ".":
                    break
                if board[row][col] == color:
                    if length > 1:
                        return True
                    break
                length += 1

        return False

Time & Space Complexity

  • Time complexity: O(1)O(1)
  • Space complexity: O(1)O(1)