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:

(photo taken from leetcode: https://leetcode.com/problems/flower-planting-with-no-adjacent/)

Explain Problem Desc with Examples:

(photo taken from leetcode:https://leetcode.com/problems/flower-planting-with-no-adjacent/)

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!

Life is beautiful!

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store