LeetCode 1562. Find Latest Group of Size M Solution in Java, C++, Python & More | Explanation + Code

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

PythonJavaC++GoJavaScript

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(code-box)

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]; } }(code-box)

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]; } };(code-box)

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 }(code-box)

const findLatestStep = function (arr, m) { function find(x) { if (p[x] !== x) { p[x] = find(p[x]); } return p[x]; } function union(a, b) { const pa = find(a); const pb = find(b); if (pa === pb) { return; } p[pa] = pb; size[pb] += size[pa]; } const n = arr.length; if (m === n) { return n; } const vis = Array(n).fill(false); const p = Array.from({ length: n }, (_, i) => i); const size = Array(n).fill(1); let ans = -1; for (let i = 0; i < n; ++i) { const 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; };(code-box)

Solution 2

PythonJavaC++Go

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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)