I like to read this solution as a small machine: keep the useful information, throw away the noise. For 1562. Find Latest Group of Size M, the solution in this repository is mainly a union-find solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: union-find, binary search, two pointers.
The notes already sitting in the source point us in the right direction:
- Union find
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are unite, add, print, findLatestStep, counter.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Union find
02//Runtime: 352 ms, faster than 40.00% of C++ online submissions for Find Latest Group of Size M.
03//Memory Usage: 89.7 MB, less than 20.00% of C++ online submissions for Find Latest Group of Size M.
04class DSU{
05public:
06 int n;
07 vector<int> parent;
08 vector<int> gsize;
09 vector<int> gsize2count;
10
11 DSU(int n){
12 this->n = n;
13 //initially there are no unions
14 //so every union's parent is -1
15 parent = vector<int>(n, -1);
16 // iota(parent.begin(), parent.end(), 0);
17 gsize = vector<int>(n, 0);
18 gsize2count = vector<int>(n+1, 0);
19 }
20
21 int find(int x){
22 //added stop condition for uninitialized parent
23 if(x == -1) return -1;
24 if(parent[x] != x){
25 parent[x] = find(parent[x]);
26 }
27 return parent[x];
28 }
29
30 void unite(int x, int y){
31 //merge y into x
32 int px = find(x);
33 int py = find(y);
34
35 int gsizex = gsize[px];
36 int gsizey = gsize[py];
37 int gsizenew = gsizex + gsizey;
38 parent[py] = px;
39 gsize[px] = gsize[py] = gsizenew;
40 --gsize2count[gsizex];
41 --gsize2count[gsizey];
42 ++gsize2count[gsizenew];
43 }
44
45 void add(int x){
46 //add a element to dsu
47 parent[x] = x;
48 ++gsize[x];
49 ++gsize2count[gsize[x]];
50 }
51
52 void print(){
53 cout << "ancestor: " << endl;
54 for(int i = 0; i < n; ++i){
55 cout << find(i) << " ";
56 }
57 cout << endl;
58 cout << "gsize: " << endl;
59 for(int i = 0; i < n; ++i){
60 /*
61 look at (the group containing i)'s size,
62 so not gsize[i]
63 */
64 cout << ((find(i) != -1) ? gsize[find(i)] : 0) << " ";
65 }
66 cout << endl;
67 cout << "gsize2count: " << endl;
68 for(int gsize = 0; gsize <= n; ++gsize){
69 cout << gsize2count[gsize] << " ";
70 }
71 cout << endl;
72 }
73};
74
75class Solution {
76public:
77 int findLatestStep(vector<int>& arr, int m) {
78 int n = arr.size();
79 //group size -> count
80 vector<int> counter(n+1, 0);
81
82 transform(arr.begin(), arr.end(), arr.begin(), [](int& x){return x-1;});
83
84 int ans = -1;
85 string s(n, '0');
86 DSU dsu(n);
87
88 for(int i = 0; i < n; ++i){
89 int num = arr[i];
90 s[num] = '1';
91 //add a new group
92 dsu.add(num);
93 if(num-1 >= 0 && s[num-1] == '1' && num+1 < n && s[num+1] == '1'){
94 // cout << "both sides 1" << endl;
95 //merge the two groups at num's two sides
96 dsu.unite(num-1, num+1);
97 dsu.unite(num-1, num);
98 }else if(num-1 >= 0 && s[num-1] == '1'){
99 // cout << "left side 1" << endl;
100 //merge current position into the group at its front
101 dsu.unite(num-1, num);
102 }else if(num+1 < n && s[num+1] == '1'){
103 // cout << "right side 1" << endl;
104 //merge the group behind to itself
105 dsu.unite(num, num+1);
106 }
107
108 // dsu.print();
109
110 if(dsu.gsize2count[m] > 0){
111 //i is 0-based, step is 1-based
112 ans = i+1;
113 }
114 }
115
116 return ans;
117 }
118};
119
120//count the length of groups
121//Runtime: 320 ms, faster than 40.00% of C++ online submissions for Find Latest Group of Size M.
122//Memory Usage: 82.7 MB, less than 20.00% of C++ online submissions for Find Latest Group of Size M.
123//https://leetcode.com/problems/find-latest-group-of-size-m/discuss/806786/JavaC%2B%2BPython-Count-the-Length-of-Groups-O(N)
124class Solution {
125public:
126 int findLatestStep(vector<int>& arr, int m) {
127 int n = arr.size();
128
129 //padding 0 left and padding n+1 right
130 vector<int> length(n+2, 0);
131 //range: [0,n]
132 vector<int> counter(n+1, 0);
133 int ans = -1;
134
135 for(int i = 0; i < n; ++i){
136 int num = arr[i];
137
138 //the length of "1" groups to its left and right
139 int left_len = length[num-1];
140 int right_len = length[num+1];
141
142 /*
143 we only update "length" value for those who are boundary of "1" groups,
144 so the element in the middle of "1" group's "length" value could be outdated,
145 but that's fine,
146 because we won't access middle element's "length" value
147 */
148 length[num-left_len] = length[num+right_len] = left_len + right_len + 1;
149
150 --counter[left_len];
151 --counter[right_len];
152 ++counter[length[num-left_len]];
153
154 if(counter[m] > 0){
155 ans = i+1;
156 }
157 }
158
159 return ans;
160 }
161};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.