Is Longest Resilient Subarray II easy or hard?

It is a medium difficulty problem with a 55.7% acceptance rate. The brute force is straightforward, but the O(n) sliding window requires you to see that validity is monotone and to update the window state correctly on removal. Most difficulty comes from getting the shrink condition right.

Longest Resilient Subarray II Python solution?

A Python solution uses two indices, a loop over the right pointer, and an inner while loop that moves the left pointer until the window is valid again. Store the state in a dict or a few variables, update it on each add and remove, and track the max of right - left + 1. The complexity is O(n) time and O(1) or O(k) space.

How to solve Longest Resilient Subarray II in O(n)?

Keep a window [left, right] and a small state that describes it, such as counts or running extremes. Add nums[right] to the state, then shrink from the left while the window violates the condition. Record the window length after each step and return the maximum. The key property is that a valid window's sub-windows are also valid, so the left pointer only moves forward.

What is the best approach for Longest Resilient Subarray II?

The best approach is a sliding window with two pointers. Expand the right pointer, update the window state, and move the left pointer forward while the window is invalid. This runs in O(n) time because each element enters and leaves the window at most once.

What data structure is used in Longest Resilient Subarray II?

The solution uses an array for input and a small window state for tracking validity. Depending on the condition, that state is a hash map of frequencies, a few integer counters, or a running min and max. The window itself is represented by two integer indices, so no extra array copies are needed.

What is the time complexity of Longest Resilient Subarray II?

The optimal sliding window solution runs in O(n) time, where n is the array length. The brute force enumeration runs in O(n^3) time, and an incremental brute force runs in O(n^2) time. Only the sliding window fits comfortably within limits for large n.

Is Longest Resilient Subarray II asked at Google, Amazon, or Meta?

This problem is tagged as a general array and sliding window question on FleetCode. Company-specific frequency data is not confirmed for this problem. Sliding window problems of this difficulty appear often in interviews at Google, Amazon, and Meta, so the pattern is worth practicing.

4076. Longest Resilient Subarray II - Practice Online

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 <= 10⁵
1 <= nums[i] <= 10⁵
1 <= k <= 10⁵