Java | TC: O(N^2) | SC: O(1) | Space Optimized (NO extra arrays used to store the scores)
Space Optimized solution (True constant space solution)\njava\n/**\n * Space Optimized solution (True constant space solution)\n *\n * Calculate net score of ea
**Space Optimized solution (True constant space solution)**\n```java\n/**\n * Space Optimized solution (True constant space solution)\n *\n * Calculate net score of each row, column and diagonal. Here the score of each\n * row, column and diagonal is stored in an int. For Player1 add 1 and for\n * Player2 add -1.\n *\n * Time Complexity:\n * Every non-diagonal element is visited 2 times. --> N^2-(2N-1)\n * Center element is visited 4 times --> 1\n * Remaining diagonal elements are visited 3 times. --> 2N-1-1 = 2N-2\n * Total Time Complexity = O( 2*(N^2-(2N-1)) + 3*(2N-2) + 4*(1) )\n *                       = O(2*N^2 + 2*N)\n *                       = O(N^2)\n *\n * Space Complexity: O(1) --> True constant space solution. No arrays are used\n * to store the scores of each row and column.\n *\n * N = Board Size (Number of Rows or Number of Columns)\n */\nclass Solution {\n    public boolean validTicTacToe(String[] board) {\n        if (board == null || board.length == 0) {\n            return false;\n        }\n\n        int n = board.length;\n        int diag1 = 0;\n        int diag2 = 0;\n        int turnsDiff = 0;\n        boolean xWin = false;\n        boolean oWin = false;\n        char c;\n\n        for (int i = 0; i < n; i++) { // ith row OR ith column\n            int row = 0;\n            int col = 0;\n            for (int j = 0; j < n; j++) {\n                c = board[i].charAt(j);\n                if (c == \'X\') {\n                    row++;\n                    turnsDiff++;\n                } else if (c == \'O\') {\n                    row--;\n                    turnsDiff--;\n                }\n                c = board[j].charAt(i);\n                if (c == \'X\') {\n                    col++;\n                } else if (c == \'O\') {\n                    col--;\n                }\n            }\n\n            c = board[i].charAt(i);\n            if (c == \'X\') {\n                diag1++;\n            } else if (c == \'O\') {\n                diag1--;\n            }\n            c = board[i].charAt(n - 1 - i);\n            if (c == \'X\') {\n                diag2++;\n            } else if (c == \'O\') {\n                diag2--;\n            }\n\n            if (row == n || col == n || diag1 == n || diag2 == n) {\n                if (oWin) {\n                    return false;\n                }\n                xWin = true;\n            }\n            if (row == -n || col == -n || diag1 == -n || diag2 == -n) {\n                if (xWin) {\n                    return false;\n                }\n                oWin = true;\n            }\n        }\n\n        if (turnsDiff < 0 || turnsDiff > 1) {\n            return false;\n        }\n        /**\n         * X Wins only after odd number of turns, thus the diff will be 1.\n         *\n         * O wins only after even number of turns, thus the diff will be 0.\n         */\n        if ((turnsDiff == 0 && xWin) || (turnsDiff == 1 && oWin)) {\n            return false;\n        }\n        return true;\n    }\n}\n```\n\n---\n**Uses array for rows and columns to store the score of each row and column**\n\n```java\n/**\n * Calculate net score of each row, column and diagonal.\n *\n * Not Space Optimized. Here the score of each row, column and diagonal is\n * stored in an int array. For Player1 add 1 and for Player2 add -1.\n *\n * Time Complexity: O(N^2) or O(1)\n *\n * Space Complexity: O(N) or O(1)\n *\n * N = Board Size (Number of Rows or Number of Columns)\n */\nclass Solution {\n    public boolean validTicTacToe(String[] board) {\n        if (board == null || board.length == 0) {\n            return false;\n        }\n\n        int n = board.length;\n        int[] rows = new int[n];\n        int[] cols = new int[n];\n        int diag1 = 0;\n        int diag2 = 0;\n        int turnsDiff = 0;\n        boolean xWin = false;\n        boolean oWin = false;\n\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < n; j++) {\n                char c = board[i].charAt(j);\n                if (c == \' \') {\n                    continue;\n                }\n                int val = c == \'X\' ? 1 : -1;\n                turnsDiff += val;\n                rows[i] += val;\n                cols[j] += val;\n                if (i == j) {\n                    diag1 += val;\n                }\n                if (i + j == n - 1) {\n                    diag2 += val;\n                }\n                if (rows[i] == n || cols[j] == n || diag1 == n || diag2 == n) {\n                    if (oWin) {\n                        return false;\n                    }\n                    xWin = true;\n                }\n                if (rows[i] == -n || cols[j] == -n || diag1 == -n || diag2 == -n) {\n                    if (xWin) {\n                        return false;\n                    }\n                    oWin = true;\n                }\n            }\n        }\n\n        if (turnsDiff < 0 || turnsDiff > 1) {\n            return false;\n        }\n        if ((turnsDiff == 0 && xWin) || (turnsDiff == 1 && oWin)) {\n            return false;\n        }\n        return true;\n    }\n}\n```\n\n---\n\nSolutions to other Tic-Tac-Toe questions on LeetCode:\n- [348. Design Tic-Tac-Toe](https://leetcode.com/problems/design-tic-tac-toe/discuss/1517545/Java-or-TC:-O(1)-or-SC:-O(N)-or-Space-Optimized-solution)\n- [1275. Find Winner on a Tic Tac Toe Game](https://leetcode.com/problems/find-winner-on-a-tic-tac-toe-game/discuss/1517563/Java-or-TC:-O(M)-or-SC:-O(1)-or-Space-Optimized-solution)\n
['Array', 'String', 'Java']