Welcome to Subscribe On Youtube
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.length1 <= m <= n <= 1051 <= arr[i] <= n- All integers in
arrare distinct.
Solutions
-
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]; } }; -
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 -
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 }