Find Latest Group of Size M LeetCode solution in Java

1
class Solution {
2
  int[] par, size, count, bits;
3

4
  // par: parent array, tells about whose it the parent of ith element
5
  // size: it tells the size of component
6
  // count: it tells the count of islands (1111 etc) of size i;
7
  // count[3] = 4: ie -> there are 4 islands of size 3
8

9
  public int find(int u) {
10
    if (u == par[u]) return u;
11
    par[u] = find(par[u]);
12
    return par[u];
13
  }
14

15
  public void union(int u, int v) {
16
    // union is performed over parents of elements not nodes itself
17
    int p1 = find(u), p2 = find(v);
18
    if (p1 == p2) return;
19

20
    // decrease the count of islands of size p1, p2
21
    count[size[p1]]--;
22
    count[size[p2]]--;
23

24
    // now merge
25
    par[p2] = p1;
26

27
    // adjust sizes
28
    size[p1] += size[p2];
29

30
    // adjust the count of islands of new size ie: size of p1
31
    count[size[p1]]++;
32
  }
33

34
  public int findLatestStep(int[] arr, int m) {
35
    int n = arr.length;
36
    par = new int[n + 1];
37
    size = new int[n + 1];
38
    count = new int[n + 1];
39
    bits = new int[n + 2];
40

41
    for (int i = 0; i < n; i++) {
42
      par[i] = i;
43
      size[i] = 1;
44
    }
45

46
    int ans = -1;
47
    for (int i = 0; i < n; i++) {
48
      int idx = arr[i];
49
      // set the bit
50
      bits[idx] = 1;
51
      // increase the count of islands of size 1
52
      count[1]++;
53

54
      if (bits[idx - 1] > 0) {
55
        union(idx, idx - 1);
56
      }
57
      if (bits[idx + 1] > 0) {
58
        union(idx, idx + 1);
59
      }
60

61
      // check if island of size m exists
62
      if (count[m] > 0) {
63
        ans = i + 1;
64
        // as it is 1 based indexing
65
      }
66
    }
67
    return ans;
68
  }
69
}