Skip to content

4076. Longest Resilient Subarray II

DifficultyMedium

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 <= 105
  • 1 <= nums[i] <= 105
  • 1 <= 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}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
}

Comments