Package g1501_1600.s1562_find_latest_group_of_size_m

Class Solution

java.lang.Object

g1501_1600.s1562_find_latest_group_of_size_m.Solution

public class Solution
extends Object

1562 - Find Latest Group of Size M.<p>Medium</p> <p>Given an array <code>arr</code> that represents a permutation of numbers from <code>1</code> to <code>n</code>.</p> <p>You have a binary string of size <code>n</code> that initially has all its bits set to zero. At each step <code>i</code> (assuming both the binary string and <code>arr</code> are 1-indexed) from <code>1</code> to <code>n</code>, the bit at position <code>arr[i]</code> is set to <code>1</code>.</p> <p>You are also given an integer <code>m</code>. Find the latest step at which there exists a group of ones of length <code>m</code>. A group of ones is a contiguous substring of <code>1</code>&rsquo;s such that it cannot be extended in either direction.</p> <p>Return <em>the latest step at which there exists a group of ones of length <strong>exactly</strong></em> <code>m</code>. <em>If no such group exists, return</em> <code>-1</code>.</p> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> arr = [3,5,1,2,4], m = 1</p> <p><strong>Output:</strong> 4</p> <p><strong>Explanation:</strong></p> <p>Step 1: &ldquo;00100&rdquo;, groups: [&ldquo;1&rdquo;]</p> <p>Step 2: &ldquo;00101&rdquo;, groups: [&ldquo;1&rdquo;, &ldquo;1&rdquo;]</p> <p>Step 3: &ldquo;10101&rdquo;, groups: [&ldquo;1&rdquo;, &ldquo;1&rdquo;, &ldquo;1&rdquo;]</p> <p>Step 4: &ldquo;11101&rdquo;, groups: [&ldquo;111&rdquo;, &ldquo;1&rdquo;]</p> <p>Step 5: &ldquo;11111&rdquo;, groups: [&ldquo;11111&rdquo;]</p> <p>The latest step at which there exists a group of size 1 is step 4.</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> arr = [3,1,5,4,2], m = 2</p> <p><strong>Output:</strong> -1</p> <p><strong>Explanation:</strong></p> <p>Step 1: &ldquo;00100&rdquo;, groups: [&ldquo;1&rdquo;]</p> <p>Step 2: &ldquo;10100&rdquo;, groups: [&ldquo;1&rdquo;, &ldquo;1&rdquo;]</p> <p>Step 3: &ldquo;10101&rdquo;, groups: [&ldquo;1&rdquo;, &ldquo;1&rdquo;, &ldquo;1&rdquo;]</p> <p>Step 4: &ldquo;10111&rdquo;, groups: [&ldquo;1&rdquo;, &ldquo;111&rdquo;]</p> <p>Step 5: &ldquo;11111&rdquo;, groups: [&ldquo;11111&rdquo;]</p> <p>No group of size 2 exists during any step.</p> <p><strong>Constraints:</strong></p> <ul> <li><code>n == arr.length</code></li> <li><code>1 <= m <= n <= 10⁵</code></li> <li><code>1 <= arr[i] <= n</code></li> <li>All integers in <code>arr</code> are <strong>distinct</strong>.</li> </ul>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
int	findLatestStep(int[] arr, int m)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

findLatestStep

public int findLatestStep(int[] arr,
 int m)