Find Winner on a Tic Tac Toe Game Solution in Java

Explore Solutions in Other Languages

Problem Description

Ah, Tic Tac Toe! The game that has brought families together and torn them apart over the ages. You know, the one where you can either be a strategic genius or just a lucky guesser. The task at hand is to determine the winner of a Tic Tac Toe game based on the moves made by two players, A and B.

Imagine this: you’re at a family gathering, and your cousin thinks they can outsmart you in Tic Tac Toe. You both take turns, and suddenly, it’s like a scene from a suspense thriller. Will you win, or will you be left staring at a grid of Xs and Os, wondering where it all went wrong?

In this problem, you’ll be given a list of moves made by both players. Your job is to figure out if player A wins, player B wins, or if the game is still pending or has ended in a draw. Simple, right? Well, let’s see how you can code this in Java!

Code Solution


class Solution {
  public String tictactoe(int[][] moves) {
    int[][] row = new int[2][3];
    int[][] col = new int[2][3];
    int[] diag1 = new int[2];
    int[] diag2 = new int[2];

    for (int i = 0; i < moves.length; ++i) {
      final int r = moves[i][0];
      final int c = moves[i][1];
      final int j = i & 1;
      if (++row[j][r] == 3 || ++col[j][c] == 3 || r == c && ++diag1[j] == 3 ||
          r + c == 2 && ++diag2[j] == 3)
        return j == 0 ? "A" : "B";
    }

    return moves.length == 9 ? "Draw" : "Pending";
  }
}

Approach

The approach taken in this solution is quite straightforward. We maintain counters for rows, columns, and diagonals for both players. As each move is made, we increment the respective counters. If any counter reaches 3, we declare that player as the winner. If all moves are made and no winner is found, we check if the game is a draw or still pending.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(1)
Space Complexity	O(1)

Real-World Example

Think of Tic Tac Toe as a mini version of life’s decisions. You make a move, and then your opponent counters. Sometimes you win, sometimes you lose, and sometimes you just end up in a stalemate. Just like in life, where you might think you’ve outsmarted your opponent, only to realize they were one step ahead all along.

In this problem, the moves represent decisions made in a game of strategy. The solution helps you determine the outcome based on those decisions, much like evaluating the results of your life choices.