Welcome to Subscribe On Youtube

4075. Longest Resilient Subarray I

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 <= 2500
  • 1 <= nums[i] <= 105
  • 1 <= k <= 105

Solutions

Solution 1: Congruent Runs

Thinking

A subarray can be as long as $2500$. Enumerating every interval and then checking the sum after each deletion is cubic, which is too much for this limit.

Requiring $\textit{sum}-a_i$ to be divisible by $k$ at every index means every $a_i$ is congruent to $\textit{sum}$ modulo $k$. All elements in the subarray therefore share one residue $r$, and the length $L$ must also satisfy $(L-1)r\equiv 0\pmod{k}$.

Equal residues form contiguous runs. Inside a run the length grows by $1$, and the condition depends only on that length and $r$, so one pass over each run records every feasible length.

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}$. 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 (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 (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 x*(cnt-1)%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;
    }
    
    

All Problems

All Solutions