Problem statement

https://leetcode.com/problems/remove-interval/

Solution

What we need to do is to traverse our intervals for for each of them find this interval with removed part. We need to carefully check cases.

  1. if A[1] < R[0] or A[0] > R[1], then we do not have intersection, remove original interval.
  2. if A[0] < R[0], it means that we have part of interval in the left side.
  3. if A[1] > R[1], then we have part of interval in the right side.

Complexity

Time complexity is O(n), space as well.

Code

class Solution:
    def removeInterval(self, intervals, R):
        def remove(A, R):
            if A[1] < R[0]: return [A]
            if A[0] > R[1]: return [A]
            ans = []
            if A[0] < R[0]: ans += [[A[0], R[0]]]
            if A[1] > R[1]: ans += [[R[1], A[1]]]
            return ans
            
        ans = []
        for I in intervals:
            ans += remove(I, R)
                
        return ans

1273 Delete Tree Nodes

[dfs, tree, recursion]

Solution

We need to pefrom dfs with 3 parameters in answer:

  1. Sum of all nodes in subtree with node as root.
  2. Number of nodes in this subtree.
  3. Number of nodes we need to delete.

Then, when we perform postorder dfs, if we have:

  1. sm + value[node] == 0, it means, that all this subtree need to be delted, so return (0, cnt + 1, cnt + 1), that is delet all nodes.
  2. If it is not equal, return (sm + value[node], cnt + 1, dl), where dl is sum of how many nodes we need to delete for each children.

Complexity

Time complexity is O(n), space complexity is O(h).

Code

class Solution:
    def deleteTreeNodes(self, n, parent, value):
        G = defaultdict(list)
        for i in range(n):
            G[parent[i]] += [i]
            
        def dfs(node):
            sm, cnt, dl = 0, 0, 0
            for child in G[node]:
                sm2, cnt2, dl2 = dfs(child)
                sm += sm2
                cnt += cnt2
                dl += dl2
            
            if sm + value[node] == 0:
                return (0, cnt + 1, cnt + 1)
            else:
                return (sm + value[node], cnt + 1, dl)
            
        return n - dfs(0)[2]