Find Winner on a Tic Tac Toe Game

 Tic-tac-toe is played by two players A and B on a 3 x 3 grid. The rules of Tic-Tac-Toe are:

• Players take turns placing characters into empty squares ' '.
• The first player A always places 'X' characters, while the second player B always places 'O' characters.
• 'X' and 'O' characters are always placed into empty squares, never on filled ones.
• The game ends when there are three of the same (non-empty) character filling any row, column, or diagonal.
• The game also ends if all squares are non-empty.
• No more moves can be played if the game is over.

Given a 2D integer array moves where moves[i] = [rowi, coli] indicates that the ith move will be played on grid[rowi][coli]. return the winner of the game if it exists (A or B). In case the game ends in a draw return "Draw". If there are still movements to play return "Pending".

You can assume that moves is valid (i.e., it follows the rules of Tic-Tac-Toe), the grid is initially empty, and A will play first.

 

Example 1:

Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"
Explanation: A wins, they always play first.

Example 2:

Input: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
Output: "B"
Explanation: B wins.

Example 3:

Input: moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
Output: "Draw"
Explanation: The game ends in a draw since there are no moves to make.

 

Constraints:

• 1 <= moves.length <= 9
• moves[i].length == 2
• 0 <= rowi, coli <= 2
• There are no repeated elements on moves.
• moves follow the rules of tic tac toe.

class Solution {
    public String tictactoe(int[][] moves) {
       int n = 3;
       int[] rows = new int[n];
       int[] cols = new int[n];
       int player = 1;
       int diag = 0;
        int antidiag = 0;
        
        for(int[] move:moves){
            int row = move[0];
            int col = move[1];
            
            rows[row] += player;
            cols[col] += player;
            
            if(row == col){
                diag+= player;
            }
            
            if(row + col == n-1){
                antidiag += player;
            }
            
            if(Math.abs(diag) == n || Math.abs(antidiag) == n || Math.abs(rows[row]) == n || Math.abs(cols[col]) == n){
                return player == 1 ? "A":"B";
            }
            player *= -1;
        }
        return moves.length == n * n ? "Draw" : "Pending";
    }
}

Time complexity: $O(m)$
For every move, we update the value for a row, column, diagonal, and anti-diagonal. Each update takes constant time. We also check if any of these lines satisfies the winning condition which also takes constant time.
Space complexity: $O(n)$
We use two arrays of size n to record the value for each row and column, and two integers of constant space to record to value for diagonal and anti-diagonal.

Find N Unique Integers Sum up to Zero

 Find N Unique Integers Sum up to Zero

Given an integer n, return any array containing n unique integers such that they add up to 0.

 

Example 1:

Input: n = 5
Output: [-7,-1,1,3,4]
Explanation: These arrays also are accepted [-5,-1,1,2,3] , [-3,-1,2,-2,4].

Example 2:

Input: n = 3
Output: [-1,0,1]

Example 3:

Input: n = 1
Output: [0]

 

Constraints:

• 1 <= n <= 1000

class Solution {
    public int[] sumZero(int n) {
        if(n == 0){
            return new int[] {0};
        }
        int value = n;
        int [] uniqueIntegers = new int[n];
        for(int i=0,j=n-1;i<j;i++,j--){
            uniqueIntegers[i]= value;
            uniqueIntegers[j] = value * -1;
            value--;
        }
       return uniqueIntegers;
    }
}

TC : O(N) SC: O(N)

Sign of the Product of an Array

 Sign of the Product of an Array

There is a function signFunc(x) that returns:

• 1 if x is positive.
• -1 if x is negative.
• 0 if x is equal to 0.

You are given an integer array nums. Let product be the product of all values in the array nums.

Return signFunc(product).

 

Example 1:

Input: nums = [-1,-2,-3,-4,3,2,1]
Output: 1
Explanation: The product of all values in the array is 144, and signFunc(144) = 1

Example 2:

Input: nums = [1,5,0,2,-3]
Output: 0
Explanation: The product of all values in the array is 0, and signFunc(0) = 0

Example 3:

Input: nums = [-1,1,-1,1,-1]
Output: -1
Explanation: The product of all values in the array is -1, and signFunc(-1) = -1

 

Constraints:

• 1 <= nums.length <= 1000
• -100 <= nums[i] <= 100

Solution 1:

class Solution {
    public int arraySign(int[] nums) {
        int sign = 1;
        for(int num:nums){
            if(num == 0){
                return 0;
            }
            if(num < 0){
                sign *= -1;
            }
        }
        return sign;
    }
}

Solution 2:

class Solution {
    public int arraySign(int[] nums) {
        int countNeg = 0;
        for(int num:nums){
            if(num == 0){
                return 0;
            }
            if(num < 0){
                countNeg++;
            }
        }
        return countNeg % 2 == 0 ? 1 : -1;
    }
}

TC: O(n) SC: O(1)