algoadvance

Leetcode 1275. Find Winner on a Tic Tac Toe Game

Problem Statement

You’re given a list of moves for a Tic Tac Toe game on a 3 x 3 board. The game consists of two players, A and B, who take turns making moves. The moves are represented by a list of tuples. Player A always goes first.

You need to determine the result of the game (who won or if it ended in a draw). The possible outcomes are:

The moves list is given in the format [[row, col], ...].

Clarifying Questions

  1. Input Constraints: Are there always at least one move in the input list?
  2. Move Validity: Can we assume that all moves are valid and within the bounds of the board?
  3. Order of Moves: Is it guaranteed that Player A and Player B alternate moves correctly starting with Player A?
  4. Output Format: Should the output be a single string indicating the outcome?

Assuming answers to the above questions:

  1. Yes
  2. Yes
  3. Yes
  4. Yes

Strategy

  1. Initialize a Tic Tac Toe Board: Use a 2D vector to represent the 3x3 board.
  2. Simulate Game Moves: Iterate over the given list of moves to populate the board.
  3. Check for Win Condition: After each move, check if the current player has won by examining rows, columns, and diagonals.
  4. Determine Outcome:
    • If any player wins, return the respective player (“A” or “B”).
    • If all moves are exhausted and no winner is found, return “Draw”.
    • If there are moves left but no winner yet, return “Pending”.

Code

Here is the implementation in C++:

#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    string tictactoe(vector<vector<int>>& moves) {
        vector<vector<char>> board(3, vector<char>(3, ' '));
        int n = moves.size();
        
        // Populate the board
        for (int i = 0; i < n; ++i) {
            int row = moves[i][0];
            int col = moves[i][1];
            board[row][col] = (i % 2 == 0) ? 'A' : 'B';
        }
        
        // Check for win condition
        for (int i = 0; i < 3; ++i) {
            // Check rows
            if (board[i][0] != ' ' && board[i][0] == board[i][1] && board[i][1] == board[i][2])
                return string(1, board[i][0]);

            // Check columns
            if (board[0][i] != ' ' && board[0][i] == board[1][i] && board[1][i] == board[2][i])
                return string(1, board[0][i]);
        }

        // Check diagonals
        if (board[0][0] != ' ' && board[0][0] == board[1][1] && board[1][1] == board[2][2])
            return string(1, board[0][0]);

        if (board[0][2] != ' ' && board[0][2] == board[1][1] && board[1][1] == board[2][0])
            return string(1, board[0][2]);
        
        // If all moves are made but no winner
        if (n == 9)
            return "Draw";
        
        // If not all cells are filled
        return "Pending";
    }
};

Time Complexity

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