Java O(1) solution, easy to understand - Leetcode Discuss
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
Read full article from Java O(1) solution, easy to understand - Leetcode Discuss
No comments:
Post a Comment