Build a Matrix With Conditions

Problem Statement

In this task, you are provided with:

1. An integer k, representing the size of a square matrix (k x k).
2. Two sets of conditions in the form of 2D arrays: rowConditions and colConditions.

Each entry in rowConditions is a pair [abovei, belowi], indicating that the number abovei should be placed in a row above the row where belowi is located. Similarly, each entry in colConditions is a pair [lefti, righti], specifying that the number lefti should be located in a column to the left of the column where righti is found.

Your goal is to fill out the k x k matrix following these rules:

• Every number from 1 to k is used exactly once in the matrix.
• Any unfilled cells in the matrix should be assigned the value 0.

The matrix must adhere to all the specific rowConditions and colConditions. If a valid arrangement exists, return the matrix; otherwise, if no such arrangement is possible, you should return an empty matrix.

Examples

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

Approach and Intuition

The problem can be perceived as finding a valid topological sort for both rows and columns given the constraints, and then mapping these sorted orders back to a matrix format. Here’s how you can think about the process:

1. Model Row and Column Constraints as Graphs:

   • For rowConditions, create an adjacency list where each directed edge u -> v indicates u is to be above v.
   • Similarly, for colConditions, form another adjacency structure where u -> v now signifies u is to the left of v.

2. Topological Sorting:

   • With the built graph structures, perform a topological sort. If the sort is successful, it provides a valid order.
   • If a cycle exists in any graph (detected during topological sort), it implies conflicting conditions, thus making it impossible to build a valid matrix, in which case return an empty matrix.

3. Mapping Numbers to the Matrix:

   • Using the orders obtained from the topological sorting (for both rows and columns), start placing numbers at their appropriate row and column indices.
   • Fill non-assigned cells of the matrix with 0.

4. Edge Cases:

   • Handle cases where multiple valid matrices might exist. Any valid matrix as per the conditions should be acceptable.
   • Ensure the solution is efficient to handle the upper constraint limits, considering k could be as large as 400 and conditions can be up to 20,000.

This overall approach leverages graph theory concepts, especially topological sorting, to decide the relative positioning of numbers in the matrix, making the problem much more structured and manageable.

Solutions

class Solution {
public:
    vector<vector<int>> generateMatrix(int size, vector<vector<int>>& rowReqs, vector<vector<int>>& colReqs) {
        vector<int> rowOrder = topologicalSort(rowReqs, size);
        vector<int> columnOrder = topologicalSort(colReqs, size);
    
        if (rowOrder.empty() || columnOrder.empty()) return {};
    
        vector<vector<int>> result(size, vector<int>(size, 0));
        for (int row = 0; row < size; row++) {
            for (int col = 0; col < size; col++) {
                if (rowOrder[row] == columnOrder[col]) {
                    result[row][col] = rowOrder[row];
                }
            }
        }
        return result;
    }
    
private:
    vector<int> topologicalSort(vector<vector<int>>& relations, int nodes) {
        vector<vector<int>> adjacencyList(nodes + 1);
        vector<int> inDegree(nodes + 1), sortedResult;
        for (auto relation : relations) {
            adjacencyList[relation[0]].push_back(relation[1]);
            inDegree[relation[1]]++;
        }
        queue<int> zeroInDegree;
        for (int node = 1; node <= nodes; node++) {
            if (inDegree[node] == 0) zeroInDegree.push(node);
        }
        while (!zeroInDegree.empty()) {
            int current = zeroInDegree.front();
            zeroInDegree.pop();
            sortedResult.push_back(current);
            nodes--;
            for (int next : adjacencyList[current]) {
                if (--inDegree[next] == 0) zeroInDegree.push(next);
            }
        }
        if (nodes != 0) return {};
        return sortedResult;
    }
};