Skip to content

1562. Find Latest Group of Size M 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  int findLatestStep(vector<int>& arr, int m) {
    if (arr.size() == m)
      return arr.size();

    int ans = -1;
    int step = 0;
    // sizes[i] := the size of the group starting from i or ending in i
    // (1-indexed)
    vector<int> sizes(arr.size() + 2);

    for (const int i : arr) {
      ++step;
      // In the previous step, there exists a group with a size of m.
      if (sizes[i - 1] == m || sizes[i + 1] == m)
        ans = step - 1;
      const int head = i - sizes[i - 1];
      const int tail = i + sizes[i + 1];
      sizes[head] = tail - head + 1;
      sizes[tail] = tail - head + 1;
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
  public int findLatestStep(int[] arr, int m) {
    if (arr.length == m)
      return arr.length;

    int ans = -1;
    int step = 0;
    // sizes[i] := the size of the group starting from i or ending in i
    // (1-indexed)
    int[] sizes = new int[arr.length + 2];

    for (final int i : arr) {
      ++step;
      // In the previous step, there exists a group with a size of m.
      if (sizes[i - 1] == m || sizes[i + 1] == m)
        ans = step - 1;
      final int head = i - sizes[i - 1];
      final int tail = i + sizes[i + 1];
      sizes[head] = tail - head + 1;
      sizes[tail] = tail - head + 1;
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def findLatestStep(self, arr: List[int], m: int) -> int:
    if len(arr) == m:
      return len(arr)

    ans = -1
    step = 0
    # sizes[i] := the size of the group starting from i or ending in i
    # (1-indexed)
    sizes = [0] * (len(arr) + 2)

    for i in arr:
      step += 1
      # In the previous step, there exists a group with a size of m.
      if sizes[i - 1] == m or sizes[i + 1] == m:
        ans = step - 1
      head = i - sizes[i - 1]
      tail = i + sizes[i + 1]
      sizes[head] = tail - head + 1
      sizes[tail] = tail - head + 1

    return ans