23.01.19 Today’s Leetcode

974. Subarray Sums Divisible by K (medium)

First try : Time Limit Exceeded (65/73)

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        n = len(nums)
        arr = [0] * n
        arr[0] = nums[0]
        for i in range(1, n):
            arr[i] = arr[i - 1] + nums[i]
        count = 0
        for i in range(n):
            if arr[i] % k == 0:
                count += 1
            for j in range(i + 1, n):
                p = arr[j] - arr[i]
                if p % k == 0:
                    count += 1
        return count
            

Solution with prefixSum and frequency table.
처음보는 솔루션이다. 신기방기. 근무시간에 이해하려고 노력해봐야겠다. 가장 이해가 안되는 부분은 res += remainderFrq[remainder] 이 부분이다. 왜냐하면 divisable by k subarray를 count하는게 목적인데 왜 하필 ` remainderFrq[remainder]` 를 더하는지 이해가 안된다. remainder 가 1이라면 나머지가 1인 subarray를 더하는 건데… 그래서 그런지 이부분이 이해가 안됨.

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        # frequency table to store the frequency of the remainder
        remainderFrq = defaultdict(int)
        # Empty sub array will have a sum of 0 and remainder of 0, thus the frequency of 0 is 1 before we go into the array
        remainderFrq[0] = 1
        
        res = prefixSum = 0
        for n in nums:
            # Adding n to the prefixSum, so we have the prefixSum up to the ith position.
            prefixSum += n
            # Get the remainder of the current prefixSum.
            remainder = prefixSum % k
            # We need to increase the result before update the frequency table.
            # Because we are counting how many previous prefixSum have the same remainder.
            res += remainderFrq[remainder]
            # Update the frequency table.
            remainderFrq[remainder] += 1
        return res

226. Invert Binary Tree (easy)

Solution with DFS

# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(node):
            if node == None:
                return
            left = node.left
            right = node.right
            node.left = right
            node.right = left
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return root