Skip to main content

Matrix

Check if Move is Legal Solution In C++/Python/java/JS

Problem Description:

You are given a 0-indexed 8 x 8 grid board, where board[r][c] represents the cell (r, c) on a game board. On the board, free cells are represented by '.', white cells are represented by 'W', and black cells are represented by 'B'.
Each move in this game consists of choosing a free cell and changing it to the color you are playing as (either white or black). However, a move is only legal if, after changing it, the cell becomes the endpoint of a good line (horizontal, vertical, or diagonal).
A good line is a line of three or more cells (including the endpoints) where the endpoints of the line are one color, and the remaining cells in the middle are the opposite color (no cells in the line are free). You can find examples for good lines in the figure below
Check if Move is Legal-Problem-Description
Given two integers rMove and cMove and a character color representing the color you are playing as (white or black), return true if changing cell (rMove, cMove) to color color is a legal move, or false if it is not legal.

Examples:

Check if Move is Legal-Problem-Description-Example-1

Input: board = [[".",".",".","B",".",".",".","."],[".",".",".","W",".",".",".","."],[".",".",".","W",".",".",".","."],[".",".",".","W",".",".",".","."],["W","B","B",".","W","W","W","B"],[".",".",".","B",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","W",".",".",".","."]], rMove = 4, cMove = 3, color = "B"
Output: true
Explanation: '.', 'W', and 'B' are represented by the colors blue, white, and black respectively, and cell (rMove, cMove) is marked with an 'X'.
The two good lines with the chosen cell as an endpoint are annotated above with the red rectangles.

Check if Move is Legal-Problem-Description-Example-2

Input: board = [[".",".",".",".",".",".",".","."],[".","B",".",".","W",".",".","."],[".",".","W",".",".",".",".","."],[".",".",".","W","B",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".","B","W",".","."],[".",".",".",".",".",".","W","."],[".",".",".",".",".",".",".","B"]], rMove = 4, cMove = 4, color = "W"
Output: false
Explanation: While there are good lines with the chosen cell as a middle cell, there are no good lines with the chosen cell as an endpoint.

Constraints:

  • board.length == board[r].length == 8
  • 0 <= rMove, cMove < 8
  • board[rMove][cMove] == '.'
  • color is either 'B' or 'W'.

Check if Move is Legal Problem

We are given a matrix board and the following inputs:

  • (rMove, cMove): The row and column where a piece will be placed.
  • color ('B' for Black, 'W' for White): The color of the piece to be placed.

Our task is to place the given color at (rMove, cMove) and determine whether it creates a good line, following these conditions:

A good line must:

  1. Start at the given position as one endpoint and have another piece of the same color at the other endpoint in a straight direction.
  2. Contain only the opposite color in between (no empty spaces).
  3. Be aligned vertically, horizontally, or diagonally.

If at least one such line is formed, we return True; otherwise, we return False.

Brute Force Approach

Intuition:

Now that we understand the problem, how should we approach solving it?

The first thought that comes to mind is to go as per the problem statement. Given rMove and cMove, and character colour. Let's start with placing the colour at the coordinates (rMove, cMove).

Once the piece is placed, we will then check whether it forms an endpoint of a good line in any direction (vertically, horizontally, or diagonally).

If we find a good line in any direction, we simply return True. However, if none of the directions form a valid line, we return False.

💡
Try to solve the problem yourself first !

To do this, we first place the given colour at the specified coordinates on the board.

Next, we need to check if this move creates a good line in any direction. Since a good line can be formed in different ways, we must check in 8 possible directions:

  1. Down (moving downward in the same column)
  2. Up (moving upward in the same column)
  3. Right (moving right in the same row)
  4. Left (moving left in the same row)
  5. Bottom Right Diagonal (moving diagonally down-right)
  6. Top Left Diagonal (moving diagonally up-left)
  7. Top Right Diagonal (moving diagonally up-right)
  8. Bottom Left Diagonal (moving diagonally down-left)

How to check if there is a good line in any direction or not?

To check if a move creates a good line, we need to carefully follow a few simple steps. Let’s break it down.

Step 1: Checking the Next Cell

Before we start looking for a valid line, the first thing we need to check is the next cell in the given direction. Why is this important? Because for a line to be good, the very next cell must be of the opposite colour.

  • If the next cell is empty (.) or the same colour, we stop right there because a valid line cannot be formed in that direction.
  • But if the next cell is of the opposite colour, we continue checking further.

E.g.. Assume that the first row of the 8x8 board is like this

['.', 'B', 'W', 'W', 'B'], rMove = 0, cMove = 0, colour = 'B'

Now, once we place colour 'B' at (0,0). we get

['B', 'B', 'W', 'W', 'B']

So step 1 says that we can only proceed to next step when the adjacent cell lying in the direction we are checking is of opposite color.

Meaning here to find a good line on the right side, we first need (0, 1) to be 'W'. Which is not the case in the example, it is black, hence we can't find a good line on the right side

Step 2: Searching for an Endpoint

Once we confirm that the next cell is of the opposite colour, we start moving step by step in that direction. Our goal is to find another piece of the same colour as the one we just placed. This would act as the other endpoint of the line.

While moving, we need to carefully check each cell:

  • If we find the same colour as the character colour given to us, it means we have a good line, and we return true.
  • If we find an empty cell (.) before reaching the same colour, then the line is broken, and we stop checking in this direction.

E.g.. Assume that the first row of the 8x8 board is like this

['.', 'W', 'W', 'W', 'B'], rMove = 0, cMove = 0, colour = 'B'

Now, once we place colour 'B' at (0,0). we get

['B', 'W', 'W', 'W', 'B']

We start checking from (0, 2). Because we have already verified (0,1) in step 1.

So, we start from (0,2) until we find a 'B' (same as character colour) or a '.'.

If we arrive at some 'B', that means we have found a good line and we return true. On the other hand, if we arrive at some '.'. This means there can't be a good line in the particular direction we are processing, so we move to the next direction.

Step 3: Checking All 8 Directions

We repeat this same process in all 8 directions—up, down, left, right, and the four diagonals.

  • If at least one direction forms a valid line, we immediately return true.
  • If none of the directions result in a valid line, all the loops will end without returning true, and we return false.

Real World Example:

Think of it like drawing a straight line on a chessboard. If you place a piece and it "connects" to another piece of the same colour with only the opposite colour in between, then it's a good move. If there's a gap ('.'). or it doesn't connect properly, then it's not valid.

This method ensures that we correctly check every possible way a valid line can form.

0:00
/0:50

Check if Move is Legal-Animation Showing How Optimal Approach Works.

Check if Move is Legal Example

Input: board = [
['.', '.', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', 'W', '.', '.', '.', '.'],
['.', '.', 'W', 'B', 'W', '.', '.', '.'],
['.', '.', '.', 'W', '.', '.', '.', '.'],
['.', '.', '.', '.', 'W', '.', '.', '.'],
['.', '.', '.', '.', '.', 'B', '.', '.'],
['.', '.', '.', '.', '.', '.', '.', '.']
];

rMove = 3, cMove = 2, color = 'B'

Step 1: Place 'B' at (3,2)

We update the board:

board[3][2] = 'B';

Our task is to check if placing 'B' at (3,2) creates a valid line.

Step 2: Check Each of the 8 Directions

We are looking for:

  1. An opposite color 'W' immediately next to (3,2) in a given direction.
  2. A continuation of 'W' pieces until we find another 'B' at the other endpoint.
  3. No empty cell ('.') in between.

The opposite color (oppositeColor) = 'W'.

Direction 1: Down (↓)

  • Next cell (4,2) → board[4][2] = '.' (empty) → Not a valid line

Direction 2: Up (↑)

  • Next cell (2,2) → board[2][2] = '.' (empty) → Not a valid line

Direction 3: Right (→)

  • Next cell (3,3) → board[3][3] = 'B' (same color) → Not a valid line

Direction 4: Left (←)

  • Next cell (3,1) → board[3][1] = '.' (empty) → Not a valid line

Direction 5: Bottom-Right Diagonal (↘)

  • Next cell (4,3) → board[4][3] = 'W'
  • Next cell (5,4) → board[5][4] = 'W'
  • Next cell (6,5) → board[6][5] = 'B'

Since we have a 'B' at (6,5) as the endpoint, this forms a valid diagonal line. Hence we return true.

Final Result

Since we found a valid Bottom-Right Diagonal (↘) line, we return true.

Valid move! checkMove(board, 3, 2, 'B') returns true.

Check if Move is Legal Algorithm

Step 1: Place the given color on the board

  • Modify the board at position (rMove, cMove) to be the given color ('B' or 'W').

Step 2: Set the opposite color

  • If color == 'B', then oppositeColor = 'W'
  • If color == 'W', then oppositeColor = 'B'

Step 3: Prepare to check all 8 directions

You need to look in these directions from the placed cell:

  • Vertical:
    • Down
    • Up
  • Horizontal:
    • Right
    • Left
  • Diagonals:
    • Bottom-Right
    • Top-Left
    • Top-Right
    • Bottom-Left

Step 4: For each direction, do the following

  1. Move one step in that direction from (rMove, cMove)
  2. Check the next cell:
    • If it's not oppositeColor, skip this direction.
  4. If it is oppositeColor, keep moving in the same direction:
    • If you find '.', this direction is invalid → break.
    • If you find the same color, this is a valid move → return true.

Step 5: After checking all 8 directions

  • If no direction returns true, then return false. (No good line)
Check if Move is Legal Solutions in all languages
Check if Move is Legal Solution in C++ 
class Solution {
public:
    bool checkMove(vector<vector<char>>& board, int rMove, int cMove, char color) {
        // Place the piece at the given position
        board[rMove][cMove] = color;

        // Determine the opponent's color
        char oppositeColor = (color == 'B') ? 'W' : 'B';

        // Check Down (↓)
        if (rMove + 1 < 8 && board[rMove + 1][cMove] == oppositeColor) {
            for (int i = rMove + 2; i < 8; ++i) {
                if (board[i][cMove] == '.') break;
                else if (board[i][cMove] == color) return true;
            }
        }

        // Check Up (↑)
        if (rMove - 1 >= 0 && board[rMove - 1][cMove] == oppositeColor) {
            for (int i = rMove - 2; i >= 0; --i) {
                if (board[i][cMove] == '.') break;
                else if (board[i][cMove] == color) return true;
            }
        }

        // Check Right (→)
        if (cMove + 1 < 8 && board[rMove][cMove + 1] == oppositeColor) {
            for (int i = cMove + 2; i < 8; ++i) {
                if (board[rMove][i] == '.') break;
                else if (board[rMove][i] == color) return true;
            }
        }

        // Check Left (←)
        if (cMove - 1 >= 0 && board[rMove][cMove - 1] == oppositeColor) {
            for (int i = cMove - 2; i >= 0; --i) {
                if (board[rMove][i] == '.') break;
                else if (board[rMove][i] == color) return true;
            }
        }

        // Check Bottom-Right Diagonal (↘)
        if (rMove + 1 < 8 && cMove + 1 < 8 && board[rMove + 1][cMove + 1] == oppositeColor) {
            for (int i = rMove + 2, j = cMove + 2; i < 8 && j < 8; ++i, ++j) {
                if (board[i][j] == '.') break;
                else if (board[i][j] == color) return true;
            }
        }

        // Check Top-Left Diagonal (↖)
        if (rMove - 1 >= 0 && cMove - 1 >= 0 && board[rMove - 1][cMove - 1] == oppositeColor) {
            for (int i = rMove - 2, j = cMove - 2; i >= 0 && j >= 0; --i, --j) {
                if (board[i][j] == '.') break;
                else if (board[i][j] == color) return true;
            }
        }

        // Check Top-Right Diagonal (↗)
        if (rMove - 1 >= 0 && cMove + 1 < 8 && board[rMove - 1][cMove + 1] == oppositeColor) {
            for (int i = rMove - 2, j = cMove + 2; i >= 0 && j < 8; --i, ++j) {
                if (board[i][j] == '.') break;
                else if (board[i][j] == color) return true;
            }
        }

        // Check Bottom-Left Diagonal (↙)
        if (rMove + 1 < 8 && cMove - 1 >= 0 && board[rMove + 1][cMove - 1] == oppositeColor) {
            for (int i = rMove + 2, j = cMove - 2; i < 8 && j >= 0; ++i, --j) {
                if (board[i][j] == '.') break;
                else if (board[i][j] == color) return true;
            }
        }

        // No valid move found
        return false;
    }
};

Check if Move is Legal Solution in java 
class Solution {

    public static boolean checkMove(char[][] board, int rMove, int cMove, char color) {
        board[rMove][cMove] = color;
        char opposite = (color == 'B') ? 'W' : 'B';

        // Check ↓
        if (rMove + 1 < 8 && board[rMove + 1][cMove] == opposite) {
            for (int i = rMove + 2; i < 8; i++) {
                if (board[i][cMove] == '.') break;
                if (board[i][cMove] == color) return true;
            }
        }

        // Check ↑
        if (rMove - 1 >= 0 && board[rMove - 1][cMove] == opposite) {
            for (int i = rMove - 2; i >= 0; i--) {
                if (board[i][cMove] == '.') break;
                if (board[i][cMove] == color) return true;
            }
        }

        // Check →
        if (cMove + 1 < 8 && board[rMove][cMove + 1] == opposite) {
            for (int i = cMove + 2; i < 8; i++) {
                if (board[rMove][i] == '.') break;
                if (board[rMove][i] == color) return true;
            }
        }

        // Check ←
        if (cMove - 1 >= 0 && board[rMove][cMove - 1] == opposite) {
            for (int i = cMove - 2; i >= 0; i--) {
                if (board[rMove][i] == '.') break;
                if (board[rMove][i] == color) return true;
            }
        }

        // ↘
        if (rMove + 1 < 8 && cMove + 1 < 8 && board[rMove + 1][cMove + 1] == opposite) {
            for (int i = rMove + 2, j = cMove + 2; i < 8 && j < 8; i++, j++) {
                if (board[i][j] == '.') break;
                if (board[i][j] == color) return true;
            }
        }

        // ↖
        if (rMove - 1 >= 0 && cMove - 1 >= 0 && board[rMove - 1][cMove - 1] == opposite) {
            for (int i = rMove - 2, j = cMove - 2; i >= 0 && j >= 0; i--, j--) {
                if (board[i][j] == '.') break;
                if (board[i][j] == color) return true;
            }
        }

        // ↗
        if (rMove - 1 >= 0 && cMove + 1 < 8 && board[rMove - 1][cMove + 1] == opposite) {
            for (int i = rMove - 2, j = cMove + 2; i >= 0 && j < 8; i--, j++) {
                if (board[i][j] == '.') break;
                if (board[i][j] == color) return true;
            }
        }

        // ↙
        if (rMove + 1 < 8 && cMove - 1 >= 0 && board[rMove + 1][cMove - 1] == opposite) {
            for (int i = rMove + 2, j = cMove - 2; i < 8 && j >= 0; i++, j--) {
                if (board[i][j] == '.') break;
                if (board[i][j] == color) return true;
            }
        }

        return false;
    }
}

Check if Move is Legal Solution in Python 
class Solution:
    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:
        
        # Place the piece at the given position
        board[rMove][cMove] = color

        # Determine the opponent's color
        opposite = 'W' if color == 'B' else 'B'

        # Check Down (↓)
        if rMove + 1 < 8 and board[rMove + 1][cMove] == opposite:
            for i in range(rMove + 2, 8):
                if board[i][cMove] == '.': break
                elif board[i][cMove] == color: return True

        # Check Up (↑)
        if rMove - 1 >= 0 and board[rMove - 1][cMove] == opposite:
            for i in range(rMove - 2, -1, -1):
                if board[i][cMove] == '.': break
                elif board[i][cMove] == color: return True

        # Check Right (→)
        if cMove + 1 < 8 and board[rMove][cMove + 1] == opposite:
            for i in range(cMove + 2, 8):
                if board[rMove][i] == '.': break
                elif board[rMove][i] == color: return True

        # Check Left (←)
        if cMove - 1 >= 0 and board[rMove][cMove - 1] == opposite:
            for i in range(cMove - 2, -1, -1):
                if board[rMove][i] == '.': break
                elif board[rMove][i] == color: return True

        # Check Bottom-Right Diagonal (↘)
        if rMove + 1 < 8 and cMove + 1 < 8 and board[rMove + 1][cMove + 1] == opposite:
            i, j = rMove + 2, cMove + 2
            while i < 8 and j < 8:
                if board[i][j] == '.': break
                elif board[i][j] == color: return True
                i += 1
                j += 1

        # Check Top-Left Diagonal (↖)
        if rMove - 1 >= 0 and cMove - 1 >= 0 and board[rMove - 1][cMove - 1] == opposite:
            i, j = rMove - 2, cMove - 2
            while i >= 0 and j >= 0:
                if board[i][j] == '.': break
                elif board[i][j] == color: return True
                i -= 1
                j -= 1

        # Check Top-Right Diagonal (↗)
        if rMove - 1 >= 0 and cMove + 1 < 8 and board[rMove - 1][cMove + 1] == opposite:
            i, j = rMove - 2, cMove + 2
            while i >= 0 and j < 8:
                if board[i][j] == '.': break
                elif board[i][j] == color: return True
                i -= 1
                j += 1

        # Check Bottom-Left Diagonal (↙)
        if rMove + 1 < 8 and cMove - 1 >= 0 and board[rMove + 1][cMove - 1] == opposite:
            i, j = rMove + 2, cMove - 2
            while i < 8 and j >= 0:
                if board[i][j] == '.': break
                elif board[i][j] == color: return True
                i += 1
                j -= 1

        # No valid move found
        return False

Check if Move is Legal Solution in Javascript 
/**
 * @param {character[][]} board
 * @param {number} rMove
 * @param {number} cMove
 * @param {character} color
 * @return {boolean}
 */
var checkMove = function(board, rMove, cMove, color) {
    // Place the piece
    board[rMove][cMove] = color;
    let oppositeColor = (color === 'B') ? 'W' : 'B';

    // Check Down (↓)
    if (rMove + 1 < 8 && board[rMove + 1][cMove] === oppositeColor) {
        for (let i = rMove + 2; i < 8; ++i) {
            if (board[i][cMove] === '.') break;
            if (board[i][cMove] === color) return true;
        }
    }

    // Check Up (↑)
    if (rMove - 1 >= 0 && board[rMove - 1][cMove] === oppositeColor) {
        for (let i = rMove - 2; i >= 0; --i) {
            if (board[i][cMove] === '.') break;
            if (board[i][cMove] === color) return true;
        }
    }

    // Check Right (→)
    if (cMove + 1 < 8 && board[rMove][cMove + 1] === oppositeColor) {
        for (let i = cMove + 2; i < 8; ++i) {
            if (board[rMove][i] === '.') break;
            if (board[rMove][i] === color) return true;
        }
    }

    // Check Left (←)
    if (cMove - 1 >= 0 && board[rMove][cMove - 1] === oppositeColor) {
        for (let i = cMove - 2; i >= 0; --i) {
            if (board[rMove][i] === '.') break;
            if (board[rMove][i] === color) return true;
        }
    }

    // Check Bottom-Right (↘)
    if (rMove + 1 < 8 && cMove + 1 < 8 && board[rMove + 1][cMove + 1] === oppositeColor) {
        for (let i = rMove + 2, j = cMove + 2; i < 8 && j < 8; ++i, ++j) {
            if (board[i][j] === '.') break;
            if (board[i][j] === color) return true;
        }
    }

    // Check Top-Left (↖)
    if (rMove - 1 >= 0 && cMove - 1 >= 0 && board[rMove - 1][cMove - 1] === oppositeColor) {
        for (let i = rMove - 2, j = cMove - 2; i >= 0 && j >= 0; --i, --j) {
            if (board[i][j] === '.') break;
            if (board[i][j] === color) return true;
        }
    }

    // Check Top-Right (↗)
    if (rMove - 1 >= 0 && cMove + 1 < 8 && board[rMove - 1][cMove + 1] === oppositeColor) {
        for (let i = rMove - 2, j = cMove + 2; i >= 0 && j < 8; --i, ++j) {
            if (board[i][j] === '.') break;
            if (board[i][j] === color) return true;
        }
    }

    // Check Bottom-Left (↙)
    if (rMove + 1 < 8 && cMove - 1 >= 0 && board[rMove + 1][cMove - 1] === oppositeColor) {
        for (let i = rMove + 2, j = cMove - 2; i < 8 && j >= 0; ++i, --j) {
            if (board[i][j] === '.') break;
            if (board[i][j] === color) return true;
        }
    }

    // No valid line found
    return false;
}

Time Complexity: O(1)

Understanding the Problem

You're checking all 8 directions (up, down, left, right, and the 4 diagonals) starting from a given cell (rMove, cMove) on an 8×8 board. In each direction, you move along the line to:

  • Look for at least one opponent piece.
  • Then continue in the same direction until you either:
    • Hit your own piece (→ valid move),
    • Or hit an empty cell (→ invalid move).

Worst-Case Behavior

For each direction, in the worst case, you might have to scan up to 7 cells (the board is 8x8). But that only happens if the line goes all the way to the board’s edge.

Total Work per Call

  • There are 8 directions.
  • For each direction, you may scan up to O(7) = O(1) (since 7 is a constant).
  • So, the total work is:

Time Complexity=O(8×7)=O(56)=O(1)

Final Time Complexity: O(1) (constant time, since board size is fixed at 8×8)

Space Complexity: O(1)

Auxiliary Space Complexity

This refers to the extra space used by the algorithm excluding input.

What extra space does the function use?

  • A single character variable: oppositeColor
  • Some loop variables: i, j used in the for-loops

These are all primitive variables, and their space usage does not depend on input size.

Auxiliary Space Complexity: O(1)

Total Space Complexity

This includes input space + auxiliary space.

Input:

  • The board is passed by reference, not copied.
  • So we don’t count the full 8x8 board as part of the space complexity of the function itself.

Hence, the board’s size doesn’t impact the space consumed by this function.

Total Space Complexity: O(1)

Similar Problems

Now we have successfully tackled this problem, let's try these similar problems:-

1. Number of Islands

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

2. Word Search

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.