1042. Flower Planting With No Adjacent

Problem

You have n gardens, labeled from 1 to n, and an array paths where paths[i] = [xi, yi] describes a bidirectional path between garden xi to garden yi. In each garden, you want to plant one of 4 types of flowers.

All gardens have at most 3 paths coming into or leaving it.

Your task is to choose a flower type for each garden such that, for any two gardens connected by a path, they have different types of flowers.

Return *any such a choice as an array answer, where answer[i] is the type of flower planted in the (i+1)th garden. The flower types are denoted 1, 2, 3, or 4. It is guaranteed an answer exists.*

  Example 1:

Input: n = 3, paths = [[1,2],[2,3],[3,1]]
Output: [1,2,3]
Explanation:
Gardens 1 and 2 have different types.
Gardens 2 and 3 have different types.
Gardens 3 and 1 have different types.
Hence, [1,2,3] is a valid answer. Other valid answers include [1,2,4], [1,4,2], and [3,2,1].

Example 2:

Input: n = 4, paths = [[1,2],[3,4]]
Output: [1,2,1,2]

Example 3:

Input: n = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
Output: [1,2,3,4]

  Constraints:

• 1 <= n <= 104

• 0 <= paths.length <= 2 * 104

• paths[i].length == 2

• 1 <= xi, yi <= n

• xi != yi

• Every garden has at most 3 paths coming into or leaving it.

Solution

/**
 * @param {number} n
 * @param {number[][]} paths
 * @return {number[]}
 */
var gardenNoAdj = function(n, paths) {
    var pathMap = Array(n).fill(0).map(() => ({}));
    for (var i = 0; i < paths.length; i++) {
        pathMap[paths[i][0] - 1][paths[i][1] - 1] = true;
        pathMap[paths[i][1] - 1][paths[i][0] - 1] = true;
    }
    var possibleMap = Array(n).fill(0).map(() => [1,1,1,1]);
    var result = Array(n).fill(0);
    for (var j = 0; j < n; j++) {
        var type = possibleMap[j].findIndex(item => item === 1);
        var others = Object.keys(pathMap[j]);
        for (var k = 0; k < others.length; k++) {
            possibleMap[others[k]][type] = 0;
        }
        result[j] = type + 1;
    }
    return result;
};

Explain:

In the beginning, every garden can plant 4 types of flower.

We go through the gardens, pick one flower type from all passible choices for that garden.

And remove this kind of flower type from the possible types of all neighbor gardens.

In the end, you will have (one of) the result.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).