Leetcode 1042: Flower Planting With No Adjacent

https://leetcode.com/problems/flower-planting-with-no-adjacent/description/

Note:

• 1 <= N <= 10000
• 0 <= paths.size <= 20000
• No garden has 4 or more paths coming into or leaving it.
• It is guaranteed an answer exists.

Notes:

This question seems not easy, but actually it can be solved in a greedy way.

The first step is to build a graph with adjacent elements. Then is the key: for each element i or the ith garden, we need to check its neighbors (less than 4). If they have been planned with flowers, we cannot plan that kind of flower in ith. Otherwise, we can.

See the code below:

class Solution {
public:
    vector<int> gardenNoAdj(int N, vector<vector<int>>& paths) {
        vector<int> res(N, 0);
        vector<vector<int>> g(N);
        for(auto &a : paths){
            g[a[0]-1].push_back(a[1]-1);
            g[a[1]-1].push_back(a[0]-1);
        }
        for(int i=0; i<N; ++i){
            vector<int> used(5, 0);
            for(auto &a : g[i]) used[res[a]] = 1;//if used, label as 1;
            for(int fl = 1; fl <5; ++fl) {
                if(!used[fl]) {res[i] = fl; break;}
            }
        }
        return res;
    }
};