2392. Build a Matrix With Conditions

[mah-shamim]

You are given a positive integer k. You are also given:

• a 2D integer array rowConditions of size n where rowConditions[i] = [abovei, belowi], and
• a 2D integer array colConditions of size m where colConditions[i] = [lefti, righti].

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 the following conditions:

• The number abovei should appear in a row that is strictly above the row at which the number belowi appears for all i from 0 to n - 1.
• The number lefti should appear in a column that is strictly left of the column at which the number righti appears for all i from 0 to m - 1.

Return any matrix that satisfies the conditions. If no answer exists, return an empty matrix.

Example 1:

• Input: k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]]
• Output: [[3,0,0],[0,0,1],[0,2,0]]
• Explanation: The diagram above shows a valid example of a matrix that satisfies all the conditions.
  • The row conditions are the following:
    • Number 1 is in row 1, and number 2 is in row 2, so 1 is above 2 in the matrix.
    • Number 3 is in row 0, and number 2 is in row 2, so 3 is above 2 in the matrix.
  • The column conditions are the following:
    • Number 2 is in column 1, and number 1 is in column 2, so 2 is left of 1 in the matrix.
    • Number 3 is in column 0, and number 2 is in column 1, so 3 is left of 2 in the matrix.
  • Note that there may be multiple correct answers.

Example 2:

• Input: k = 3, rowConditions = [[1,2],[2,3],[3,1],[2,3]], colConditions = [[2,1]]
• Output: []
• Explanation: From the first two conditions, 3 has to be below 1 but the third conditions needs 3 to be above 1 to be satisfied.
  No matrix can satisfy all the conditions, so we return the empty matrix.

Constraints:

• 2 <= k <= 400
• 1 <= rowConditions.length, colConditions.length <= 104
• rowConditions[i].length == colConditions[i].length == 2
• 1 <= abovei, belowi, lefti, righti <= k
• abovei != belowi
• lefti != righti

Hint:

1. Can you think of the problem in terms of graphs?
2. What algorithm allows you to find the order of nodes in a graph?

[mah-shamim]

To solve this problem, we can follow these steps:

1. Topological Sorting: We'll perform topological sorting on the row conditions and column conditions separately to determine the order in which elements should appear in rows and columns.
2. Constructing the Matrix: Using the sorted order from the topological sort, we will place the elements in the ( k \times k ) matrix accordingly.
3. Validation: If there is a cycle detected during topological sorting, it means the conditions are contradictory, and no valid matrix can be formed. In this case, we return an empty matrix.

Let's implement this solution in PHP: 2392. Build a Matrix With Conditions

<?PHP

/**
 * @param Integer $k
 * @param Integer[][] $rowConditions
 * @param Integer[][] $colConditions
 * @return Integer[][]
 */
function buildMatrix($k, $rowConditions, $colConditions) {
    // Topologically sort the row and column conditions
    $rowOrder = $this->topologicalSort($rowConditions, $k);
    $colOrder = $this->topologicalSort($colConditions, $k);

    if (empty($rowOrder) || empty($colOrder)) {
        return []; // No valid matrix possible
    }

    // Create a mapping from value to its index in the sorted order
    $rowPosition = array_flip($rowOrder);
    $colPosition = array_flip($colOrder);

    // Initialize the matrix
    $matrix = array_fill(0, $k, array_fill(0, $k, 0));

    // Place the elements in the matrix based on the sorted order
    for ($i = 1; $i <= $k; $i++) {
        $row = $rowPosition[$i];
        $col = $colPosition[$i];
        $matrix[$row][$col] = $i;
    }

    return $matrix;
}

// Helper function to perform topological sort
function topologicalSort($conditions, $k) {
    $graph = array_fill(1, $k, []);
    $inDegree = array_fill(1, $k, 0);
    
    foreach ($conditions as $condition) {
        $graph[$condition[0]][] = $condition[1];
        $inDegree[$condition[1]]++;
    }
    
    $queue = [];
    for ($i = 1; $i <= $k; $i++) {
        if ($inDegree[$i] == 0) {
            $queue[] = $i;
        }
    }
    
    $sortedOrder = [];
    while (!empty($queue)) {
        $node = array_shift($queue);
        $sortedOrder[] = $node;
        foreach ($graph[$node] as $neighbor) {
            $inDegree[$neighbor]--;
            if ($inDegree[$neighbor] == 0) {
                $queue[] = $neighbor;
            }
        }
    }
    
    if (count($sortedOrder) == $k) {
        return $sortedOrder;
    }
    
    return []; // Cycle detected
}

// Example usage:
$k = 3;
$rowConditions = [[1, 2], [3, 2]];
$colConditions = [[2, 1], [3, 2]];
$result = buildMatrix($k, $rowConditions, $colConditions);

foreach ($result as $row) {
    echo implode(" ", $row) . "\n";
}
?>

Explanation:

1. Topological Sorting:

   • We build a graph and calculate in-degrees for each node based on the given conditions.
   • Using a queue, we perform a topological sort and track the sorted order of elements.
   • If we successfully sort ( k ) elements, we return the sorted order. Otherwise, we return an empty array indicating a cycle (contradictory conditions).

2. Constructing the Matrix:

   • We use the sorted order from topological sorting to determine the row and column positions of each element.
   • We map each element to its respective position and place it in the ( k \times k ) matrix.

3. Validation:

   • If either row order or column order is empty, it means a cycle was detected, and we return an empty matrix.

The provided code effectively handles the given constraints and ensures that the matrix satisfies the specified conditions.