Max After m Range Increments

Problem Overview

Start with an array of n zeros and apply m updates that add k[i] on every index in [a[i], b[i]].

Intuition

Start with an array of n zeros and apply m updates that add k[i] on every index in [a[i], b[i]]. Touching each range naively is too slow. A difference array marks +k at the start and -k just after the end so one prefix-sum pass materializes all final values and the maximum among them.

Algorithm

1Allocate diff of size n+1 initialized to 0.
2For each operation i: diff[a[i]] += k[i]; diff[b[i]+1] -= k[i].
3Scan i = 0..n-1: curr += diff[i]; track res = max(res, curr).
4Return res.

Example Walkthrough

Input: n = 5, a = [0, 1], b = [2, 4], k = [100, 100]

1. After marks: +100 at 0, -100 at 3; +100 at 1, -100 at 5.
2. Prefix: 100, 200, 200, 100, 100.
3. Maximum is 200.

Output: 200

Common Pitfalls

• Need size n+1 so the end+1 decrement is in bounds when b[i] = n-1.
• Only walk the first n positions when taking the prefix max - index n is a sentinel.
• Indices a[i], b[i] are 0-based inclusive ranges.
• Do not loop each range element-by-element - that is O(m*n) and will TLE.

Max After m Range Increments.java

Java


class Solution {

    // Approach: Difference array for m range adds on an n-length zero array.
    // For each [a[i], b[i]] add k[i]: mark +k at a[i] and -k at b[i]+1. Prefix
    // sum reconstructs final values; track the maximum along the way.
    // Complexity: O(m + n) time and O(n) space.
    public int findMax(int n, int[] a, int[] b, int[] k) {
        int m = a.length;
        int[] arr = new int[n + 1];

        for (int i = 0; i < m; i++) {
            int start = a[i], end = b[i], add = k[i];
            arr[start] += add;
            arr[end + 1] -= add;
        }

        int res = 0, curr = 0;
        for (int i = 0; i < n; i++) {
            curr += arr[i];
            res = Math.max(res, curr);
        }
        return res;
    }
}

Was this solution helpful?