Welcome to Subscribe On Youtube
4076. Longest Resilient Subarray II
Description
You are given an integer array nums and an integer k.
A subarray is resilient if, for every position in it, deleting the element at that position leaves the remaining elements with a sum divisible by k.
For a subarray of length 1, the remaining sum is 0, which is divisible by k.
Return the length of the longest resilient subarray.
Example 1:
Input: nums = [2,4,6,3], k = 2
Output: 3
Explanation:
The subarray [2, 4, 6] sums to 12. Deleting 2, 4, or 6 leaves a sum of 10, 8, or 6, respectively, each of which is divisible by 2. Therefore, the answer is 3.
Example 2:
Input: nums = [1,4,7,1], k = 3
Output: 4
Explanation:
The subarray [1, 4, 7, 1] sums to 13. Deleting the first 1, the 4, the 7, or the last 1 leaves a sum of 12, 9, 6, or 12, respectively, each of which is divisible by 3. Therefore, the answer is 4.
Example 3:
Input: nums = [5,5,4,8], k = 4
Output: 2
Explanation:
The subarray [5, 5] is not resilient, since deleting either 5 leaves a sum of 5, which is not divisible by 4.
The subarray [4, 8] sums to 12. Deleting 4 or 8 leaves a sum of 8 or 4, respectively, each of which is divisible by 4. Therefore, the answer is 2.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1051 <= k <= 105
Solutions
Solution 1: Congruent Runs
Thinking
Once $n$ reaches $10^5$, enumerating intervals and recomputing the remaining sums no longer fits. A resilient subarray is still exactly a block of equal residues modulo $k$: if the residue is $r$ and the length is $L$, then $(L-1)r\equiv 0\pmod{k}$.
The scan therefore walks each run of equal residues, increases the length by one, and updates the answer whenever the condition holds.
Both $r$ and the run length can be as large as $10^5$, so the product $r\cdot(\textit{cnt}-1)$ exceeds a $32$-bit integer. The divisibility test is computed with $64$-bit arithmetic.
Reduce every element modulo $k$. Equal residues form contiguous runs. Let $r$ be the residue of the current run and $\textit{cnt}$ its current length. A run of length $1$ is always resilient, because the remaining sum is $0$. Whenever
\[r\cdot(\textit{cnt}-1)\equiv 0\pmod{k},\]the prefix of length $\textit{cnt}$ is resilient, and the answer is updated with $\textit{cnt}$. Both $r$ and $\textit{cnt}$ can reach $10^5$, so the product is computed with $64$-bit integers. A change of residue starts a new run.
The time complexity is $O(n)$, and the space complexity is $O(1)$, where $n$ is the length of $\textit{nums}$.
-
class Solution { public int resilientSubarray(int[] nums, int k) { int ans = 0, cnt = 0; for (int i = 0; i < nums.length; i++) { int x = nums[i] % k; if (i > 0 && nums[i - 1] % k == x) { cnt++; } else { cnt = 1; } if ((long) x * (cnt - 1) % k == 0) { ans = Math.max(ans, cnt); } } return ans; } } -
class Solution { public: int resilientSubarray(vector<int>& nums, int k) { int ans = 0, cnt = 0; for (int i = 0; i < nums.size(); i++) { int x = nums[i] % k; if (i > 0 && nums[i - 1] % k == x) { cnt++; } else { cnt = 1; } if (1LL * x * (cnt - 1) % k == 0) { ans = max(ans, cnt); } } return ans; } }; -
class Solution: def resilientSubarray(self, nums: list[int], k: int) -> int: ans = cnt = 0 for i, x in enumerate(nums): x %= k if i and nums[i - 1] % k == x: cnt += 1 else: cnt = 1 if x * (cnt - 1) % k == 0: ans = max(ans, cnt) return ans -
func resilientSubarray(nums []int, k int) int { ans, cnt := 0, 0 for i, v := range nums { x := v % k if i > 0 && nums[i-1]%k == x { cnt++ } else { cnt = 1 } if int64(x)*int64(cnt-1)%int64(k) == 0 { ans = max(ans, cnt) } } return ans } -
function resilientSubarray(nums: number[], k: number): number { let ans = 0, cnt = 0; for (let i = 0; i < nums.length; i++) { const x = nums[i] % k; if (i > 0 && nums[i - 1] % k === x) { cnt++; } else { cnt = 1; } if ((x * (cnt - 1)) % k === 0) { ans = Math.max(ans, cnt); } } return ans; }