# Java Two Solutions: String-Based(Slow) and Array-Based(fast)

• The solution in the editorial article does something essentially like counting `000` runs.

The two solutions I used can both be extended to solve a broader category of problems: paragraph splitting, or run counting. Although for this particular problem, they are not the optimal solutions, since they do use extra space.

In this problem, we just have to go 1pass, and find the all the consecutive 0 runs, then process each run's length to get the number of flowers such a run can support:

1. for `0` and `00`, supports no flowers. for `000` and `0000`, we subtract 2 from the `len`, and we can calculate the number of flowers supported:
``````len - 2 <= 0 -> no flowers
len - 2 == 1 -> 1 flower
len - 2 == 2 -> 1 flower
len - 2 == 3 -> 2 flowers
len - 2 == 4 -> 2 flowers
...
``````
1. for a zero at the head or end of the whole bed, we add one to `len` since they are like spots where we have an open end, which is just a `0` on the other side. For example: `[0]01` and `10[0]01` supports the same number of flowers and the bracketed `0` are actually equivalent.

In the code below I do not try to reduce the verbosity but feel free to do so if you are into that.

String-based version (not fast, 28ms@20170715)

``````public class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
StringBuilder sb = new StringBuilder();
for (int i : flowerbed) sb.append(i);
String str = sb.toString();
String[] runs = str.split("1");
if (flowerbed[0] == 0) runs[0] += "0";
if (flowerbed[flowerbed.length - 1] == 0) runs[runs.length - 1] += "0";
int[] runLens = new int[runs.length];
for (int i = 0; i < runs.length; i++) {
int len = runs[i].length();
if (len == 0) continue;
runLens[i] = len - 2 <= 0 ? 0 : ((len - 2 - 1) / 2 + 1) ;
}
int sum = 0;
for (int i : runLens) sum += i;
return n <= sum;
}
}
``````

Array-based version (same speed as the editorial solution (without the premature exit test) 12ms@20170715)

``````public class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int sum = 0, run = 0, len = flowerbed.length;
boolean inRun = true;
for (int i = 0; i < len; i++) {
if (inRun && flowerbed[i] == 1) {
sum += run - 2 <= 0 ? 0 : ((run - 2 - 1) / 2 + 1);
run = 0;
} else if (!inRun && flowerbed[i] == 0) {
run++;
inRun = true;
} else if (inRun && flowerbed[i] == 0) {
run++;
if (i == 0) run++;
if (i == len - 1) {
run++;
sum += run - 2 <= 0 ? 0 : ((run - 2 - 1) / 2 + 1);
}
}
}
return n <= sum;
}
}
``````

This array-based solution can be extended to solve most problems that requires paragraph delimiting.

Hope this more or less helps.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.