Skip to content

4064. Longest Subarray Divisible by K with At Most One Negation II

DifficultyHard

Description

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 by k = 3.
  • Negating nums[2] = 2 changes the sum to 4 + 1 − 2 = 3, which is divisible by k.
  • 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 by k = 7 without 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] <= 105
  • 1 <= k <= 3000​​​​​​​

Solutions

Solution 1: Prefix Sums

Thinking

\(n\) can be \(10^5\). Enumerating the negated index and scanning prefix sums for each choice, as in the previous problem, takes \(O(n^2)\) and does not finish in time. Here \(k\le 3000\), so there are only that many residues.

A subarray sum modulo \(k\) is the right prefix minus the left prefix. Negating an element \(x\) decreases that difference by \(2x\), so the right residue equals the left residue plus \(2(x\bmod 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]+\textit{nums}[i])\bmod k\). The sum of \(\textit{nums}[L..R]\) is \(p[R+1]-p[L]\) modulo \(k\). Negating \(\textit{nums}[t]\) inside it, with \(a=\textit{nums}[t]\bmod k\), decreases the sum by \(2\textit{nums}[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.

\(\textit{first}[q]\) is the first prefix index whose residue is \(q\). Sort the residues that occur by \(\textit{first}\) into \(\textit{order}\). \(\textit{best}[s]\) stores the smallest left end currently known for a right prefix of residue \(s\). It starts as \(\textit{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=\textit{nums}[i]\bmod k\). A pointer remembers how far each residue \(a\) has walked through \(\textit{order}\). Every residue \(q\) with \(\textit{first}[q]\le i\) can include position \(i\), so set

\[ t=(q+2a)\bmod k,\qquad \textit{best}[t]=\min(\textit{best}[t],\textit{first}[q]). \]

After negating index \(i\), a subarray that starts at \(\textit{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 \(\textit{best}\) keeps the smallest left end.

Let \(s=p[i+1]\). When \(\textit{best}[s]\) is not the sentinel, update the answer with \(i+1-\textit{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)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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 ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class 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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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;
}

Comments