Crack Leetcode 1042: Flower Planting with No Adjacent
There is a way to make it easy.
Sometimes they make it look hard, while in fact, there’s always a way you can easily understand. Today, we’ll crack leetcode 1042 — Flower Planting with No Adjacent— together. Without further ado, let’s get started.
Problem Description:
Explain Problem Desc with Examples:
It may be easier to understand if we draw the examples out, like this:
Solution:
Explain the idea:
First, if we want to color a node, we need to know which color is still available, considering its all neighbors.
That makes me think, how do I know the colors of all its neighbors, or take one step back, how do I know all its neighbors?
Step#1. find all its neighbors:
The word “dictionary” immediately pop up. Dictionary is like this:
Let’s say, if garden1 has neighbors: garden2 and garden3, then we can put it like this: key1 = garden1, value x = [garden2, garden3].
Then later if we are coloring garden1, we can find it’s neighbors immediately.
Step#2. store corresponding colors:
Now we found the neighbors of a garden, but how do we know the color of its neighbors? So we need a storage. I used a list, and named it “res_colors”.
Since the color choice is [1,2,3,4], I initiated res_colors = [0 for i in range(n)], meaning no garden is colored yet.
Once a garden — say, garden k — is colored, we update the value to res_colors[k-1], as garden is named from 1, not 0.
For example, n=3: we initiate res_colors = [0, 0, 0]. Once we colored garden1 with color1, then we update: res_colors = [1, 0, 0].
Step#3. find the color choice available for a garden:
Now that we know the neighbors of a garden, the colors used in its neighbors, it’s easy to find out the color available for this garden: We just cross out all the colors used by neighbors from colorlist [1,2,3,4], and pick any color from the rest.
Summary: whole story illustrated:
Combining all the thoughts above, we get the whole story shown below:
Question: How to implement the “dictionary”:
An easy way is just use dict{} in python. Why not? The only thing to be careful about is when querying if a key is in the dict. You can say “if Garden1 in dict.keys( )”, but this query takes a long time, as in my practice on leetcode, when the test case n hits the upper limit 10⁴, it exceeds time limit. A better way is to write “if Garden1 in dict”. Same meaning, but faster.
There is another way to implement dictionary, just with a little twist. The twist is to use a list, instead of dict, to achieve the same result. Here I named it “dictList”, but it’s totally up to you.
Python Code:
Complexity Analysis:
I’ll try to give my answers on time and space complexity. Please comment if you have other opinions.
Time Complexity:
When making the neiDict, we need 2*E, where E is the number of paths, or in other word, edges.
Then we coloring, each path is visited twice, so we have 2*E here. For those gardens that have no neighbors, to color it we need 1 operation for each of them. Together we need 2*E+(num of gardens with no neighbor), and at most, it’s 2*E+N, where N is the number of gardens in total.
=> Time it takes in total is 2*E + (2*E+N) = 4*E+N
As in this problem, one garden has at most 3 neighbors. Therefore, E ≤ 3/2*N.
=> Time complexity is O(N).
Space Complexity:
The neiDict need 2*E space, where E is the number of paths, or in other word, edges.
When coloring, we have a constant array “colors” [1,2,3,4], and a neis array of at most 3 in length.
The storage list res_colors has a length of N.
=> auxiliary space comsumption = 2*E+N.
As in this problem, one garden has at most 3 neighbors. Therefore, E ≤ 3/2*N.
=> Auxiliary Space Complexity is O(N).
and since input space = E ,
=> Space Complexity is O(N).
The End:
Thanks for reading! Please check our articles more often, if you’d like to support our work — and we’ll see you in the next one!
