Find Latest Group of Size M — LeetCode 1562 Python Solution
MediumArrayHash TableBinary SearchSimulation
- Problem
- #1562
- Pattern
- Binary Search
- Reading time
- 6 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- arr = [3,5,1,2,4], m = 1
- Output
- 4
- Explanation
- Step 1: "00100", groups: ["1"]
Python solution
Python
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 ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Binary Search
Halve the search space each step — over an array, or over the answer itself. LeetCode 1562. Find Latest Group of Size M is filed here because LeetCode tags it Binary Search, which is the vocabulary this hub collects.
The binary search guide has the Python template for the pattern and the 254 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1562. Find Latest Group of Size M?
- LeetCode 1562. Find Latest Group of Size M is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1562. Find Latest Group of Size M?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1562. Find Latest Group of Size M?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1562. Find Latest Group of Size M cover?
- LeetCode 1562. Find Latest Group of Size M is tagged Array, Hash Table, Binary Search and Simulation on LeetCode.