Your question is Tic Tac Toe Winner in O(n). Start with the requirements on the right.
Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.
Didi Labs wants to validate game states for a generalized Tic Tac Toe surface. Given an n x n board, determine whether X or O has won, whether the game is still pending, or whether the board is a draw.
A player wins when every cell in any complete row, column, or one of the two main diagonals contains that player's mark. The board is guaranteed to represent a valid game state, so both players cannot have winning lines simultaneously.
Implement tic_tac_toe_winner(board), where board is a square list of lists containing only "X", "O", and ".". Return exactly one of "X", "O", "Pending", or "Draw".
Use at most O(n) auxiliary space. The input board itself does not count toward auxiliary space.
def tic_tac_toe_winner(board):