Skip to main content
Talentd

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

Approach Overview

Problem Overview: You get an integer array and must return the length of the longest contiguous subarray that meets the resilience condition defined in the problem statement. The answer is a single length, and the subarray must be contiguous, so you cannot skip elements.

Approach 1: Brute Force Over All Subarrays (O(n^2) to O(n^3))

Fix a start index, extend the end index one element at a time, and check the condition on each candidate window. Track the maximum valid length. The check itself is what drives the cost: if you recompute it from scratch for every window, you get O(n^3). If you maintain the check incrementally as you extend the end, you get O(n^2). Space is O(1) because you only store the running maximum and a few variables. Use this to confirm you understand the condition before optimizing.

Approach 2: Sliding Window with Two Pointers (O(n) time, O(1) space)

Maintain a window [left, right] and expand right on every step. When the window becomes invalid, advance left until it is valid again. Each index enters and leaves the window at most once, so the total work is linear. The key condition is that validity is preserved when you shrink the window: if a subarray is valid, every sub-window you get by removing elements from the ends is also valid. That property is what makes it safe to discard the left element without re-checking everything. Prefer this approach whenever the condition can be updated in O(1) per add or remove, such as with running counts, sums, or min and max values. Store those aggregates as variables so the window update stays constant time. See sliding window and two pointers for the pattern in more depth.

Recommended for interviews: Start with the brute force to show you understand the condition, then move to the sliding window. Interviewers expect the O(n) version. The brute force shows understanding, but the sliding window with O(1) updates shows skill. Explain why shrinking the window from the left is valid before you write code. That justification is what interviewers check for. Common mistakes include forgetting to update the aggregate when removing the left element and returning the window size before the window is valid. For more array practice, see arrays.

Solution

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 sum-a_i to be divisible by k at every index means every a_i is congruent to 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 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. 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, full recheck per windowO(n^3)O(1)Small inputs or verifying the condition
Brute force, incremental checkO(n^2)O(1)When the condition extends cheaply per element
Sliding window with two pointersO(n)O(1)General case when validity is preserved under shrinking

Video Solutions (5)

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

CodeWithMeGuys17:41760 views
Video 1 of 5

Frequently Asked Questions

Is Longest Resilient Subarray I easy or hard?
It is rated Medium with an acceptance rate of about 35.3%. The difficulty comes from identifying that the sliding window is valid and maintaining the condition's state correctly during shrinking.
Longest Resilient Subarray I Python solution?
Use two pointers. Loop over the array with right as the index, update your aggregate with nums[right], and while the window is invalid, subtract nums[left] from the aggregate and increment left. Update the answer with right - left + 1 after each step. Java and C++ follow the same structure.
How to solve Longest Resilient Subarray I in O(n)?
Keep a window with left and right pointers and maintain the condition's aggregate, such as a count or running value, as you move the right pointer. When the window becomes invalid, advance the left pointer and update the aggregate for the removed element. Record the maximum window length after each step.
What is the best approach for Longest Resilient Subarray I?
The best approach is a sliding window with two pointers. Expand the right pointer on each step, and move the left pointer forward only when the window becomes invalid. This runs in O(n) time and O(1) space.
What data structure is used in Longest Resilient Subarray I?
The main solution uses only integer variables such as left and right indices and a running aggregate, so no extra data structure is required. A hash map or frequency array can be used if the condition depends on element counts.
What is the time complexity of Longest Resilient Subarray I?
The optimal solution runs in O(n) time because each index enters and leaves the window at most once. A brute force solution that checks every subarray takes O(n^2) or O(n^3) time depending on how the condition is verified.
Is Longest Resilient Subarray I asked at Google, Amazon, or Meta?
The problem's tags on FleetCode are listed as General, so company tagging is not confirmed from this data. Check the company filter on your platform of choice for the latest reports before you plan around a specific interview loop.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Longest Resilient Subarray II