Algorithm Challenges #2

Leetcode problems

1. Build a Matrix With Conditions

link: https://leetcode.com/problems/build-a-matrix-with-conditions/description

---

This problem states that we must find a matrix that meets the row and column conditions. Each condition contains the order of numbers that should appear from top to bottom and from left to right. For example, if one of the row conditions is [2, 3], 2 should appear upper than 3. If one of the column conditions is [2, 3], 2 should appear on the left of 3.

Even though it is a k-by-k matrix, let’s consider it one dimension. We can solve the problem only with the row conditions first.

No matter how many conditions are provided, we only have k numbers. Matrix also has k rows. This means we can ensure that each number is placed in each row. So, we don’t need to consider the case of two numbers located in the same row.

We need to solve the order in which the numbers are placed. This problem has now been changed to a graph problem. A similar situation is finding the order of classes I should take when the prerequisites of each class are provided. To solve this problem, we can use the topology sort algorithm to get orders from graphs.

One thing we need to check here is the case that has the cycle. 1 → 2 → 3 → 1 is one case with the cycle because 3 should be placed above 1, but 1 should be above 3, too. This cannot happen! If this case is found, we should return an empty list as the answer.

So, we can use a color mechanism to check if the current number is in progress or completed. Let’s assume that color 0 means ready state. If we start finding orders of nodes with connected edges, then let’s change the color to 1. If all connected edges are well ordered, add the current node to the array and change the color to 2.

While processing each number, we can check the current color to see if the number is in progress. If the color of the number is 1, we face the cycle! In this case, we can return None to detect the cycle case.

Now, we can get the order of k numbers that meet the row conditions. With the same logic, we also need to get the order of k numbers that meet the column conditions. After that, we can just place the number i in the position of row order[i] and column order[i].

Here’s the code.

• Time complexity is O(K+E), where E is the number of edges in the graph. But it excludes the initialization of the matrix for the answer.

• Space complexity is O(K+E), where E is the number of edges in the graph.

 class Solution:
    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:
        def topsort(g, node, colors, ret):
            if colors[node] == 1:
                return False
            if colors[node] == 2:
                return True
            colors[node] = 1
            for ne in g[node]:
                if not topsort(g, ne, colors, ret):
                    return False
            colors[node] = 2
            ret.append(node)
            return True
            
        def make_graph(arr, k):
            g = defaultdict(list)
            s = set(list(range(1,k+1)))
            for p, q in arr:
                g[p].append(q)
            ret = []
            colors = [0 for _ in range(k+1)]
            for e in s:
                if not topsort(g, e, colors, ret):
                    return None
            ret.reverse()
            return { v: i for i, v in enumerate(ret) }
        row = make_graph(rowConditions, k)
        col = make_graph(colConditions, k)
        
        if not row or not col:
            return []
            
        ans = [[0 for _ in range(k) ] for _ in range(k)]
        for i in range(1, k+1):
            ans[row[i]][col[i]] = i

        return ans
        

2. Find a Valid Matrix Given Row and Column Sums

Link: https://leetcode.com/problems/find-valid-matrix-given-row-and-column-sums/description

---

The problem states that we should fill the matrix that meets the row and column conditions. Row and column conditions contain the sum of each row and column.

Here’s an example. Let’s say the sum of the first column is 5, and the sum of the second row is 8. Then, you can fill in the number like this to meet those two conditions.

If you think about this problem for a while, you will easily find that you can fill the number greedily. It’s because the overall sum is always the same and there is no other constraints to distribute the number except for the sum.

This means we can iterate the rows and distribute the number row[i] greedily to columns. For example, if row[0] is 10, we can fill the column[0] to 10 if possible. If column[0] is smaller than 10, we can fill the rest of the number to column[1].

Here’s the simple code.

• Time complexity is O(N*M), where N is the number of rows, and M is the number of columns.

• Space complexity is O(N*M) because of the list for the answer.

class Solution:
    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:
        n = len(rowSum)
        m = len(colSum)
        ans = [[0 for _ in range(m)] for _ in range(n)]

        curr_idx = 0
        for i in range(n):
            value = rowSum[i]
            while curr_idx < m and value > 0:
                can = min(colSum[curr_idx], value)
                colSum[curr_idx] -= can
                value -= can
                ans[i][curr_idx] = can
                if colSum[curr_idx] == 0:
                    curr_idx += 1
        return ans