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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Build a Matrix With Conditions

Number: 2472

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given a positive integer k and two lists of order conditions (one for rows and one for columns), build a k x k matrix where each of the numbers from 1 to k appears exactly once (all other cells remain 0). The rowConditions list specifies that one number must appear in a row strictly above another number, and the colConditions list specifies a similar constraint for columns. Return any valid matrix that satisfies these conditions, or return an empty matrix if none exists.

Key Insights

  • The order constraints for rows and columns can be modeled as separate directed graphs.
  • Topological sorting (using Kahn’s algorithm) is used to determine a valid ordering that obeys the given conditions.
  • Two independent topological sorts are performed: one for row ordering and one for column ordering.
  • Once valid orderings are obtained, use their positions to place each number in the matrix, where the row index is given by the row order and the column index by the column order.
  • If either ordering fails (i.e. there is a cycle), then no valid matrix exists and an empty matrix should be returned.

Space and Time Complexity

Time Complexity: O(k + R + C) where R is the number of rowConditions and C is the number of colConditions.
Space Complexity: O(k + R + C) for storing graphs, in-degrees, and the ordering arrays.

Solution

We first build two directed graphs for the row and column conditions. For each graph, we perform a topological sort using Kahn's algorithm, which involves:

  • Building an adjacency list and maintaining an in-degree count for each node (number).
  • Using a queue to process nodes whose in-degree is zero. If the sorted order does not include all nodes, then a cycle exists and no valid ordering is possible.
    After obtaining valid orderings, we create a mapping from number to its position in the ordering for both rows and columns. Then, we iterate through each number and place it in the matrix at the position determined by these mappings.
    The final matrix is returned if both orderings are valid; otherwise, an empty matrix is returned.

Code Solutions

from collections import deque

def topological_sort(k, conditions):
    # Build graph and in-degree mapping for nodes from 1 to k
    graph = {i: [] for i in range(1, k+1)}
    in_degree = {i: 0 for i in range(1, k+1)}
    
    # Add edges for each condition [u, v] meaning u should come before v
    for u, v in conditions:
        graph[u].append(v)
        in_degree[v] += 1
    
    # Initialize queue with all numbers that have zero in-degree
    queue = deque([node for node in range(1, k+1) if in_degree[node] == 0])
    order = []
    
    while queue:
        node = queue.popleft()
        order.append(node)
        for neigh in graph[node]:
            in_degree[neigh] -= 1
            if in_degree[neigh] == 0:
                queue.append(neigh)
    
    # If order size is less than k, a valid order is not possible
    return order if len(order) == k else []

def buildMatrix(k, rowConditions, colConditions):
    row_order = topological_sort(k, rowConditions)
    col_order = topological_sort(k, colConditions)
    
    # If either ordering is invalid, return empty matrix
    if not row_order or not col_order:
        return []
    
    # Create positions mapping for row and column orders
    pos_in_row = {num: idx for idx, num in enumerate(row_order)}
    pos_in_col = {num: idx for idx, num in enumerate(col_order)}
    
    # Create the k x k matrix initialized with zeros
    matrix = [[0] * k for _ in range(k)]
    
    # Place each number in the corresponding row and column
    for num in range(1, k+1):
        matrix[pos_in_row[num]][pos_in_col[num]] = num
        
    return matrix

# Example usage:
k = 3
rowConditions = [[1,2],[3,2]]
colConditions = [[2,1],[3,2]]
print(buildMatrix(k, rowConditions, colConditions))
← Back to All Questions