{"id":7300,"date":"2020-08-23T11:22:49","date_gmt":"2020-08-23T18:22:49","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7300"},"modified":"2020-08-23T11:32:26","modified_gmt":"2020-08-23T18:32:26","slug":"leetcode-1562-find-latest-group-of-size-m","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-1562-find-latest-group-of-size-m\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1562. Find Latest Group of Size M"},"content":{"rendered":"\n<p>Given an array&nbsp;<code>arr<\/code>&nbsp;that represents a permutation of numbers from&nbsp;<code>1<\/code>&nbsp;to&nbsp;<code>n<\/code>. You have a binary string of size&nbsp;<code>n<\/code>&nbsp;that initially has all its bits set to zero.<\/p>\n\n\n\n<p>At each step&nbsp;<code>i<\/code>&nbsp;(assuming both the binary string and&nbsp;<code>arr<\/code>&nbsp;are 1-indexed) from&nbsp;<code>1<\/code>&nbsp;to&nbsp;<code>n<\/code>, the bit at position&nbsp;<code>arr[i]<\/code>&nbsp;is set to&nbsp;<code>1<\/code>. You are given an integer&nbsp;<code>m<\/code>&nbsp;and you need to find the latest step at which there exists a group of ones of length&nbsp;<code>m<\/code>. A group of ones is a contiguous substring of 1s such that it cannot be extended in either direction.<\/p>\n\n\n\n<p>Return&nbsp;<em>the latest step at which there exists a group of ones of length&nbsp;<strong>exactly<\/strong><\/em>&nbsp;<code>m<\/code>.&nbsp;<em>If no such group exists, return<\/em>&nbsp;<code>-1<\/code>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> arr = [3,5,1,2,4], m = 1\n<strong>Output:<\/strong> 4\n<strong>Explanation:\n<\/strong>Step 1: \"00100\", groups: [\"1\"]\nStep 2: \"00101\", groups: [\"1\", \"1\"]\nStep 3: \"10101\", groups: [\"1\", \"1\", \"1\"]\nStep 4: \"11101\", groups: [\"111\", \"1\"]\nStep 5: \"11111\", groups: [\"11111\"]\nThe latest step at which there exists a group of size 1 is step 4.<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> arr = [3,1,5,4,2], m = 2\n<strong>Output:<\/strong> -1\n<strong>Explanation:\n<\/strong>Step 1: \"00100\", groups: [\"1\"]\nStep 2: \"10100\", groups: [\"1\", \"1\"]\nStep 3: \"10101\", groups: [\"1\", \"1\", \"1\"]\nStep 4: \"10111\", groups: [\"1\", \"111\"]\nStep 5: \"11111\", groups: [\"11111\"]\nNo group of size 2 exists during any step.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> arr = [1], m = 1\n<strong>Output:<\/strong> 1\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> arr = [2,1], m = 2\n<strong>Output:<\/strong> 2\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>n == arr.length<\/code><\/li><li><code>1 &lt;= n &lt;= 10^5<\/code><\/li><li><code>1 &lt;= arr[i] &lt;= n<\/code><\/li><li>All integers in&nbsp;<code>arr<\/code>&nbsp;are&nbsp;<strong>distinct<\/strong>.<\/li><li><code>1 &lt;= m&nbsp;&lt;= arr.length<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Hashtable<\/strong><\/h2>\n\n\n\n<p>Similar to <a href=\"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-128-longest-consecutive-sequence\/\">LC 128<\/a><\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int findLatestStep(vector<int>& arr, int m) {\n    const int n = arr.size();\n    vector<int> len(n + 2);\n    vector<int> counts(n + 2);\n    int ans = -1;\n    for (int i = 0; i < n; ++i) {\n      const int x = arr[i];      \n      const int l = len[x - 1];\n      const int r = len[x + 1];\n      const int t = 1 + l + r;  \n      len[x - l] = len[x + r] = t;\n      --counts[l];\n      --counts[r];\n      ++counts[t];\n      if (counts[m]) ans = i + 1;\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given an array&nbsp;arr&nbsp;that represents a permutation of numbers from&nbsp;1&nbsp;to&nbsp;n. You have a binary string of size&nbsp;n&nbsp;that initially has all its bits set to zero. At&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70],"tags":[82,177],"class_list":["post-7300","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-hashtable","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7300","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7300"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7300\/revisions"}],"predecessor-version":[{"id":7303,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7300\/revisions\/7303"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7300"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7300"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7300"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}