LeetCode 2392: Build a Matrix With Conditions

link

The row indices of the numbers $1, 2, 3, \ldots, k$ must be a permutation of row indices $0, 1, 2, \ldots, k-1$ . Say we only have rowConditions — no conditions on the columns. We can build a directed graph with vertex set $\{ x : 1 \le x \le k \}$ and edge set $\left\{ (u, v) : u \ \text{is-strictly-above-of} \ v \right\}$ . Then, from a topological ordering of $V$ , we can find a valid permuation of row indices $\mathcal{R} = \left\{ (x: \text{row}) \mid 1 \le x \le k, 0 \le \text{row} \le k-1 \right\}$ . Note, $\text{is-strictly-above-of}$ is a transitive relation but it is neither reflexive nor symmetric. Consequently, any cycle, including self-loop, signals absence of a solution.

Likewise, with only colConditions, from a similar directed graph with the same $V$ , but with $E = \left\{ (u, v) : u \ \text{is-strictly-left-of} \ v \right\}$ , we can first find a topological ordering of $V$ and from that we can find a valid permutation of column indices $\mathcal{C} = \left\{ (x: \text{col}) \mid 1 \le x \le k, 0 \le \text{col} \le k-1 \right\}$ .

Insight: Row placement is independent from column placement.

Now, in the matrix, we put $x$ in the cell $\langle \text{row}, \text{col} \rangle = \langle \mathcal{R}[x], \mathcal{C}[x] \rangle$ .

DFS

Time and space complexity comes from building the graph. Vertex set, $V$ , has size $k$ and edge set, $E$ , has size $\mathcal{ O }\left( \max{ \left( |\text{rowConditions}|, |\text{colConditions}| \right) } \right)$ . Time and space complexity: $\mathcal{O}( |V| + |E| )$ .

class Solution:
    def build_graph(self, k, edges) -> Dict[int, Set[int]]:
        # V: {1, 2, ..., k}
        # E: {(u, v) : u is-strictly-above-of v}
        # E: {(u, v) : u is-strictly-left-of  v}
        adj_list = { u : set() for u in range(1, k+1) }
        for u, v in edges:
            adj_list[u].add(v)
        return adj_list

    def explore(self, u, adj_list, visited, onstack, post) -> bool:
        visited.add(u)

        onstack.add(u)

        for v in adj_list[u]:
            if (v in visited) and (v in onstack):
                # Cycle
                return True
            if (v in visited):
                continue
            if self.explore(v, adj_list, visited, onstack, post):
                return True
        
        post.append(u)
        onstack.remove(u)
        return False

    def dfs(self, adj_list) -> Tuple[bool, List[int]]:
        visited, onstack = set(), set()
        post = []
        for u in adj_list:
            if u in visited:
                continue
            if self.explore(u, adj_list, visited, onstack, post):
                return True, []
        return False, post[::-1]

    def sorted_topo(self, adj_list) -> Dict[int, int]:
        has_cycle, topo = self.dfs( adj_list )
        if has_cycle:
            return {}
        return {x : coord for coord, x in enumerate(topo)}

    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:
        row_adj_list = self.build_graph(k, rowConditions)
        row_sorted = self.sorted_topo(row_adj_list)
        if not row_sorted:
            return []
        col_adj_list = self.build_graph(k, colConditions)
        col_sorted = self.sorted_topo(col_adj_list)
        if not col_sorted:
            return []
        matrix = [ [0]*k for _ in range(k) ]
        for x in range(1, k+1):
            r, c = row_sorted[x], col_sorted[x]
            matrix[r][c] = x
        return matrix

In-degree

class Solution:
    def build_graph(self, k, edges) -> Dict[int, Set[int]]:
        # V: {1, 2, ..., k}
        # E: {(u, v) : u is-strictly-above-of v}
        # E: {(u, v) : u is-strictly-left-of  v}
        adj_list = { u : set() for u in range(1, k+1) }
        for u, v in edges:
            adj_list[u].add(v)
        return adj_list

    def build_indegree_map(self, adj_list) -> Dict[int, int]:
        inmap = {u : 0 for u in adj_list}
        for u in adj_list:
            for v in adj_list[u]:
                inmap[v] += 1
        return inmap

    def sorted_topo(self, adj_list) -> Dict[int, int]:
        inmap = self.build_indegree_map( adj_list )
        curr_sources = [u for u, d in inmap.items() if d == 0]
        topo = []
        while curr_sources:
            topo.extend(curr_sources)
            new_sources = []
            for u in curr_sources:
                for v in adj_list[u]:
                    inmap[v] -= 1
                    if inmap[v] == 0:
                        new_sources.append(v)
            curr_sources = new_sources

        if len(topo) != len(adj_list):
            # cycle
            return {}
        return {x : coord for coord, x in enumerate(topo)}

    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:
        row_adj_list = self.build_graph(k, rowConditions)
        row_sorted = self.sorted_topo(row_adj_list)
        if not row_sorted:
            return []
        col_adj_list = self.build_graph(k, colConditions)
        col_sorted = self.sorted_topo(col_adj_list)
        if not col_sorted:
            return []
        matrix = [ [0]*k for _ in range(k) ]
        for x in range(1, k+1):
            r, c = row_sorted[x], col_sorted[x]
            matrix[r][c] = x
        return matrix

unreasonably effective