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 given an integer m and you need to find the latest step at which there exists a group of ones of length m. A group of ones is a contiguous substring of 1s 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.
Example 3:
Input: arr = [1], m = 1 Output: 1
Example 4:
Input: arr = [2,1], m = 2 Output: 2
Constraints:
n == arr.length1 <= n <= 10^51 <= arr[i] <= n- All integers in
arrare distinct. 1 <= m <= arr.length
Solution: Hashtable
Similar to LC 128
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua class Solution { public: int findLatestStep(vector<int>& arr, int m) { const int n = arr.size(); vector<int> len(n + 2); vector<int> counts(n + 2); int ans = -1; for (int i = 0; i < n; ++i) { const int x = arr[i]; const int l = len[x - 1]; const int r = len[x + 1]; const int t = 1 + l + r; len[x - l] = len[x + r] = t; --counts[l]; --counts[r]; ++counts[t]; if (counts[m]) ans = i + 1; } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment