{x}
blog image

Find Latest Group of Size M

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.

Solution Explanation

This problem asks to find the latest step at which there exists a contiguous group of '1's of length m in a binary string, where bits are set to '1' according to the order specified in the input array arr.

Approach 1: Union-Find

This approach utilizes the Union-Find data structure to efficiently track contiguous groups of '1's.

  1. Initialization:

    • We create a parent array p and a size array to represent the Union-Find structure. Initially, each element is its own parent (p[i] = i), and each group has size 1 (size[i] = 1).
    • A vis array tracks which bits have been set to '1'.

  2. Iteration:

    • The code iterates through the arr array. For each element v, it sets the corresponding bit in the implicit binary string to '1' (vis[v-1] = True).
    • Union Operations: It checks the neighbors of v. If a neighbor is already set to '1', it performs a union operation using union(v, v-1) or union(v, v+1). The union function merges the groups represented by v and its neighbor, updating the parent and size arrays accordingly.
    • Group Size Check: After each union operation, the code checks if the size of the newly merged group is equal to m. If it is, the current step i is recorded as a potential answer (ans).

  3. Return Value: The function returns the latest step ans at which a group of size m was found. If no such group was found, it returns -1.

Time Complexity: O(N log N) in the worst case, where N is the length of arr, due to the Union-Find operations. The find operation, which is used in union, can have logarithmic time complexity depending on the implementation. Space Complexity: O(N) to store the Union-Find data structures (p, size, vis).

Approach 2: Interval Merging

This approach leverages interval merging techniques.

  1. Initialization:

    • cnt array of size n+2 is used to store the length of contiguous sequences of 1's. cnt[i] denotes the length of the sequence ending at position i. The extra space handles boundary cases.

  2. Iteration:

    • The code iterates through the input array arr. For each element v, it updates the cnt array to reflect the newly set bit.
    • It calculates l and r, which represents the lengths of the sequences of 1's to the left and right of v respectively.
    • Check for group of size m: If either l or r is equal to m, it means a group of size m is found at this step. The index i is stored in ans.
    • Merge intervals: The lengths l and r are merged to form a new sequence of length l + r + 1. The cnt array is updated accordingly.

  3. Return Value: The function returns the latest step (ans) where a group of size m was found, or -1 if no such group was found.

Time Complexity: O(N), where N is the length of arr. The code iterates through the array once, and the operations within the loop are constant time. Space Complexity: O(N) for the cnt array.

The second approach (interval merging) is generally more efficient due to its linear time complexity. The Union-Find approach is a more general technique that can handle more complex scenarios involving disjoint set operations. However, for this specific problem, the interval merging approach provides a simpler and more efficient solution.