Longest Subarray Divisible by K with At Most One Negation II solution and explanation
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 <= 105-105 <= nums[i] <= 1051 <= k <= 3000
Approach overview
Problem Overview: You get an integer array and an integer K. Find the longest contiguous subarray whose sum is divisible by K, where you may negate at most one element inside that subarray. The problem combines the classic divisible-subarray pattern with a single sign flip, which changes the remainder you need to track.
Approach 1: Brute Force Over All Subarrays (O(n^2) time, O(1) space)
Fix a start index and extend the end index one element at a time, keeping a running sum. For each subarray, check whether the plain sum is divisible by K. Then check whether flipping one element gives a sum divisible by K. Flipping element x changes the sum by -2x, so you can test each candidate in constant time per element if you track the best flip for the current window. This is correct and easy to reason about, but it does O(n^2) work. It is only practical for small inputs. Use it to verify your logic on examples before optimizing.
Approach 2: Prefix Sums with Hash Map on Remainders (O(n) time, O(n) space)
Build prefix sums and work with their remainders modulo K. For a subarray without a flip, two prefix sums with the same remainder mean the subarray between them is divisible by K. Store the earliest index for each remainder in a hash map, so each lookup gives the longest candidate ending at the current position. To handle the single negation, keep a second layer of state: whether a flip has been used so far, and the remainder adjusted by the flipped element's contribution. Each position updates a constant number of map entries, so the whole scan is linear. This is the approach that scales to the input limits, and it is the one to present in interviews.
Recommended for interviews: Start by describing the brute force and its O(n^2) cost. That shows you understand the subarray structure. Then move to prefix sums with remainder tracking and state for the negation. Interviewers look for the prefix-remainder insight and for clean handling of the one-flip state. The brute force shows understanding, but the O(n) prefix solution shows skill. Related topics: prefix sum, hash table, and array.
Solution
Thinking
ncan be10^5. Enumerating the negated index and scanning prefix sums for each choice, as in the previous problem, takesO(n^2)and does not finish in time. Herek\le 3000, so there are only that many residues.A subarray sum modulo
kis the right prefix minus the left prefix. Negating an elementxdecreases that difference by2x, so the right residue equals the left residue plus2(xbmod k). Each left residue needs only its earliest prefix; a later index produces a shorter subarray.Those earliest indices are handled in the order they appear. While scanning the right end, the current element supplies the residue used for negation, and every left residue that can already cover it and has not been recorded for this residue is written onto the target residue. Each pair of residues is written once, and the smallest left end stored for the right residue is the longest valid subarray ending there.
Let p[0]=0 and p[i+1]=(p[i]+nums[i])bmod k. The sum of nums[L..R] is p[R+1]-p[L] modulo k. Negating nums[t] inside it, with a=nums[t]bmod k, decreases the sum by 2nums[t]. The subarray is valid when some t\in[L,R] satisfies
$
p[R+1]\equiv p[L]+2a\pmod{k},
and it is also valid with no negation when p[R+1]\equiv p[L]. The length is (R+1)-L, so a fixed right end wants the smallest left end.
first[q] is the first prefix index whose residue is q. Sort the residues that occur by first into order. best[s] stores the smallest left end currently known for a right prefix of residue s. It starts as first[s], or as a sentinel when that residue has not occurred. The initial values cover the case with no negation.
Scan index i from left to right and let a=nums[i]bmod k. A pointer remembers how far each residue a has walked through order. Every residue q with first[q]\le i can include position i, so set
t=(q+2a)bmod k,\qquad best[t]=min(best[t],first[q]).
After negating index i, a subarray that starts at first[q] and ends at any later right end of residue t is valid. The pointer only moves forward, so each pair (a,q) is handled once. Later right ends still contain i, and best keeps the smallest left end.
Let s=p[i+1]. When best[s] is not the sentinel, update the answer with i+1-best[s]. Negative values are reduced into [0,k).
The time complexity is O(n+k^2) and the space complexity is O(n+k)$.
class Solution:
def longestSubarray(self, nums: list[int], k: int) -> int:
n = len(nums)
p = [0] * (n + 1)
for i in range(n):
p[i + 1] = (p[i] + nums[i]) % k
first = [-1] * k
for i in range(n + 1):
if first[p[i]] == -1:
first[p[i]] = i
order = [q for q in range(k) if first[q] != -1]
order.sort(key=lambda q: first[q])
pos = [0] * k
best = [x if x != -1 else n + 1 for x in first]
ans = 0
for i, x in enumerate(nums):
a = x % k
while pos[a] < len(order) and first[order[pos[a]]] <= i:
q = order[pos[a]]
pos[a] += 1
t = (q + 2 * a) % k
best[t] = min(best[t], first[q])
s = p[i + 1]
if best[s] != n + 1:
ans = max(ans, i + 1 - best[s])
return ansclass Solution {
public int longestSubarray(int[] nums, int k) {
int n = nums.length;
int[] p = new int[n + 1];
for (int i = 0; i < n; ++i) {
p[i + 1] = (p[i] + nums[i]) % k;
if (p[i + 1] < 0) {
p[i + 1] += k;
}
}
int[] first = new int[k];
Arrays.fill(first, -1);
for (int i = 0; i <= n; ++i) {
if (first[p[i]] == -1) {
first[p[i]] = i;
}
}
Integer[] order = new Integer[k];
int m = 0;
for (int q = 0; q < k; ++q) {
if (first[q] != -1) {
order[m++] = q;
}
}
Arrays.sort(order, 0, m, (a, b) -> Integer.compare(first[a], first[b]));
int[] pos = new int[k];
int[] best = new int[k];
Arrays.fill(best, Integer.MAX_VALUE);
for (int q = 0; q < k; ++q) {
if (first[q] != -1) {
best[q] = first[q];
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
int a = nums[i] % k;
if (a < 0) {
a += k;
}
while (pos[a] < m && first[order[pos[a]]] <= i) {
int q = order[pos[a]++];
int t = (q + 2 * a) % k;
best[t] = Math.min(best[t], first[q]);
}
int s = p[i + 1];
if (best[s] != Integer.MAX_VALUE) {
ans = Math.max(ans, i + 1 - best[s]);
}
}
return ans;
}
}class Solution {
public:
int longestSubarray(vector<int>& nums, int k) {
int n = nums.size();
vector<int> p(n + 1);
for (int i = 0; i < n; ++i) {
p[i + 1] = (p[i] + nums[i]) % k;
if (p[i + 1] < 0) {
p[i + 1] += k;
}
}
vector<int> first(k, -1);
for (int i = 0; i <= n; ++i) {
if (first[p[i]] == -1) {
first[p[i]] = i;
}
}
vector<int> order;
for (int q = 0; q < k; ++q) {
if (first[q] != -1) {
order.push_back(q);
}
}
ranges::sort(order, [&](int a, int b) {
return first[a] < first[b];
});
vector<int> pos(k);
vector<int> best(k, INT_MAX);
for (int q = 0; q < k; ++q) {
best[q] = first[q] == -1 ? INT_MAX : first[q];
}
int ans = 0;
for (int i = 0; i < n; ++i) {
int a = nums[i] % k;
if (a < 0) {
a += k;
}
while (pos[a] < order.size() && first[order[pos[a]]] <= i) {
int q = order[pos[a]++];
int t = (q + 2 * a) % k;
best[t] = min(best[t], first[q]);
}
int s = p[i + 1];
if (best[s] != INT_MAX) {
ans = max(ans, i + 1 - best[s]);
}
}
return ans;
}
};function longestSubarray(nums: number[], k: number): number {
const n = nums.length;
const p = new Array<number>(n + 1).fill(0);
for (let i = 0; i < n; ++i) {
p[i + 1] = (p[i] + nums[i]) % k;
if (p[i + 1] < 0) {
p[i + 1] += k;
}
}
const first = new Array<number>(k).fill(-1);
for (let i = 0; i <= n; ++i) {
if (first[p[i]] === -1) {
first[p[i]] = i;
}
}
const order = Array.from({ length: k }, (_, q) => q).filter(q => first[q] !== -1);
order.sort((a, b) => first[a] - first[b]);
const pos = new Array<number>(k).fill(0);
const best = first.map(x => (x === -1 ? n + 1 : x));
let ans = 0;
for (let i = 0; i < n; ++i) {
let a = nums[i] % k;
if (a < 0) {
a += k;
}
while (pos[a] < order.length && first[order[pos[a]]] <= i) {
const q = order[pos[a]++];
const t = (q + 2 * a) % k;
best[t] = Math.min(best[t], first[q]);
}
const s = p[i + 1];
if (best[s] !== n + 1) {
ans = Math.max(ans, i + 1 - best[s]);
}
}
return ans;
}func longestSubarray(nums []int, k int) int {
n := len(nums)
p := make([]int, n+1)
for i := 0; i < n; i++ {
p[i+1] = (p[i] + nums[i]) % k
if p[i+1] < 0 {
p[i+1] += k
}
}
first := make([]int, k)
for i := range first {
first[i] = -1
}
for i := 0; i <= n; i++ {
if first[p[i]] == -1 {
first[p[i]] = i
}
}
order := make([]int, 0, k)
for q := 0; q < k; q++ {
if first[q] != -1 {
order = append(order, q)
}
}
slices.SortFunc(order, func(a, b int) int {
return first[a] - first[b]
})
pos := make([]int, k)
best := make([]int, k)
for q := 0; q < k; q++ {
if first[q] == -1 {
best[q] = int(^uint(0) >> 1)
} else {
best[q] = first[q]
}
}
ans := 0
for i, x := range nums {
a := x % k
if a < 0 {
a += k
}
for pos[a] < len(order) && first[order[pos[a]]] <= i {
q := order[pos[a]]
pos[a]++
t := (q + 2*a) % k
best[t] = min(best[t], first[q])
}
s := p[i+1]
if best[s] != int(^uint(0)>>1) {
ans = max(ans, i+1-best[s])
}
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Over Subarrays | O(n^2) | O(1) | Small inputs or verifying correctness |
| Prefix Sums with Hash Map (remainder + negation state) | O(n) | O(n) | General case and interview-optimal solution |
Frequently asked questions
Is Longest Subarray Divisible by K with At Most One Negation II easy or hard?
It is rated Hard, with an acceptance rate of about 24.1 percent. The difficulty comes from combining the prefix-remainder technique with the single negation state, which requires tracking more than one value per position.
How to solve Longest Subarray Divisible by K with At Most One Negation II in O(n)?
Compute prefix sums and their remainders modulo K. Store the first index where each remainder appears in a hash map. For each position, look up the matching remainder to get the longest valid subarray, and keep a separate state for whether the one allowed negation has been used.
Longest Subarray Divisible by K with At Most One Negation II Python/Java solution?
Use prefix sums with a hash map keyed by remainder and negation state. In Python, a dict maps each remainder to its first index. In Java, use a HashMap or an array of size K for each state. Both run in O(n) time and O(n) space. FleetCode provides solutions in Python, Java, C++, Go, and TypeScript.
What is the best approach for Longest Subarray Divisible by K with At Most One Negation II?
The best approach is prefix sums combined with a hash map that stores the earliest index for each remainder modulo K. Track one extra state for whether the single negation has been used. This runs in O(n) time with O(n) space.
Is Longest Subarray Divisible by K with At Most One Negation II asked at Google/Amazon/Meta?
FleetCode does not have verified company-specific frequency data for this problem. It is tagged with Array, Hash Table, Binary Search, and Prefix Sum, which are common in hard interview rounds at large tech companies.
What data structure is used in Longest Subarray Divisible by K with At Most One Negation II?
The main data structures are a hash map, which stores the earliest index for each prefix remainder, and a prefix sum array. The problem is tagged with Binary Search as well, which applies when you need to query sorted indices per remainder.
What is the time complexity of Longest Subarray Divisible by K with At Most One Negation II?
The optimal solution runs in O(n) time, since you scan the array once and perform constant hash map operations per element. The brute force over all subarrays runs in O(n^2) time with O(1) extra space.