algoadvance

Leetcode 794. Valid Tic

Problem Statement:

Implement a function to check if a given Tic-Tac-Toe board state is valid. The board is a 3x3 array where each element is either 'X', 'O', or ' '. A valid Tic-Tac-Toe board must satisfy the following conditions:

  1. The number of ‘X’s cannot be less than the number of ‘O’s and cannot exceed the number of ‘O’s by more than 1.
  2. A player wins if they have three of their characters in a row, column, or diagonal.
  3. If a player wins, the game ends and no more moves are possible.

Write a function bool validTicTacToe(vector<string>& board) to return whether the given board state is valid.

Clarifying Questions:

  1. Will the board always be a valid 3x3 grid?
    • Yes, the board will always be a valid 3x3 grid.
  2. Should the function account for invalid characters in the grid?
    • No, you can assume the board contains only ‘X’, ‘O’, and spaces.
  3. Can there be multiple winners?
    • No, there can be at most one winner.

Strategy:

  1. Count the number of ‘X’ and ‘O’:
    • Ensure the count of ‘X’ is either equal to or exactly one more than the count of ‘O’.
  2. Check for winning conditions:
    • If ‘X’ wins, ensure there is exactly one more ‘X’ than ‘O’.
    • If ‘O’ wins, ensure there are exactly the same number of ‘X’ and ‘O’.
  3. Define win conditions:
    • Check all rows, columns, and diagonals for a winning condition.
  4. Handle invalid cases:
    • Return false if any of the above conditions are violated.

Code:

#include <vector>
#include <string>

using namespace std;

bool isWinner(const vector<string>& board, char player) {
    // Check rows and columns
    for (int i = 0; i < 3; ++i) {
        if (board[i][0] == player && board[i][1] == player && board[i][2] == player) return true;
        if (board[0][i] == player && board[1][i] == player && board[2][i] == player) return true;
    }

    // Check diagonals
    if (board[0][0] == player && board[1][1] == player && board[2][2] == player) return true;
    if (board[0][2] == player && board[1][1] == player && board[2][0] == player) return true;

    return false;
}

bool validTicTacToe(vector<string>& board) {
    int countX = 0, countO = 0;
    
    // Count X's and O's
    for (const auto& row : board) {
        for (const auto& cell : row) {
            if (cell == 'X') ++countX;
            if (cell == 'O') ++countO;
        }
    }

    // If the number of 'O's is greater than 'X's, or 'X' is greater by more than 1, return false
    if (countO > countX || countX > countO + 1) return false;

    bool xWins = isWinner(board, 'X');
    bool oWins = isWinner(board, 'O');

    // If 'X' wins, then there should be exactly one more 'X' than 'O'
    if (xWins && countX != countO + 1) return false;

    // If 'O' wins, then the number of 'X' and 'O' should be equal
    if (oWins && countX != countO) return false;

    // If both 'X' and 'O' win, it's invalid
    if (xWins && oWins) return false;

    return true;
}

Time Complexity:

Thus, the overall time complexity is (O(1)).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI