7/8 lines O(1) Java/Python


  • 7

    Java

    public class TicTacToe {
    
        public TicTacToe(int n) {
            count = new int[6*n][3];
        }
        
        public int move(int row, int col, int player) {
            int n = count.length / 6;
            for (int x : new int[]{row, n+col, 2*n+row+col, 5*n+row-col})
                if (++count[x][player] == n)
                    return player;
            return 0;
        }
        
        int[][] count;
    }
    

    Python

    class TicTacToe(object):
        def __init__(self, n):
            count = collections.Counter()
            def move(row, col, player):
                for i, x in enumerate((row, col, row+col, row-col)):
                    count[i, x, player] += 1
                    if count[i, x, player] == n:
                        return player
                return 0
            self.move = move

  • 1
    C

    @StefanPochmann

    Brilliant solution!
    However I feel some space could be saved by choosing initial size of count matrix to be 5n * 3 instead of 6n * 3, since 2n+row+col should never exceed 4n-2.

    Let me know if there is some other reason for choosing initial size to be 6n * 3 instead of 5n * 3.

    Modified solution should look like below:

    public class TicTacToe {

    public TicTacToe(int n) {
        count = new int[5*n][3];
    }
    
    public int move(int row, int col, int player) {
        int n = count.length / 5;
        for (int x : new int[]{row, n+col, 2*n+row+col, 4*n+row-col})
            if (++count[x][player] == n)
                return player;
        return 0;
    }
    
    int[][] count;
    

    }


  • 1

    @coderatleet Because 4n+row-col can, thanks to subtracting col, get smaller than 4n-2 and thus overlap the range used by 2n+row+col. But looks like the counts in the overlap range can only go up to n-1, never n, so it seems ok.


  • 0
    C

    @StefanPochmann
    Thanks for the explanation. It makes sense. It also explains why modified solution above works despite overlap in the range.

    With solution above, there will be overlap for range 3n+1...4n-2.

    And still it is unaffected by the overlap due to following reasons:

    1. Counts in the overlap range can only go up to n-1.
    2. Cells of our interest 3n-1 (antidiagonal) and 4n (diagonal) lie outside of this range.

Log in to reply
 

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