#1562

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find Latest Group of Size M

Determine the latest step where a contiguous group of ones of exact length m exists using array scanning and hash tracking.

array hash table binary search simulation

Problem Statement

You are given a permutation array arr of length n containing numbers from 1 to n. Start with a binary string of size n initialized to all zeros. At each step i, set the bit at position arr[i] to 1, creating contiguous groups of ones dynamically.

Given an integer m, determine the latest step at which there exists at least one contiguous group of ones of length exactly m. A group of ones is defined as consecutive 1's that cannot be extended left or right. If no such group ever exists, return -1.

Examples

Example 1

Input: arr = [3,5,1,2,4], m = 1

Output: 4

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

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.

Solution Approach

Use a Hash Map to Track Group Boundaries

Maintain a hash map where keys are positions and values are the lengths of the group ending or starting at that position. When a new one is placed, check left and right neighbors to merge groups, update lengths, and check if a group of size m appears. This ensures O(1) updates per step.

Scan the Array Once

Iterate through arr sequentially. At each step, update the group lengths in the hash map and track counts of groups of length m. This approach directly aligns with the array scanning plus hash lookup pattern, efficiently identifying when target-sized groups appear or disappear.

Consider Reverse Search for Latest Step

Since the problem asks for the latest step, optionally scan from the end or maintain a running latest-step variable whenever a group of size m exists. This prevents unnecessary full iteration and aligns with the failure mode where early detection might be misleading.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity can be O(n) since each position is updated at most once, and hash lookups are O(1). Space complexity is O(n) to store group boundaries and counts of groups of specific lengths.

What Interviewers Usually Probe

Asks if groups can merge or split dynamically and how to track that efficiently.
Questions whether scanning from the end helps in quickly finding the latest step.
Checks understanding of hash-based bookkeeping for constant-time group length updates.

Common Pitfalls or Variants

Common pitfalls

Failing to update both ends of a merged group, leading to incorrect group length tracking.
Counting overlapping groups incorrectly, especially after merges or splits.
Assuming the first occurrence is enough instead of tracking the latest step.

Follow-up variants

Find the earliest step a group of size m exists instead of the latest.
Return the number of steps where at least one group of size m exists.
Change the problem to track groups of at least size m instead of exact size.

FAQ

What is the core pattern in Find Latest Group of Size M?

It is array scanning plus hash lookup to maintain group boundaries and quickly detect groups of exact length m.

Can we solve this problem without a hash map?

Yes, using a union-find or array-based boundary tracking is possible, but hash maps simplify dynamic length updates and merges.

Why is scanning from the end recommended?

Scanning from the end lets you detect the latest step quickly, aligning with the problem's request to find the last occurrence of a group of size m.

How do we handle overlapping or merging groups?

Update both start and end positions in the hash map when a new one connects neighboring groups to prevent miscounting.

What if no group of size m ever exists?

Return -1, indicating that during the entire process no contiguous group of ones matched the required length.

terminal

Solution

Solution 1

#### Python3

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

27

28

29

30

31

32

33

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

Solution 2

#### Python3

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

27

28

29

30

31

32

33

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

Continue Practicing

#1488 avoid flood in the city #1477 find two non overlapping sub arrays each with target sum #1658 minimum operations to reduce x to zero