Question

1562. Find Latest Group of Size M

中文文档

Description

Given an array arr that represents a permutation of numbers from 1 to n.

You have a binary string of size n that initially has all its bits set to zero. At each step i (assuming both the binary string and arr are 1-indexed) from 1 to n, the bit at position arr[i] is set to 1.

You are also given an integer m. Find the latest step at which there exists a group of ones of length m. A group of ones is a contiguous substring of 1's such that it cannot be extended in either direction.

Return _the latest step at which there exists a group of ones of length exactly_ m. _If no such group exists, return_ -1.

 

Example 1:

Input: arr = [3,5,1,2,4], m = 1
Output: 4
Explanation: 
Step 1: "00100", groups: ["1"]
Step 2: "00101", groups: ["1", "1"]
Step 3: "10101", groups: ["1", "1", "1"]
Step 4: "11101", groups: ["111", "1"]
Step 5: "11111", groups: ["11111"]
The latest step at which there exists a group of size 1 is step 4.

Example 2:

Input: arr = [3,1,5,4,2], m = 2
Output: -1
Explanation: 
Step 1: "00100", groups: ["1"]
Step 2: "10100", groups: ["1", "1"]
Step 3: "10101", groups: ["1", "1", "1"]
Step 4: "10111", groups: ["1", "111"]
Step 5: "11111", groups: ["11111"]
No group of size 2 exists during any step.

 

Constraints:

• n == arr.length
• 1 <= m <= n <= 105
• 1 <= arr[i] <= n
• All integers in arr are distinct.

Solutions

Solution 1

class Solution:
  def findLatestStep(self, arr: List[int], m: int) -> int:
    def find(x):
      if p[x] != x:
        p[x] = find(p[x])
      return p[x]

    def union(a, b):
      pa, pb = find(a), find(b)
      if pa == pb:
        return
      p[pa] = pb
      size[pb] += size[pa]

    n = len(arr)
    if m == n:
      return n
    vis = [False] * n
    p = list(range(n))
    size = [1] * n
    ans = -1
    for i, v in enumerate(arr):
      v -= 1
      if v and vis[v - 1]:
        if size[find(v - 1)] == m:
          ans = i
        union(v, v - 1)
      if v < n - 1 and vis[v + 1]:
        if size[find(v + 1)] == m:
          ans = i
        union(v, v + 1)
      vis[v] = True
    return ans

class Solution {
  private int[] p;
  private int[] size;

  public int findLatestStep(int[] arr, int m) {
    int n = arr.length;
    if (m == n) {
      return n;
    }
    boolean[] vis = new boolean[n];
    p = new int[n];
    size = new int[n];
    for (int i = 0; i < n; ++i) {
      p[i] = i;
      size[i] = 1;
    }
    int ans = -1;
    for (int i = 0; i < n; ++i) {
      int v = arr[i] - 1;
      if (v > 0 && vis[v - 1]) {
        if (size[find(v - 1)] == m) {
          ans = i;
        }
        union(v, v - 1);
      }
      if (v < n - 1 && vis[v + 1]) {
        if (size[find(v + 1)] == m) {
          ans = i;
        }
        union(v, v + 1);
      }
      vis[v] = true;
    }
    return ans;
  }

  private int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }

  private void union(int a, int b) {
    int pa = find(a), pb = find(b);
    if (pa == pb) {
      return;
    }
    p[pa] = pb;
    size[pb] += size[pa];
  }
}

class Solution {
public:
  vector<int> p;
  vector<int> size;

  int findLatestStep(vector<int>& arr, int m) {
    int n = arr.size();
    if (m == n) return n;
    p.resize(n);
    size.assign(n, 1);
    for (int i = 0; i < n; ++i) p[i] = i;
    int ans = -1;
    vector<int> vis(n);
    for (int i = 0; i < n; ++i) {
      int v = arr[i] - 1;
      if (v && vis[v - 1]) {
        if (size[find(v - 1)] == m) ans = i;
        unite(v, v - 1);
      }
      if (v < n - 1 && vis[v + 1]) {
        if (size[find(v + 1)] == m) ans = i;
        unite(v, v + 1);
      }
      vis[v] = true;
    }
    return ans;
  }

  int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
  }

  void unite(int a, int b) {
    int pa = find(a), pb = find(b);
    if (pa == pb) return;
    p[pa] = pb;
    size[pb] += size[pa];
  }
};

func findLatestStep(arr []int, m int) int {
  n := len(arr)
  if m == n {
    return n
  }
  p := make([]int, n)
  size := make([]int, n)
  vis := make([]bool, n)
  for i := range p {
    p[i] = i
    size[i] = 1
  }
  var find func(int) int
  find = func(x int) int {
    if p[x] != x {
      p[x] = find(p[x])
    }
    return p[x]
  }
  union := func(a, b int) {
    pa, pb := find(a), find(b)
    if pa == pb {
      return
    }
    p[pa] = pb
    size[pb] += size[pa]
  }

  ans := -1
  for i, v := range arr {
    v--
    if v > 0 && vis[v-1] {
      if size[find(v-1)] == m {
        ans = i
      }
      union(v, v-1)
    }
    if v < n-1 && vis[v+1] {
      if size[find(v+1)] == m {
        ans = i
      }
      union(v, v+1)
    }
    vis[v] = true
  }
  return ans
}

Solution 2

class Solution:
  def findLatestStep(self, arr: List[int], m: int) -> int:
    n = len(arr)
    if m == n:
      return n
    cnt = [0] * (n + 2)
    ans = -1
    for i, v in enumerate(arr):
      v -= 1
      l, r = cnt[v - 1], cnt[v + 1]
      if l == m or r == m:
        ans = i
      cnt[v - l] = cnt[v + r] = l + r + 1
    return ans

class Solution {
  public int findLatestStep(int[] arr, int m) {
    int n = arr.length;
    if (m == n) {
      return n;
    }
    int[] cnt = new int[n + 2];
    int ans = -1;
    for (int i = 0; i < n; ++i) {
      int v = arr[i];
      int l = cnt[v - 1], r = cnt[v + 1];
      if (l == m || r == m) {
        ans = i;
      }
      cnt[v - l] = l + r + 1;
      cnt[v + r] = l + r + 1;
    }
    return ans;
  }
}

class Solution {
public:
  int findLatestStep(vector<int>& arr, int m) {
    int n = arr.size();
    if (m == n) return n;
    vector<int> cnt(n + 2);
    int ans = -1;
    for (int i = 0; i < n; ++i) {
      int v = arr[i];
      int l = cnt[v - 1], r = cnt[v + 1];
      if (l == m || r == m) ans = i;
      cnt[v - l] = cnt[v + r] = l + r + 1;
    }
    return ans;
  }
};

func findLatestStep(arr []int, m int) int {
  n := len(arr)
  if m == n {
    return n
  }
  cnt := make([]int, n+2)
  ans := -1
  for i, v := range arr {
    l, r := cnt[v-1], cnt[v+1]
    if l == m || r == m {
      ans = i
    }
    cnt[v-l], cnt[v+r] = l+r+1, l+r+1
  }
  return ans
}