Skip to main content
Talentd

Longest Resilient Subarray II - Solution & Explanation

Medium10 min read
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You get an array and must return the length of the longest contiguous subarray that satisfies the resilience condition. The condition has to hold for the whole window, so every candidate must be checked against all of its elements.

Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)

Fix a start index i and an end index j, then validate the subarray nums[i..j] from scratch. Track the maximum valid length. This is the direct translation of the problem statement and it is correct for any validity rule. It is too slow once n reaches the 10^5 range because you repeat work for every pair of endpoints. Use it to confirm your understanding of the condition, not as a final answer.

Approach 2: Brute Force with Incremental Validation (O(n^2) time, O(1) space)

Keep the start index fixed and extend the end index one element at a time. Update the window state in O(1) per step (counts, running min or max, or whatever the condition needs) instead of rescanning. Stop extending once the window becomes invalid for that start. This removes the inner validation loop, but you still visit O(n^2) pairs in the worst case.

Approach 3: Sliding Window / Two Pointers (O(n) time, O(1) or O(k) space)

Use two pointers, left and right, that only move forward. Expand right and add nums[right] to the window state. While the window violates the condition, advance left and remove nums[left] from the state. After each step, record right - left + 1 as a candidate. This works because validity is monotone: if a window is valid, every sub-window of it is valid too, so a left pointer never needs to move backward. Each element enters and leaves the window at most once, which gives O(n) total work. Prefer this approach whenever the condition can be updated in O(1) on insert and removal. The state is typically a frequency map or a few scalar counters, so the extra space stays small.

Recommended for interviews: Start by describing the brute force so the interviewer sees you understand the condition. Then move to the sliding window and explain why the left pointer is monotone. The brute force shows understanding, but the O(n) sliding window shows the skill they are testing. Make sure you can justify the window update and shrink steps out loud before writing code.

Related practice: sliding window, two pointers, and arrays.

Solution

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 rcdot(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 cnt its current length. A run of length 1 is always resilient, because the remaining sum is 0. Whenever

$ rcdot(cnt-1)\equiv 0\pmod{k},

the prefix of length cnt is resilient, and the answer is updated with cnt. Both r and 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 nums$.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(n^3)O(1)Small inputs or verifying the condition
Brute Force with Incremental ValidationO(n^2)O(1)Medium inputs when the window state is easy to update
Sliding Window / Two PointersO(n)O(1) or O(k)General case and interview answer for large n

Video Solutions (4)

Leetcode 4076 | Leetcode 4075 | Longest Resilient Subarray II | Leetcode biweekly contest 193

CodeWithMeGuys17:41743 views
Video 1 of 4

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Longest Resilient Subarray II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Resilient Subarray I