[LeetCode] 781. Rabbits in Forest

 Problem : https://leetcode.com/problems/rabbits-in-forest/

Remember the last rabbit answered the same values. Then count rabbits must be in different colors.

class Solution:
    def numRabbits(self, answers: List[int]) -> int:
        
        total = 0
        seen = defaultdict(int)
        
        for n in answers:
            if n == 0:
                # encounter a single rabbit of this color
                total += 1
            else:
                if seen[n+1]:
                    # encounter rabbit with same color
                    seen[n+1] -= 1
                else:
                    # encounter rabbit with different color
                    seen[n+1] += n
                    total += n+1
                    
        return total

Another math solution:

Firstly count number of rabbits anwsered the same values. For example, M rabbits answered N. Then there must be M // (N+1) group of rabbits with same color. Each group has N+1 rabbits. Additionally, there must be another group of N+1 rabbits if M % (N+1) > 0.

class Solution:
    def numRabbits(self, answers: List[int]) -> int:
        
        total = 0
        count = Counter(answers)
        
        for n, m in count.items():
            total += m // (n+1) * (n+1)
            total += n + 1 if m % (n+1) else 0
                    
        return total

[LeetCode] 261. Graph Valid Tree

 Problem: https://leetcode.com/problems/graph-valid-tree/

Use DFS to locate if all nodes are connected and no loop exists.

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        
        seen = [False] * n
        visited = 0
        stack = [0]
        
        graph = defaultdict(set)
        
        for a, b in edges:
            graph[a].add(b)
            graph[b].add(a)
        
        while stack:
            a = stack.pop()
            
            if seen[a]:
                return False
            
            visited += 1
            seen[a] = True
            
            for b in graph[a]:
                stack.append(b)
                graph[b].remove(a)
            
        
        return visited == n

[LeetCode] 186. Reverse Words in a String II

 Problem : https://leetcode.com/problems/reverse-words-in-a-string-ii/

This problem requests reverse words in place.

So we reverse the entire list first, then reverse every words again.

class Solution:
    def reverseWords(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
    
        def reverse(left, right):
            while left < right:
                s[left], s[right] = s[right], s[left]
                left += 1
                right -= 1
        
        
        reverse(0, len(s) - 1)
        
        left = 0
        for right in range(len(s)):
            if s[right] == ' ':
                reverse(left, right -1)
                left = right + 1
        
        # revese the last word
        reverse(left, len(s) -1)

[LeetCode] 170. Two Sum III - Data structure design

 Problem : https://leetcode.com/problems/two-sum-iii-data-structure-design/

M = Value - N.   Use hash table to find whether M exists when given Value and N.

class TwoSum:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.seen = {}
        self.memo = set()
        
    def add(self, number: int) -> None:
        """
        Add the number to an internal data structure..
        """
        
        if number in self.seen:
            self.seen[number] += 1
        else:
            self.seen[number] = 1
        
    def find(self, value: int) -> bool:
        """
        Find if there exists any pair of numbers which sum is equal to the value.
        """
        
        if value in self.memo: return True

        for n in self.seen.keys():
            if value - n == n:
                if self.seen.get(n, 0) >= 2: 
                    self.memo.add(value)
                    return True
            elif self.seen.get(value - n, 0) > 0: 
                self.memo.add(value)
                return True
        
        return False

[LeetCode] 159. Longest Substring with At Most Two Distinct Characters

 Problem :  https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/

This is a classic sliding window problem.

class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        seen = defaultdict(int)
        distinct = 0
        result = 0
        
        right = 0
        
        for left in range(len(s)):
            while right < len(s) and distinct <= 2:
                seen[s[right]] += 1
                
                if seen[s[right]] == 1:
                    distinct += 1
                
                right += 1
                
                if distinct <= 2:
                    result = max(result, right - left)
             
            seen[s[left]] -= 1
            if seen[s[left]] == 0:
                distinct -= 1
                
        return result

[LeetCode] 158. Read N Characters Given Read4 II - Call multiple times

 Problem : https://leetcode.com/problems/read-n-characters-given-read4-ii-call-multiple-times/

The difference to problem 157 is the read() can be called multiple times. So we need to remember the reading position since last time the API be called.

Use queue as intermediate buffer to simplify the reading logic.

# The read4 API is already defined for you.
# def read4(buf4: List[str]) -> int:

class Solution:
    def __init__(self):
        self.queue = deque()
        
    def read(self, buf: List[str], n: int) -> int:
        copied = 0
        buf4 = [''] * 4
        
        while copied < n:
            while self.queue:
                buf[copied] = self.queue.popleft()
                copied += 1
                
                if copied == n:
                    return copied
            
            read = read4(buf4)
            if read == 0:
                return copied
            
            for i in range(read):
                self.queue.append(buf4[i])
        
        return copied

[LeetCode] 157. Read N Characters Given Read4

 Problem : https://leetcode.com/problems/read-n-characters-given-read4/

Use intermediate buffer to read 4 bytes every time.

"""
The read4 API is already defined for you.

    @param buf4, a list of characters
    @return an integer
    def read4(buf4):

# Below is an example of how the read4 API can be called.
file = File("abcdefghijk") # File is "abcdefghijk", initially file pointer (fp) points to 'a'
buf4 = [' '] * 4 # Create buffer with enough space to store characters
read4(buf4) # read4 returns 4. Now buf = ['a','b','c','d'], fp points to 'e'
read4(buf4) # read4 returns 4. Now buf = ['e','f','g','h'], fp points to 'i'
read4(buf4) # read4 returns 3. Now buf = ['i','j','k',...], fp points to end of file
"""

class Solution:
    def read(self, buf, n):
        """
        :type buf: Destination buffer (List[str])
        :type n: Number of characters to read (int)
        :rtype: The number of actual characters read (int)
        """
        
        copied = 0
        read = 0
        buf4 = [''] * 4
        
        while copied < n:   
            read = read4(buf4)
            if read > 0:
                for i in range(min(read, n-copied)):
                    buf[copied] = buf4[i]
                    copied += 1
            else:
                break
        
        return copied

[LeetCode] 156. Binary Tree Upside Down

 Problem : https://leetcode.com/problems/binary-tree-upside-down/

Although it says every node has either 0 or 2 children in the given example. The input tree may only has left sub-tree.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:
        
        def helper(node):
            if node and node.left:
                lt = node.left
                node.left = None
                lt = helper(lt)
                
                rt = node.right
                node.right = None
                rt = helper(rt)
                   
                np = lt
                while np.right:
                    np = np.right
                
                np.left = rt
                np.right = node
                   
                return lt
                
            else:
                return node
            
        
        return helper(root)

[LeetCode] 323. Number of Connected Components in an Undirected Graph

 Problem : https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/

Use DFS to find all connected nodes.

A stack based DFS solution:

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        
        graph = defaultdict(list)
        
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
                    
        result = 0
        seen = set()
        stack = []
        
        for i in range(n):
            if i not in seen:
                result += 1
                
                seen.add(i)
                stack.append(i)
                
                while stack:
                    a = stack.pop()
                    
                    for b in graph[a]:
                        if b not in seen:
                            seen.add(b)
                            stack.append(b)
        
        return result