Find Winner on a Tic Tac Toe Game Leetcode Solution

Difficulty Level Easy
Frequently asked in Amazon Apple Facebook Zoho
algorithms Array coding Interview interviewprep LeetCode LeetCodeSolutionsViews 3714

The problem Find Winner on a Tic Tac Toe Game Leetcode Solution asks us to find out the winner of a tic tac toe game. The problem provides us with an array or vector of moves made by the players. We need to go through the moves and judge who wins the game. The outcome of the game can be won, draw, or pending. In cases, when any one of them wins the game, we return A or B. But before judging the game, we must be aware of the rules of this specific version of Tic Tac Toe.

  • Players can only make moves on squares that have not been utilized already.
  • The first player A always places “X” characters, while the second player B always places “O” characters.
  • “X” and “O” characters are always placed into empty squares. One should never use squares that have already been utilized.
  • The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
  • The game also ends if all squares are non-empty. In some cases, both of them do not win and end up in a draw.
  • No more moves can be played if the game is over. If there are some moves left, the verdict is “Pending”.
  • Player “A” makes the first move and then alternate turns are used by both the players.

Let’s take a look at a few examples.

moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
"A"

Find Winner on a Tic Tac Toe Game Leetcode Solution

Explanation: As shown above in the figure, the player with the “X” wins the game. A always starts the game, thus the winner is also “A”.

Approach for Find Winner on a Tic Tac Toe Game Leetcode Solution

The problem is to find the final verdict of the tic tac toe game after some moves. It’s a standard game, so we need to just simulate the process. We also need to perform the steps in the same order as given in the input. One way is to create a grid of 3×3 and then simulate the same process. But instead of doing that, we keep track of moves made by both the players using arrays. We use 4 different arrays for both the players, 2 for moves made by them regarding each row and column. For each move, we increment the values stored in these arrays. Once the values become equal to 3. We know that 3 moves are made either horizontally or vertically.

For diagonals, we simply use 4 variables similar to arrays. When any of the value becomes equal to 3. We return the name accordingly. But if we do not reach a verdict until all the moves have been made. Then we return a verdict of the draw if all the squares on the grid are occupied else pending is returned.

Code for Find Winner on a Tic Tac Toe Game Leetcode Solution

C++ code

#include <bits/stdc++.h>
using namespace std;

string tictactoe(vector<vector<int>>& moves) {
    int aRow[3] = {0}, bRow[3] = {0}, aCol[3] = {0}, bCol[3] = {0};
    int aDiagonal1 = 0, bDiagonal1 = 0, aDiagonal2 = 0, bDiagonal2 = 0;
    int n = moves.size();
    for (int i = 0; i < n; i++) {
        int r = moves[i][0], c = moves[i][1];
        if (i % 2 == 1) {
            if (++bRow[r] == 3 || ++bCol[c] == 3 || (r == c && ++bDiagonal1 == 3) || (r + c == 2 && ++bDiagonal2 == 3)) return "B";
        }else {
            if (++aRow[r] == 3 || ++aCol[c] == 3 || (r == c && ++aDiagonal1 == 3) || (r + c == 2 && ++aDiagonal2 == 3)) return "A";
        }
    }
    return n == 9 ? "Draw" : "Pending";
}

int main(){
    vector<vector<int>> moves = {{0,0}, {2,0}, {1,1}, {2,1}, {2,2}};
    cout<<tictactoe(moves);
}

A

Java code

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static String tictactoe(int[][] moves) {
        int[] aRow = new int[3];
        int[] aCol = new int[3];
        int[] bRow = new int[3];
        int[] bCol = new int[3];
        int aDiagonal1 = 0, bDiagonal1 = 0, aDiagonal2 = 0, bDiagonal2 = 0;
        int n = moves.length;
        for (int i = 0; i < n; i++) {
            int r = moves[i][0], c = moves[i][1];
            if (i % 2 == 1) {
                if (++bRow[r] == 3 || ++bCol[c] == 3 || (r == c && ++bDiagonal1 == 3) || (r + c == 2 && ++bDiagonal2 == 3)) return "B";
            }else {
                if (++aRow[r] == 3 || ++aCol[c] == 3 || (r == c && ++aDiagonal1 == 3) || (r + c == 2 && ++aDiagonal2 == 3)) return "A";
            }
        }
        return n == 9 ? "Draw" : "Pending";        
    }
    
  public static void main (String[] args) throws java.lang.Exception {
    int[][] moves = {{0,0}, {2,0}, {1,1}, {2,1}, {2,2}};
    	System.out.println(tictactoe(moves));
  }
}
A

Complexity Analysis

Time Complexity

O(N), where N is the number of moves sent as input to the function.

Space Complexity

O(R+C), because we create 4 arrays of size equal to the row and column of the grid in tic tac toe game.

Translate »