Problem statement

https://leetcode.com/problems/minimize-malware-spread/

Solution

The idea is the following: given graph, we need to:

  1. Find all connected components and for each component we need to know size of it.
  2. For each component we need to know how many infected nodes inside: if it is more than one, we are not intersted in this component.
  3. Among all components, where we have exaclty one infected node, we need to choose one with the smallest tuple (-size, index of node).
  4. In the end, if we did not found any component with only one infected node, we retrun index of smallest node, in the opposite case we return what we found.

Dictionary comps are connections node -> index of component.

Counter sizes are connections index of component -> size of it.

Counter comps_count are connections index of component -> number of infected nodes.

Complexity

Time complexity is O(n + E) to traverse all graph, space complexity is O(n).

Code

class Solution:
    def minMalwareSpread(self, graph, initial):
        n, V, comps, cnt = len(graph), set(), {}, 0
        
        def dfs(node, i):
            comps[node] = i
            V.add(node)
            for neib in range(n):
                if graph[node][neib] == 0 or neib in V: continue
                dfs(neib, i)
        
        for i in range(n):
            if i not in V:
                dfs(i, cnt)
                cnt += 1
                
        sizes = Counter(comps.values())
                
        comps_count = Counter()
        for node in initial:
            comps_count[comps[node]] += 1
            
        ans = (n + 1, float("inf"))
                
        for node in initial:
            c = comps[node]
            if comps_count[c] != 1: continue
            ans = min(ans, (-sizes[c], node))
            
        return ans[1] if ans[1] != float("inf") else min(initial)

1622 Fancy Sequence

[math, design]

Solution

The trick is here to keep so-called lazy updates: we will keep 3 pieces of information:

  1. self.A is multiplication coefficient
  2. self.B is summation coefficient
  3. self.T is array,

such that we have nums = self.A*self.T + self.B.

  1. To get addAll, we just need to increment self.B.
  2. To get multAll, we juet need to multiply both self.A and self.B.
  3. To get getIndex, evaluate self.T[idx]*self.A + self.B
  4. Finally, to get append, when we add val, we need to solve equation self.T[n] = (val - self.B) * self.A, so we need to solve this equation moduly M.

Complexity

Time complexities of addAll, multAll and getIndex is O(1). Time complexity of append is O(log M) to perform inverse of element. Space complexity is O(n) for full data structure.

Code

class Fancy:
    def __init__(self):
        self.T, self.A, self.B = [], 1, 0
        self.M = 10**9 + 7

    def append(self, val):
        self.T += [(val - self.B)*pow(self.A, -1, self.M) % self.M]

    def addAll(self, inc):
        self.B = (self.B + inc) % self.M
        
    def multAll(self, m):
        self.A = (self.A * m) % self.M
        self.B = (self.B * m) % self.M

    def getIndex(self, idx):
        return (self.T[idx]*self.A + self.B) % self.M if idx < len(self.T) else -1