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)

Network Delay Time - Python Solution

 There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

 

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2




Output: 2

class Solution(object):
    def networkDelayTime(self, times, N, K):
        graph = collections.defaultdict(list)
        for u, v, w in times:
            graph[u].append((v, w))

        dist = {node: float('inf') for node in range(1, N+1)}
        seen = [False] * (N+1)
        dist[K] = 0

        while True:
            cand_node = -1
            cand_dist = float('inf')
            for i in range(1, N+1):
                if not seen[i] and dist[i] < cand_dist:
                    cand_dist = dist[i]
                    cand_node = i

            if cand_node < 0: break
            seen[cand_node] = True
            for nei, d in graph[cand_node]:
                dist[nei] = min(dist[nei], dist[cand_node] + d)

        ans = max(dist.values())
        return ans if ans < float('inf') else -1

 

String Transforms Into Another String - Python Solution

 Given two strings str1 and str2 of the same length, determine whether you can transform str1 into str2 by doing zero or more conversions.

In one conversion you can convert all occurrences of one character in str1 to any other lowercase English character.

Return true if and only if you can transform str1 into str2.

 

Example 1:

Input: str1 = "aabcc", str2 = "ccdee"
Output: true
Explanation: Convert 'c' to 'e' then 'b' to 'd' then 'a' to 'c'. Note that the order of conversions matter.

Example 2:

Input: str1 = "leetcode", str2 = "codeleet"
Output: false
Explanation: There is no way to transform str1 to str2.

class Solution:
    def canConvert(self, str1: str, str2: str) -> bool:
        hashmap = {}
        hashset = set()
        
        for i in range(len(str1)):
            hashset.add(str2[i])
            if str1[i] in hashmap and hashmap[str1[i]] != str2[i]:
                return False
            hashmap[str1[i]] = str2[i]
        
        if str1 != str2 and len(hashset) == 26 and len(hashmap) == 26:
            return False
        return True
        
        

O(n) and O(n)

 

Maximal Square Python Solution

 Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example:

Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if matrix is None or len(matrix) < 1:
            return 0
        
        rows = len(matrix)
        cols = len(matrix[0])
        
        dp = [[0]*(cols+1) for _ in range(rows+1)]
        max_side = 0
        
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] == '1':
                    dp[r+1][c+1] = min(dp[r][c], dp[r+1][c], dp[r][c+1]) + 1 # Be careful of the indexing since dp grid has additional row and column
                    max_side = max(max_side, dp[r+1][c+1])
                
        return max_side * max_side

            

Expressive Words - Python Solution

 Sometimes people repeat letters to represent extra feeling, such as "hello" -> "heeellooo", "hi" -> "hiiii".  In these strings like "heeellooo", we have groups of adjacent letters that are all the same:  "h", "eee", "ll", "ooo".

For some given string S, a query word is stretchy if it can be made to be equal to S by any number of applications of the following extension operation: choose a group consisting of characters c, and add some number of characters c to the group so that the size of the group is 3 or more.

For example, starting with "hello", we could do an extension on the group "o" to get "hellooo", but we cannot get "helloo" since the group "oo" has size less than 3.  Also, we could do another extension like "ll" -> "lllll" to get "helllllooo".  If S = "helllllooo", then the query word "hello" would be stretchy because of these two extension operations: query = "hello" -> "hellooo" -> "helllllooo" = S.

Given a list of query words, return the number of words that are stretchy. 

 

Example:
Input: 
S = "heeellooo"
words = ["hello", "hi", "helo"]
Output: 1
Explanation: 
We can extend "e" and "o" in the word "hello" to get "heeellooo".
We can't extend "helo" to get "heeellooo" because the group "ll" is not size 3 or more.

 

Constraints:

• 0 <= len(S) <= 100.
• 0 <= len(words) <= 100.
• 0 <= len(words[i]) <= 100.
• S and all words in words consist only of lowercase letters

class Solution(object):
    def expressiveWords(self, S, words):
        return sum(self.check(S,W) for W in words)
    def check(self,S,W):
        i,j,n,m = 0,0,len(S),len(W)
        for i in range(len(S)):
            if j<m and S[i] == W[j]: j+=1
            elif S[i-1:i+2] != S[i]*3 != S[i-2:i+1]: return False
        return j == m
    

O(noOfwords * len(largest word) SC: O(1)