GoogleOA_FlowerGroup [source code]

public class GoogleOA_FlowerGroup {
static
/******************************************************************************/
class Solution {
    public int solution(int[] P, int K) {
        int N = P.length;
        if (N == 0 || K > N - 2)
            return -1;
        boolean[] bloomed = new boolean[N + 1];
        UnionFind uf = new UnionFind (N);
        int res = -1;
        for (int i = 0; i < N; i++) {
            int p = P[i];
            bloomed[p] = true;
            if (p - 1 >= 0 && bloomed[p - 1])
                uf.union (p - 1, p);
            if (p + 1 <= N && bloomed[p + 1])
                uf.union (p, p + 1);
            Integer count_k_size = uf.size_counts.get (K);
            if (count_k_size != null && count_k_size > 0)
                res = i + 1;
        }
        return res;
    }

    class UnionFind {
        int[] parent;
        int[] rank;
        int[] size;
        Map<Integer, Integer> size_counts = new HashMap<> ();

        UnionFind (int N) {
            parent = new int[N + 1];
            rank = new int[N + 1];
            size = new int[N + 1];
            for (int i = 1; i <= N; i++) {
                parent[i] = i;
                rank[i] = 0;
                size[i] = 1;
            }
            size_counts.put (1, N);
        }

        int find (int i) {
            if (parent[i] != i)
                parent[i] = find (parent[i]);
            return parent[i];
        }

        void union (int a, int b) {
            System.out.printf ("union: %d and %d\n", a, b);
            int root_a = find (a), root_b = find (b);
            if (root_a != root_b) {
                if (rank[root_a] >= rank[root_b]) {
                    if (rank[root_a] == rank[root_b])
                        rank[root_a]++;
                    parent[root_b] = root_a;
                    size_counts.put (size[root_a], size_counts.getOrDefault (size[root_a], 0) - 1);
                    size_counts.put (size[root_b], size_counts.getOrDefault (size[root_b], 0) - 1);
                    size[root_a] += size[root_b];
                    size_counts.put (size[root_a], size_counts.getOrDefault (size[root_a], 0) + 1);
                } else {
                    parent[root_a] = root_b;
                    size_counts.put (size[root_a], size_counts.getOrDefault (size[root_a], 0) - 1);
                    size_counts.put (size[root_b], size_counts.getOrDefault (size[root_b], 0) - 1);
                    size[root_b] += size[root_a];
                    size_counts.put (size[root_a], size_counts.getOrDefault (size[root_a], 0) + 1);
                }
            }
        }

        int getSize (int a) {
            int root = find (a);
            return size[root];
        }
    }

}
/******************************************************************************/

    public static void main(String[] args) {
        GoogleOA_FlowerGroup.Solution tester = new GoogleOA_FlowerGroup.Solution();
        int[][] inputs = {
            {3,1,5,4,2},{1,4},
            {3,1,5,4,2},{2,-1},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            System.out.println (Printer.separator ());
            int[] P = inputs[2 * i];
            int k = inputs[2 * i + 1][0], ans = inputs[2 * i + 1][1], output = tester.solution (P, k);
            System.out.printf ("%s and %d -> %s, expected: %d\n", 
                Printer.array (P), k, Printer.wrap (output + "", output == ans ? 92 : 91), ans
            );
        }


    }
}

Problem Description

跟

1. K Empty Slots
   类似, 但是要求的是K等于连续开花的group的size; 感觉难一点, 只能用UF来做;