# 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 color**1**, 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 “

**”. Same meaning, but faster.**

*if Garden1 in dict*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!