Java O(1) solution, easy to understand


  • 149
    B

    Initially, I had not read the Hint in the question and came up with an O(n) solution. After reading the extremely helpful hint; a much easier approach became apparent. The key observation is that in order to win Tic-Tac-Toe you must have the entire row or column. Thus, we don't need to keep track of an entire n^2 board. We only need to keep a count for each row and column. If at any time a row or column matches the size of the board then that player has won.

    To keep track of which player, I add one for Player1 and -1 for Player2. There are two additional variables to keep track of the count of the diagonals. Each time a player places a piece we just need to check the count of that row, column, diagonal and anti-diagonal.

    Also see a very similar answer that I believe had beaten me to the punch. We came up with our solutions independently but they are very similar in principle.
    Aeonaxx's soln

    public class TicTacToe {
    private int[] rows;
    private int[] cols;
    private int diagonal;
    private int antiDiagonal;
    
    /** Initialize your data structure here. */
    public TicTacToe(int n) {
        rows = new int[n];
        cols = new int[n];
    }
    
    /** Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins. */
    public int move(int row, int col, int player) {
        int toAdd = player == 1 ? 1 : -1;
        
        rows[row] += toAdd;
        cols[col] += toAdd;
        if (row == col)
        {
            diagonal += toAdd;
        }
        
        if (col == (cols.length - row - 1))
        {
            antiDiagonal += toAdd;
        }
        
        int size = rows.length;
        if (Math.abs(rows[row]) == size ||
            Math.abs(cols[col]) == size ||
            Math.abs(diagonal) == size  ||
            Math.abs(antiDiagonal) == size)
        {
            return player;
        }
        
        return 0;
    }
    

    }


  • 1
    B

    Anyone care to comment on the why the down vote?


  • 0

    Voted up! it looks neat.


  • 0

    You could just return player;, no? And then you could also combine the ifs.


  • 0
    B

    facepalm Yeah, I could just return player! I'm not sure why I didn't see that. I'll update. Thanks!


  • 0
    B

    Updated, thanks again for the suggestion.:)


  • 0
    L

    you might want to combine rows[row] == size || rows[row] == -size as Math.abs(rows[row]) == size. More concise, I guess.


  • 0
    B

    Yeah, that would clean it up a bit! I'll make the adjustment. Good suggestions, guys.


  • 0
    X

    very concise solution, thank you~


  • 0
    L
    This post is deleted!

  • 0
    B

    No worries larrywang2014, I came up with the solution on my own. Initially I had a different solution then I went back and read the hints. The hints are pretty straight forward and it becomes clear what you have to do. It is likely there will be many that have very similar or exact solutions. I'm not sure how else you can solve this one in O(1) without doing the above or something very similar.


  • 0
    B

    I added a link to that solution in the description above. Getting up-votes isn't nearly as important as learning something from others. It wasn't my intention to take attention away from anyone else's solution. :)


  • 0
    L

    Up-votes is nothing but encouragements/credits. The more encouragements/credits, the better solution will be possibly inspired. At least that works for me. As mentioned, do not get me wrong. It could be great minds think alike. Maybe I should not have mentioned the whole thing in the first place.


  • 0

    nice neat solution, my own solution uses some extra space to track if some certain rows, cols or diagonals is not winnable.


  • 4

    One more small clarity improvement (shout out to tushar roy N-queens video for this suggestion):

        if ((row - col) == 0) diag += toAdd;
        if ((row + col) == (n - 1)) antidiag += toAdd;
    

    On an n x n matrix, you can compute the (anti-)diagonal of a cell by using x + y or x - y. Since given y = mx + b, and m = {1, -1}, then y = {1, -1}x + b, thus y + {1, -1}x = b. If 'b' = 0 then it's the diagonal starting from the bottom, if 'b' = n then it's the diagonal starting from the top.

    And of course, the 'b' value creates an equivalency relation, which means you can generalize this property to partition all diagonals using the 'b' value. So two spots having the same b value are on the same diagonal.


  • 0
    H

    @bdwalker Thanks for sharing. It is easy to read and understand. I much say I don't think I am able to come up this logic in 1 hour.


  • 0
    R

    You do not implement the 1st rule:
    A move is guaranteed to be valid and is placed on an empty block.

    I think a int[][] board array is needed to keep track all the available blocks.


  • 0
    S

    @realjimmyli this means the input is always valid. We don't need to worry about checking the input.


  • 0
    L

    Nice, solution


  • -1

    This question is actually part of the Fastest Solution Ever of N Queen Problem, which uses bit mask to check the validation.

    This is my solution, time complexity O(1).

    public int move(int row, int col, int player) {
            // row: rows[row] |= 1 << col if ((rows[row] ^ K) == 0) win
            // col: cols[col] |= 1 << row if ((cols[col] ^ K) == 0) win
            // pie: if (row + col == n - 1) pie |= (1 << row) if ((pie ^ K) == 0) win
            // na: if (row == col) na |= (1 << row), if ((na ^ K) == 0) win
            int K = (2 << (n - 1)) - 1;
            if (player == 1) {
                rows[row] |= 1 << col;
                cols[col] |= 1 << row;
                if (row + col == n - 1) {
                    pie |= (1 << row);
                }
                if (row == col) {
                    na |= (1 << row);
                }
                
                if ((cols[col] ^ K) == 0 || (rows[row] ^ K) == 0 || (pie ^ K) == 0 || (na ^ K) == 0)
                    return 1;
            } else {
                rows2[row] |= 1 << col;
                cols2[col] |= 1 << row;
                if (row + col == n - 1) {
                    pie2 |= (1 << row);
                }
                if (row == col) {
                    na2 |= (1 << row);
                }
                
                if ((cols2[col] ^ K) == 0 || (rows2[row] ^ K) == 0 || (pie2 ^ K) == 0 || (na2 ^ K) == 0)
                    return 2;
            }
            return 0;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.