Longest Subarray Divisible by K with At Most One Negation I solution and explanation
4 more videos on this problem
Leetcode 4063 | Longest Subarray Divisible by K with At Most One Negation I | biweekly contest 192CodeWithMeGuys · 12:55 · 238 views
Longest Subarray Divisible by K with At Most One Negation II | Maths + Prefix Map + Binary SearchManjeet Dhayal · 10:17 · 88 views
Longest Subarray Divisible by K with At Most One Negation I | Prefix + HashMap | LeetCode 4063Manjeet Dhayal · 7:04 · 65 views
LeetCode 4063 | Longest Subarray Divisible by K with At Most One Negation I | JavaCode Kage · 17:41 · 55 views
4063. Longest Subarray Divisible by K with At Most One Negation IAnurag Sharma · 7:36 · 50 views
The problem
You are given an integer array nums and an integer k.
A subarray is valid if its sum is divisible by k, or can become divisible by k by negating one element within that subarray.
Negating an element means replacing its value x with -x.
Return the length of the longest valid subarray. If no valid subarray exists, return 0.
A subarray is a contiguous, non-empty sequence of elements within an array.
Example 1:
Input: nums = [4,1,2], k = 3
Output: 3
Explanation:
- The sum of the entire array is 7, and
7 % 3 = 1, so it is not divisible byk = 3. - Negating
nums[2] = 2changes the sum to4 + 1 − 2 = 3, which is divisible byk. - Therefore, the entire array is a valid subarray, giving a length of 3.
Example 2:
Input: nums = [5,3,4], k = 7
Output: 2
Explanation:
- The sum of the entire array is 12, and negating any one of its elements does not make its sum divisible by 7.
- However, the subarray
[3, 4]has a sum of 7, which is divisible byk = 7without any negation. - Therefore, the longest valid subarray has a length of 2.
Example 3:
Input: nums = [2,2,5], k = 6
Output: 2
Explanation:
- The sum of the entire array is 9, and negating any one of its elements does not make its sum divisible by 6.
- The subarray
[2, 2]has a sum of 4. Negating either element changes it to[-2, 2]or[2, -2], both of which have a sum of 0. - Therefore, the longest valid subarray has a length of 2.
Constraints:
1 <= nums.length <= 1000-105 <= nums[i] <= 1051 <= k <= 105
Approach overview
Problem Overview: Given an integer array nums and an integer k, find the longest contiguous subarray whose sum is divisible by k, where you may negate at most one element in that subarray before summing.
Approach 1: Brute Force Over All Subarrays (O(n^3) time, O(1) space)
Fix a left endpoint l and extend the right endpoint r, keeping a running sum S of the original values. A subarray is valid if S mod k == 0 without any negation, or if some index j in [l, r] satisfies (S - 2 * nums[j]) mod k == 0, which is the sum after flipping nums[j]. Checking every j for every subarray costs a full scan each time, so the total is cubic. Use this to confirm the math on small inputs, not as a submission.
Approach 2: Enumerate the Negated Index with Prefix Sums and a Hash Map (O(n^2) time, O(n) space)
Run one pass per possible negated index i, plus one pass with no negation. For each pass, flip nums[i] and walk the array while maintaining a prefix sum taken modulo k. Normalize negative remainders with ((x % k) + k) % k. A subarray (a, b] has a sum divisible by k exactly when the prefix remainders at a and b match. Store the first index where each remainder appears in a hash map. At each position b, the candidate length is b - first[remainder]. Because only the first occurrence matters for maximizing length, each pass is linear. The outer loop over negated indices makes the total O(n^2). The map holds at most min(n + 1, k) entries, so space is O(n) in the worst case.
This works because a subarray that does not contain index i is unaffected by the flip, and a subarray that does contain it sees exactly one negation. Taking the maximum across all passes covers every subarray with at most one negation.
Recommended for interviews: Interviewers expect you to start with the brute force to show you understand what "at most one negation" means in terms of sums. The enumerate-and-hash approach is what demonstrates skill. Explain why prefix remainders reduce subarray divisibility to a equality check, and why first occurrences give the longest valid window. Mention the negative modulo normalization explicitly, since it is a common source of wrong answers.
Related topics: array, hash table, prefix sum.
Solution
Thinking
A subarray sum is divisible by
kexactly when the prefix sums at its two ends are congruent modulok. Enumerating every subarray and then every element inside it is aboutO(n^3). Sincen\le 1000, the search has to drop an order of magnitude.Negating
xdecreases the sum of every subarray that contains it by2x, and leaves every other subarray unchanged. There arenchoices for the negated index, plus the choice of negating nothing. Each choice only needs the longest subarray whose sum is divisible byk.Each prefix residue modulo
kkeeps the first index where it appears. Meeting that residue again makes an earlier left end a longer subarray. A subarray that misses the negated index was already counted on the original array.
After nums[i] is negated, every subarray that contains index i loses 2timesnums[i], and every subarray that misses i keeps its sum. Run the divisible-subarray search on the original array and again after negating each index in turn. The answer is the maximum of those lengths.
The scan keeps the prefix sum modulo k, with the residue folded into [0, k). Each residue keeps the first index where it appears, and residue 0 starts at index -1. At index i, if the current residue was seen at index j, then the sum of nums[j+1..i] is divisible by k and the length is i-j. Python, Java, Go, and TypeScript store those indices in a hash map. C++ uses an array of length k, indexed by the residue, and passes the negated index as a parameter.
The time complexity is O(n^2) and the space complexity is O(n). C++ resets that array on every scan, so its time complexity is O(n(n+k)) and its space complexity is O(k).
class Solution:
def longestSubarray(self, nums: list[int], k: int) -> int:
def f(nums: list[int], k: int) -> int:
d = {0: -1}
s = res = 0
for i, x in enumerate(nums):
s = (s + x) % k
if s in d:
res = max(res, i - d[s])
else:
d[s] = i
return res
ans = f(nums, k)
for i, x in enumerate(nums):
nums[i] = -x
ans = max(ans, f(nums, k))
nums[i] = x
return ansclass Solution {
public int longestSubarray(int[] nums, int k) {
int ans = f(nums, k);
for (int i = 0; i < nums.length; ++i) {
nums[i] = -nums[i];
ans = Math.max(ans, f(nums, k));
nums[i] = -nums[i];
}
return ans;
}
private int f(int[] nums, int k) {
Map<Integer, Integer> d = new HashMap<>();
d.put(0, -1);
int s = 0, res = 0;
for (int i = 0; i < nums.length; ++i) {
s = ((s + nums[i]) % k + k) % k;
if (d.containsKey(s)) {
res = Math.max(res, i - d.get(s));
} else {
d.put(s, i);
}
}
return res;
}
}class Solution {
public:
int longestSubarray(vector<int>& nums, int k) {
int n = nums.size();
vector<int> d(k, -2);
auto f = [&](int skip) {
fill(d.begin(), d.end(), -2);
d[0] = -1;
int s = 0, res = 0;
for (int i = 0; i < n; ++i) {
int x = i == skip ? -nums[i] : nums[i];
s = (s + x) % k;
if (s < 0) {
s += k;
}
if (d[s] != -2) {
res = max(res, i - d[s]);
} else {
d[s] = i;
}
}
return res;
};
int ans = f(-1);
for (int i = 0; i < n; ++i) {
ans = max(ans, f(i));
}
return ans;
}
};function longestSubarray(nums: number[], k: number): number {
const f = (nums: number[]): number => {
const d = new Map<number, number>([[0, -1]]);
let s = 0,
res = 0;
for (let i = 0; i < nums.length; ++i) {
s = (s + nums[i]) % k;
if (s < 0) {
s += k;
}
if (d.has(s)) {
res = Math.max(res, i - d.get(s)!);
} else {
d.set(s, i);
}
}
return res;
};
let ans = f(nums);
for (let i = 0; i < nums.length; ++i) {
nums[i] = -nums[i];
ans = Math.max(ans, f(nums));
nums[i] = -nums[i];
}
return ans;
}func longestSubarray(nums []int, k int) int {
f := func(nums []int) int {
d := map[int]int{0: -1}
s, res := 0, 0
for i, x := range nums {
s = (s + x) % k
if s < 0 {
s += k
}
if j, ok := d[s]; ok {
res = max(res, i-j)
} else {
d[s] = i
}
}
return res
}
ans := f(nums)
for i, x := range nums {
nums[i] = -x
ans = max(ans, f(nums))
nums[i] = x
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Over All Subarrays | O(n^3) | O(1) | Verifying logic on tiny inputs |
| Enumerate Negated Index with Prefix Sum Hash Map | O(n^2) | O(n) | General case and interview solution |
Frequently asked questions
Is Longest Subarray Divisible by K with At Most One Negation I easy or hard?
It is rated Medium with an acceptance rate of about 34.2%. The hard part is reducing the one-negation constraint to a flip-and-rescan pattern and handling negative remainders correctly. Once you see the enumerate-the-flip idea, the implementation is a standard prefix-sum hash map loop.
How to solve Longest Subarray Divisible by K with At Most One Negation I in O(n^2)?
Loop over each index i and flip nums[i]. For each flipped array, compute prefix sums modulo k with normalized negative remainders, and store the first index of each remainder in a hash map. At each position, update the answer with the current index minus the first index stored for the same remainder. Also run one pass with no flip.
Longest Subarray Divisible by K with At Most One Negation I Python and Java solution?
Both Python and Java solutions use the same logic: loop over the negated index, compute prefix remainders with a dictionary or HashMap, and track the maximum length. In Python, normalize remainders with (x % k + k) % k, since Python's modulo already returns non-negative results for positive k but Java's does not. Java needs the explicit normalization.
What is the best approach for Longest Subarray Divisible by K with At Most One Negation I?
The best approach is to enumerate each possible negated index, plus one pass with no negation, and run a prefix-sum scan with a hash map of first occurrences of each remainder modulo k. This runs in O(n^2) time with O(n) space. It is the approach available on FleetCode in Python, Java, C++, and Go.
What data structure is used in Longest Subarray Divisible by K with At Most One Negation I?
The solution uses a hash map to store the earliest prefix-sum remainder modulo k, and a running prefix sum over the array. The outer enumeration over negated indices is a plain loop. No heap, tree, or graph structure is needed.
What is the time complexity of Longest Subarray Divisible by K with At Most One Negation I?
The enumerate-and-hash approach runs in O(n^2) time because each of the n possible negated indices triggers a linear prefix-sum scan. The brute force over all subarrays is O(n^3). Space is O(n) for the hash map of remainders.
Is Longest Subarray Divisible by K with At Most One Negation I asked at Google, Amazon, or Meta?
The problem tags on FleetCode are Array, Hash Table, and Prefix Sum, but company-specific frequency data is not listed here. Check recent interview reports on company-tagged question lists for current information. The prefix sum and hash map pattern it uses appears across many interview problems.