We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Build a Matrix With Conditions

Difficulty: Hard

Problem Description

You are given 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 x k matrix that contains each of the numbers from 1 to k exactly once. The remaining cells should have the value 0. The matrix should also satisfy certain conditions related to the positions of the numbers in rows and columns. Return any matrix that satisfies the conditions. If no answer exists, return an empty matrix.

Key Insights

  • The problem requires constructing a matrix with specific order constraints for both rows and columns.
  • This can be modeled as a directed graph where each number has dependencies based on the row and column conditions.
  • Topological sorting can be used to determine the valid ordering of numbers to satisfy the given constraints.
  • If a cycle is detected in the graph, it indicates that no valid matrix can be formed.

Space and Time Complexity

Time Complexity: O(n + m + k) where n is the number of row conditions, m is the number of column conditions, and k is the size of the matrix. Space Complexity: O(k + n + m) for storing the graph and the in-degree array.

Solution

The solution involves the following steps:

  1. Construct a directed graph based on the row and column conditions, where an edge from a to b indicates that a must appear before b.
  2. Perform a topological sort on this graph using Kahn's algorithm or depth-first search to determine a valid order of numbers.
  3. Populate the k x k matrix based on the valid order obtained from the topological sort, ensuring that the numbers are placed according to their respective indices.
  4. If a valid topological order cannot be obtained (i.e., a cycle exists), return an empty matrix.

Code Solutions

from collections import defaultdict, deque

def buildMatrix(k, rowConditions, colConditions):
    def topological_sort(conditions):
        graph = defaultdict(list)
        in_degree = [0] * (k + 1)
        
        for a, b in conditions:
            graph[a].append(b)
            in_degree[b] += 1
        
        queue = deque()
        for i in range(1, k + 1):
            if in_degree[i] == 0:
                queue.append(i)
        
        sorted_order = []
        while queue:
            node = queue.popleft()
            sorted_order.append(node)
            for neighbor in graph[node]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)
        
        return sorted_order if len(sorted_order) == k else []
    
    row_order = topological_sort(rowConditions)
    col_order = topological_sort(colConditions)
    
    if not row_order or not col_order:
        return []
    
    matrix = [[0] * k for _ in range(k)]
    for i in range(k):
        matrix[row_order[i] - 1][col_order[i] - 1] = row_order[i]
    
    return matrix
← Back to All Questions