aboutsummaryrefslogtreecommitdiff
path: root/build_matrix_conditions.py
blob: 8f553609f0f661101fd170b969fec7e7b65f4ead (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
# 2392. Build a Matrix With Conditions
from collections import deque

"""
you are givne a positive integer 'k'. you are also given a 2d integer array
'rowConditions' of size 'n' where 'rowConditions[i] = [above_i, below_i]' and
a 2d integer array 'colConditions' of size 'm' where 'colConditions[i] =
[left_i, right_i]'. the two arrays contain integers from 1 to 'k'. you have
to build a 'k  k' matrix that contains each of the numbers from 1 to 'k'
exactly once. the remaining cells should satisfy the following conditions.
the number 'above_i' should appear in a row that is strictly above the row at
which the number 'below_i' appears for all 'i'. the number 'left_i' should
appear in a column that is strictly left of the column at which the number
'right_i' appears for all 'i'. return any matrix that satisfies these
conditions.
"""


class Solution(object):
    def buildMatrix(self, k, rowConditions, colConditions):
        """
        :type k: int
        :type rowConditions: List[List[int]]
        :type colConditions: List[List[int]]
        :rtype: List[List[int]]
        """

        def helper(a):
            next, in_deg = [set() for _ in range(k)], [0] * k
            dq, res = deque(), []
            a = set([tuple(i) for i in a])
            for i, j in a:
                next[i - 1].add(j - 1)
                in_deg[j - 1] += 1
            for i in range(k):
                if in_deg[i] == 0:
                    dq.append(i)
            while dq:
                curr = dq.popleft()
                res.append(curr)
                for candidate in next[curr]:
                    in_deg[candidate] -= 1
                    if in_deg[candidate] == 0:
                        dq.append(candidate)
            return res if len(res) == k else []

        a1, a2 = helper(rowConditions), helper(colConditions)
        if not a1 or not a2:
            return []
        ans = [[0] * k for _ in range(k)]
        for i in range(k):
            ans[a1.index(i)][a2.index(i)] = i + 1
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(
        obj.buildMatrix(
            k=3, rowConditions=[[1, 2], [3, 2]], colConditions=[[2, 1], [3, 2]]
        )
    )
    print(
        obj.buildMatrix(
            k=3, rowConditions=[[1, 2], [2, 3], [3, 1], [2, 3]], colConditions=[[2, 1]]
        )
    )