Difference Array

Arrays & StringsPriority 3 of 5 — Worth knowing — usually a variant of a must-know patternWorth knowing Updated Sep 18, 2026
Section priorityPriority 5 of 5 — Must know — expect it in almost every loopMust knowPriority 4 of 5 — High value — a gap here costs you roundsHigh valuePriority 3 of 5 — Worth knowing — usually a variant of a must-know patternWorth knowingPriority 2 of 5 — Niche — read once, revisit only if a company is known to askNicheMarked on the sections that carry it — unmarked sections are background/reference.

Scope — O(1) range update, O(n) rebuild — the inverse of a prefix sum. See also: prefix_sum.md — the forward direction; scanning_line.md — the event-sorted version for sparse coordinates; intervals.md — merging rather than accumulating.

LeetCode Problem Lists

Overview

Difference Array is a technique for efficiently performing range update operations on an array. Instead of updating each element individually (O(n) per update), we can perform range updates in O(1) time and reconstruct the final array in O(n) time.

Key Properties

  • Time Complexity:
    • Range Update: O(1)
    • Build Difference Array: O(n)
    • Reconstruct Original: O(n)
    • Multiple Updates: O(m) for m updates
  • Space Complexity: O(n) for storing difference array
  • Core Idea: Store differences between consecutive elements to enable efficient range updates
  • When to Use: Multiple range update operations, interval modifications, booking systems, resource allocation

References

Problem Categories

Pattern 1: Basic Range Updates

  • Description: Add/subtract a value to all elements in a range
  • Recognition: “Update range [i, j]”, “increment by val”, “modify interval”
  • Examples: LC 370, LC 1109, LC 1893
  • Template: Use Basic Difference Array Template

Pattern 2: Resource Allocation

  • Description: Track resource usage across intervals
  • Recognition: “Booking”, “capacity”, “overlapping intervals”
  • Examples: LC 1094, LC 731, LC 732
  • Template: Use Resource Tracking Template

Pattern 3: Event Timeline

  • Description: Process events happening at different times
  • Recognition: “Start/end times”, “scheduling”, “timeline”
  • Examples: LC 253, LC 1851, LC 2021
  • Template: Use Event Processing Template

Pattern 4: 2D Difference Array

  • Description: Range updates on 2D matrices
  • Recognition: “Rectangle updates”, “2D range modifications”
  • Examples: LC 2132, LC 2536
  • Template: Use 2D Difference Array Template

Pattern 5: Coverage Map + Greedy Fill (Diff Array → Prefix Sum → Greedy)

  • Description: First use a difference array to compute which positions are already covered by pre-existing intervals, then greedily fill the remaining uncovered gaps
  • Recognition: “Minimum number of X to cover everything”, “already-covered ranges given, add the fewest new ones”, “illuminate / paint / patch the whole line”
  • Examples: LC 3964 (Minimum Lights to Illuminate a Road)
  • Template: Use Coverage + Greedy Template (Template 6)

Pattern 6: Range Update + Range MAX Query (when a difference array is NOT enough) Priority 4 of 5 — High value — a gap here costs you rounds

  • Description: Same “stamp a range” shape as a difference array, but each new range must first read the current maximum over that range, then overwrite the range with a value derived from it
  • Recognition: “after each drop / insert, report the max so far”, “stack on top of whatever is already there”, the update value depends on a query over the same range
  • Why the difference array breaks down (the interview talking point):
    • A difference array is offline — stamp every range first, then one prefix-sum sweep at the end. Here updates are online: the answer after step i is needed before step i+1 is applied
    • A difference array only accumulates sums. max is not invertible, so there is no diff[end + 1] -= val that “undoes” a max
    • Escalation path: diff array → prefix sum handles add over range + read whole array once; segment tree + lazy handles assign/add over range + max/min/sum query at any time
  • Examples: LC 699 (Falling Squares)
  • Template: Use Segment Tree + Lazy Assign (Template 7) — this is the “Lazy Propagation” row promised in the Template Comparison Table below

Templates & Algorithms

Template Comparison Table

Template Type Use Case Update Time Query Time Space When to Use
Basic Difference Range updates O(1) O(n) rebuild O(n) Multiple range updates
With Prefix Sum Range updates + queries O(1) O(1) O(n) Updates and queries
2D Difference Matrix range updates O(1) O(mn) rebuild O(mn) 2D range updates
Lazy Propagation Dynamic queries O(log n) O(log n) O(n) Many queries between updates

Universal Difference Array Template

python
def difference_array_template(nums, updates):
    """
    Universal template for difference array problems
    nums: original array
    updates: list of [start, end, value] operations
    """
    n = len(nums)
    # Build difference array
    diff = [0] * n
    diff[0] = nums[0]
    for i in range(1, n):
        diff[i] = nums[i] - nums[i-1]
    
    # Apply range updates in O(1) each
    for start, end, val in updates:
        diff[start] += val
        if end + 1 < n:
            diff[end + 1] -= val
    
    # Reconstruct final array
    result = [0] * n
    result[0] = diff[0]
    for i in range(1, n):
        result[i] = result[i-1] + diff[i]
    
    return result

Template 1: Basic Difference Array

python
class DifferenceArray:
    def __init__(self, nums):
        """Initialize difference array from original array"""
        self.n = len(nums)
        self.diff = [0] * self.n
        
        # Build difference array
        self.diff[0] = nums[0]
        for i in range(1, self.n):
            self.diff[i] = nums[i] - nums[i-1]
    
    def update(self, start, end, val):
        """Add val to all elements in range [start, end] in O(1)"""
        self.diff[start] += val
        if end + 1 < self.n:
            self.diff[end + 1] -= val
    
    def get_result(self):
        """Reconstruct the final array in O(n)"""
        result = [0] * self.n
        result[0] = self.diff[0]
        for i in range(1, self.n):
            result[i] = result[i-1] + self.diff[i]
        return result

Template 2: Resource Allocation

python
def check_resource_allocation(intervals, capacity, resource_field=2):
    """
    Check if resource allocation is valid
    intervals: [[start, end, resource_needed], ...]
    capacity: maximum available resource
    """
    # Find the range of positions
    max_pos = max(interval[1] for interval in intervals) + 1
    diff = [0] * max_pos
    
    # Apply all resource allocations
    for interval in intervals:
        start, end, resource = interval[0], interval[1], interval[resource_field]
        diff[start] += resource
        if end + 1 < max_pos:
            diff[end + 1] -= resource
    
    # Check if any position exceeds capacity
    current = 0
    for i in range(max_pos):
        current += diff[i]
        if current > capacity:
            return False
    
    return True

Template 3: Event Timeline

python
def process_events(events):
    """
    Process events on a timeline
    events: [[start_time, end_time, value], ...]
    Returns: timeline with accumulated values
    """
    if not events:
        return []
    
    # Create timeline
    max_time = max(e[1] for e in events) + 1
    timeline = [0] * max_time
    
    # Process each event
    for start, end, value in events:
        timeline[start] += value
        if end + 1 < max_time:
            timeline[end + 1] -= value
    
    # Calculate prefix sum to get actual values
    for i in range(1, max_time):
        timeline[i] += timeline[i-1]
    
    return timeline

Template 4: 2D Difference Array

python
class DifferenceArray2D:
    def __init__(self, matrix):
        """Initialize 2D difference array"""
        self.m, self.n = len(matrix), len(matrix[0])
        self.diff = [[0] * self.n for _ in range(self.m)]
        
        # Build 2D difference array
        for i in range(self.m):
            for j in range(self.n):
                self.diff[i][j] = matrix[i][j]
                if i > 0:
                    self.diff[i][j] -= matrix[i-1][j]
                if j > 0:
                    self.diff[i][j] -= matrix[i][j-1]
                if i > 0 and j > 0:
                    self.diff[i][j] += matrix[i-1][j-1]
    
    def update(self, r1, c1, r2, c2, val):
        """Add val to all elements in rectangle [r1,c1] to [r2,c2]"""
        self.diff[r1][c1] += val
        if r2 + 1 < self.m:
            self.diff[r2 + 1][c1] -= val
        if c2 + 1 < self.n:
            self.diff[r1][c2 + 1] -= val
        if r2 + 1 < self.m and c2 + 1 < self.n:
            self.diff[r2 + 1][c2 + 1] += val
    
    def get_result(self):
        """Reconstruct the final 2D array"""
        result = [[0] * self.n for _ in range(self.m)]
        
        for i in range(self.m):
            for j in range(self.n):
                result[i][j] = self.diff[i][j]
                if i > 0:
                    result[i][j] += result[i-1][j]
                if j > 0:
                    result[i][j] += result[i][j-1]
                if i > 0 and j > 0:
                    result[i][j] -= result[i-1][j-1]
        
        return result

Template 5: Optimized with Coordinates Compression

python
def difference_array_compressed(updates):
    """
    Handle large coordinate space with compression
    updates: [[start, end, value], ...]
    """
    # Collect all unique points
    points = set()
    for start, end, _ in updates:
        points.add(start)
        points.add(end + 1)
    
    # Sort and create mapping
    sorted_points = sorted(points)
    point_to_idx = {p: i for i, p in enumerate(sorted_points)}
    
    # Apply updates on compressed coordinates
    n = len(sorted_points)
    diff = [0] * n
    
    for start, end, val in updates:
        start_idx = point_to_idx[start]
        end_idx = point_to_idx.get(end + 1, n)
        diff[start_idx] += val
        if end_idx < n:
            diff[end_idx] -= val
    
    # Calculate values at each point
    for i in range(1, n):
        diff[i] += diff[i-1]
    
    # Return results with original coordinates
    result = {}
    for i, point in enumerate(sorted_points[:-1]):  # Exclude the last dummy point
        if diff[i] != 0:
            result[point] = diff[i]
    
    return result

Template 6: Coverage Map + Greedy Fill (LC 3964)

python
# python — LC 3964 Minimum Lights to Illuminate a Road
#
# core idea (3 phases):
#   1. DIFF ARRAY  -> mark every range an existing bulb covers in O(1) each
#   2. PREFIX SUM  -> turn diff into a `covered[i]` map (0 == dark spot)
#   3. GREEDY      -> walk left->right; at each dark spot drop 1 new bulb and
#                     jump ahead 3 (a new bulb at i+1 lights i, i+1, i+2)
#
# time  = O(n)   diff build + prefix sum + single greedy pass
# space = O(n)   difference array + coverage map
def minLights(lights):
    n = len(lights)

    # 1) difference array (size n+1 so `right+1` never overflows)
    diff = [0] * (n + 1)
    for i, v in enumerate(lights):
        if v > 0:
            left  = max(0, i - v)
            right = min(n - 1, i + v)
            diff[left]      += 1        # +1 where coverage starts
            diff[right + 1] -= 1        # -1 right AFTER it ends

    # 2) prefix sum -> covered[i] > 0 means position i is already lit
    covered = [0] * n
    running = 0
    for i in range(n):
        running += diff[i]
        covered[i] = running

    # 3) greedy fill of the dark gaps
    ans = 0
    i = 0
    while i < n:
        if covered[i] == 0:             # dark spot found
            ans += 1
            # best move: put bulb at i+1 -> covers i, i+1, i+2 -> jump 3
            i += 3
        else:
            i += 1                      # already lit -> next position
    return ans

Alternative greedy (count dark runs): instead of the jump-by-3 loop, accumulate the length of each maximal dark run and add (run + 2) // 3 bulbs per run (ceil-divide by a bulb’s width of 3). Same O(n), avoids index juggling — see V1-2 / V2 in the solution file.

Template 7: Range Assign + Range Max (Segment Tree w/ Lazy Propagation) — LC 699

When to reach for this instead of a difference array: the moment a range update needs the current aggregate over that same range, or an answer is required between updates. Difference array = offline + additive; this = online + any associative aggregate.

Coordinate compression first. Endpoints are up to 10^8 but there are only 2n of them, so map the sorted unique endpoints to indices and let leaf i represent the half-open elementary segment [xs[i], xs[i+1]). A square on [l, l+size) becomes leaf range [idx[l], idx[l+size] - 1] — half-open input, closed leaf range, which is exactly the off-by-one the difference array end + 1 trick also guards against.

java
// java
// LC 699 - Falling Squares
// IDEA: coordinate-compress the 2n endpoints, then a segment tree with a LAZY ASSIGN tag
//       supports "max over [l,r]" and "set [l,r] = h" in O(log n) each.
//       Per square: h = query(l, r) + size; assign(l, r, h); answer = running max.
// time = O(n log n), space = O(n)
class Solution {
    private int[] mx, lz;   // mx = max height in node's range, lz = pending "assign" tag (0 = none)

    public List<Integer> fallingSquares(int[][] positions) {
        // 1) coordinate compression of all endpoints
        TreeSet<Integer> set = new TreeSet<>();
        for (int[] p : positions) { set.add(p[0]); set.add(p[0] + p[1]); }
        List<Integer> xs = new ArrayList<>(set);
        Map<Integer, Integer> idx = new HashMap<>();
        for (int i = 0; i < xs.size(); i++) idx.put(xs.get(i), i);
        int m = xs.size() - 1;                 // # of elementary segments

        mx = new int[4 * Math.max(m, 1)];
        lz = new int[4 * Math.max(m, 1)];

        List<Integer> res = new ArrayList<>();
        int best = 0;
        for (int[] p : positions) {
            // NOTE !!! square covers [l, l+size) -> closed leaf range [a, b]
            int a = idx.get(p[0]);
            int b = idx.get(p[0] + p[1]) - 1;
            int cur = query(1, 0, m - 1, a, b);        // tallest thing already under it
            update(1, 0, m - 1, a, b, cur + p[1]);     // it lands ON TOP -> assign, not add
            best = Math.max(best, cur + p[1]);
            res.add(best);
        }
        return res;
    }

    // push the pending assign tag down to both children
    private void push(int node) {
        if (lz[node] != 0) {
            for (int c = 2 * node; c <= 2 * node + 1; c++) {
                mx[c] = lz[node];
                lz[c] = lz[node];
            }
            lz[node] = 0;
        }
    }

    private void update(int node, int lo, int hi, int l, int r, int val) {
        if (r < lo || hi < l) return;                       // disjoint
        if (l <= lo && hi <= r) {                           // fully covered -> tag & stop
            mx[node] = val; lz[node] = val; return;
        }
        push(node);
        int mid = (lo + hi) >>> 1;
        update(2 * node, lo, mid, l, r, val);
        update(2 * node + 1, mid + 1, hi, l, r, val);
        mx[node] = Math.max(mx[2 * node], mx[2 * node + 1]);
    }

    private int query(int node, int lo, int hi, int l, int r) {
        if (r < lo || hi < l) return 0;
        if (l <= lo && hi <= r) return mx[node];
        push(node);
        int mid = (lo + hi) >>> 1;
        return Math.max(query(2 * node, lo, mid, l, r),
                        query(2 * node + 1, mid + 1, hi, l, r));
    }
}
python
# python
# LC 699 - Falling Squares
# IDEA: same as java — compress endpoints, segment tree with a lazy ASSIGN tag.
#       max is not invertible, so the diff-array "+val at l, -val at r+1" trick does not apply.
# time = O(n log n), space = O(n)
class Solution(object):
    def fallingSquares(self, positions):
        # 1) coordinate compression
        xs = sorted({x for l, s in positions for x in (l, l + s)})
        idx = {x: i for i, x in enumerate(xs)}
        m = len(xs) - 1                       # # of elementary segments

        size = 4 * max(m, 1)
        mx = [0] * size                       # max height in node's range
        lz = [0] * size                       # pending assign tag (0 = none)

        def push(node):
            if lz[node]:
                for c in (2 * node, 2 * node + 1):
                    mx[c] = lz[node]
                    lz[c] = lz[node]
                lz[node] = 0

        def update(node, lo, hi, l, r, val):
            if r < lo or hi < l:              # disjoint
                return
            if l <= lo and hi <= r:           # fully covered -> tag & stop
                mx[node] = val
                lz[node] = val
                return
            push(node)
            mid = (lo + hi) // 2
            update(2 * node, lo, mid, l, r, val)
            update(2 * node + 1, mid + 1, hi, l, r, val)
            mx[node] = max(mx[2 * node], mx[2 * node + 1])

        def query(node, lo, hi, l, r):
            if r < lo or hi < l:
                return 0
            if l <= lo and hi <= r:
                return mx[node]
            push(node)
            mid = (lo + hi) // 2
            return max(query(2 * node, lo, mid, l, r),
                       query(2 * node + 1, mid + 1, hi, l, r))

        res, best = [], 0
        for l, s in positions:
            # square covers [l, l+s) -> closed leaf range [a, b]
            a, b = idx[l], idx[l + s] - 1
            cur = query(1, 0, m - 1, a, b)    # tallest thing already under it
            update(1, 0, m - 1, a, b, cur + s)  # lands ON TOP -> assign
            best = max(best, cur + s)
            res.append(best)
        return res

Variation — “just sort the ranges” O(n²) fallback (say this first in an interview, then optimize). The twist: skip the tree entirely and keep a plain height[i] per square. For square i, scan all earlier squares and take the max height among those that overlap it (l < r2 and l2 < r — strict, since the intervals are half-open and touching edges do not stack). n <= 1000 on LC 699, so this passes.

python
# python — LC 699 brute force
# time = O(n^2), space = O(n)
def fallingSquares(positions):
    n = len(positions)
    h, res, best = [0] * n, [], 0
    for i, (l, s) in enumerate(positions):
        r = l + s
        base = 0
        for j in range(i):
            l2, s2 = positions[j]
            if l < l2 + s2 and l2 < r:      # half-open overlap: touching != stacking
                base = max(base, h[j])
        h[i] = base + s
        best = max(best, h[i])
        res.append(best)
    return res

1) General form

java

// java
// https://labuladong.online/algo/data-structure/diff-array/

// 差分数组工具类
// V1
class Difference {
    // 差分数组
    private int[] diff;
    
    // 输入一个初始数组，区间操作将在这个数组上进行
    public Difference(int[] nums) {
        assert nums.length > 0;
        diff = new int[nums.length];
        // 根据初始数组构造差分数组
        diff[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
    }

    // 给闭区间 [i, j] 增加 val（可以是负数）
    public void increment(int i, int j, int val) {
        diff[i] += val;
        if (j + 1 < diff.length) {
            diff[j + 1] -= val;
        }
    }

    // 返回结果数组
    public int[] result() {
        int[] res = new int[diff.length];
        // 根据差分数组构造结果数组
        res[0] = diff[0];
        for (int i = 1; i < diff.length; i++) {
            res[i] = res[i - 1] + diff[i];
        }
        return res;
    }
}
java
// V2
// https://github.com/yennanliu/CS_basics/blob/master/leetcode_java/src/main/java/AlgorithmJava/DifferenceArray.java


// method
public int[] getDifferenceArray(int[][] input, int n) {

/** LC 1109. Corporate Flight Bookings input : [start, end, seats]
 *
 *  NOTE !!!
 *
 *   in java, index start from 0;
 *   but in LC 1109, index start from 1
 *
 */
int[] tmp = new int[n + 1];
for (int[] x : input) {
  int start = x[0];
  int end = x[1];
  int seats = x[2];

  // add
  tmp[start] += seats;

  // subtract
  if (end + 1 <= n) {
    tmp[end + 1] -= seats;
  }
}

for (int i = 1; i < tmp.length; i++) {
  //tmp[i] = tmp[i - 1] + tmp[i];
    tmp[i] += tmp[i - 1];
}

return Arrays.copyOfRange(tmp, 1, n+1);
}

Problems by Pattern

Pattern-Based Problem Classification

Pattern 1: Basic Range Update Problems

Problem LC # Difficulty Key Technique Template
Range Addition 370 Medium Basic difference array Template 1
Corporate Flight Bookings 1109 Medium Range updates Template 1
Range Addition II 598 Easy Minimum overlap Template 1
Apply Operations to Make All Array Elements Equal to Zero 2772 Medium Range updates Template 1

Pattern 2: Resource Allocation Problems

Problem LC # Difficulty Key Technique Template
Car Pooling 1094 Medium Capacity check Template 2
Meeting Rooms II 253 Medium Timeline events Template 2
My Calendar I 729 Medium Interval booking Template 2
My Calendar II 731 Medium Double booking Template 2
My Calendar III 732 Hard K-booking Template 2

Pattern 3: Event Timeline Problems

Problem LC # Difficulty Key Technique Template
Number of Flowers in Full Bloom 2251 Hard Timeline query Template 3
Describe the Painting 2158 Medium Color mixing Template 3
Maximum Population Year 1854 Easy Timeline count Template 3
Count Positions on Street With Required Brightness 2021 Medium Light coverage Template 3

Pattern 4: 2D Difference Array Problems

Problem LC # Difficulty Key Technique Template
Stamping the Grid 2132 Hard 2D range update Template 4
Increment Submatrices by One 2536 Medium Rectangle updates Template 4

Pattern 5: Coverage Map + Greedy Fill Problems

Problem LC # Difficulty Key Technique Template
Minimum Lights to Illuminate a Road 3964 Medium Diff coverage + greedy gap fill Template 6
Count Positions on Street With Required Brightness 2021 Medium Diff coverage map (query, no fill) Template 3
Video Stitching 1024 Medium Interval coverage + greedy jump Greedy
Minimum Number of Taps to Open to Water a Garden 1326 Hard Coverage ranges + greedy min-taps Greedy

Pattern 6: Range Update + Range MAX Query Problems

Problem LC # Difficulty Key Technique Template
Falling Squares 699 Hard Compression + segment tree lazy assign Template 7
My Calendar III 732 Hard Same escalation, but additive (+1/-1) so a sorted-map diff array still works Template 2 / 5

Complete Problem List by Difficulty

Easy Problems (Foundation)

  • LC 598: Range Addition II - Find minimum affected area
  • LC 1854: Maximum Population Year - Simple timeline
  • LC 1893: Check if All Integers in Range Are Covered - Range coverage

Medium Problems (Core)

  • LC 370: Range Addition - Classic difference array
  • LC 1109: Corporate Flight Bookings - Flight seat allocation
  • LC 1094: Car Pooling - Resource capacity validation
  • LC 253: Meeting Rooms II - Minimum rooms needed
  • LC 729: My Calendar I - No double booking
  • LC 731: My Calendar II - Allow one double booking
  • LC 2021: Street Light Brightness - Range illumination
  • LC 2158: Amount of New Area Painted - Color segments
  • LC 2536: Increment Submatrices by One - 2D updates
  • LC 2772: Apply Operations to Array - Make all zeros

Hard Problems (Advanced)

  • LC 732: My Calendar III - Maximum K-booking
  • LC 2132: Stamping the Grid - 2D stamp validation
  • LC 2251: Number of Flowers in Full Bloom - Point queries on timeline
  • LC 699: Falling Squares - Range assign + range max (diff array insufficient → segment tree lazy)

2) LC Example

2-1) Range Addition — LC 370

java
// java
// LC 370


// V0
// IDEA : DIFFERENCE ARRAY
public static int[] getModifiedArray(int length, int[][] updates) {

int[] tmp = new int[length + 1]; // or new int[length]; both works
for (int[] x : updates) {
  int start = x[0];
  int end = x[1];
  int amount = x[2];

  // add
  tmp[start] += amount;

  // subtract (remove the "adding affect" on "NEXT" element)
  /**
   * NOTE !!!
   *
   * <p>we remove the "adding affect" on NEXT element (e.g. end + 1)
   */
  if (end + 1 < length) { // NOTE !!! use `end + 1`
    tmp[end + 1] -= amount;
  }
}

// prepare final result
for (int i = 1; i < tmp.length; i++) {
  tmp[i] += tmp[i - 1];
}

return Arrays.copyOfRange(tmp, 0, length); // return the sub array between 0, lengh index
}

// V1
class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        // nums 初始化为全 0
        int[] nums = new int[length];
        // 构造差分解法
        Difference df = new Difference(nums);
        
        for (int[] update : updates) {
            int i = update[0];
            int j = update[1];
            int val = update[2];
            df.increment(i, j, val);
        }
        
        return df.result();
    }
}

2-2) Corporate Flight Bookings — LC 1109

java
// java
// LC 1109

// V1
class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        // nums 初始化为全 0
        int[] nums = new int[n];
        // 构造差分解法
        Difference df = new Difference(nums);

        for (int[] booking : bookings) {
            // 注意转成数组索引要减一哦
            int i = booking[0] - 1;
            int j = booking[1] - 1;
            int val = booking[2];
            // 对区间 nums[i..j] 增加 val
            df.increment(i, j, val);
        }
        // 返回最终的结果数组
        return df.result();
    }
}

2-3) Car Pooling — LC 1094

java
// java
// LC 1094
// https://leetcode.com/problems/car-pooling/description/

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        // 最多有 1001 个车站
        int[] nums = new int[1001];

        // 构造差分解法
        Difference df = new Difference(nums);

        for (int[] trip : trips) {
            // 乘客数量
            int val = trip[0];

            // 第 trip[1] 站乘客上车
            int i = trip[1];

            // 第 trip[2] 站乘客已经下车，
            // 即乘客在车上的区间是 [trip[1], trip[2] - 1]
            int j = trip[2] - 1;

            // 进行区间操作
            df.increment(i, j, val);
        }

        int[] res = df.result();

        // 客车自始至终都不应该超载
        for (int i = 0; i < res.length; i++) {
            if (capacity < res[i]) {
                return false;
            }
        }
        return true;
    }
}

2-4) Minimum Lights to Illuminate a Road — LC 3964

Core idea: three phases — (1) a difference array records every range the existing bulbs already cover in O(1) each, (2) a prefix sum turns that into a covered[] map where 0 = dark spot, (3) a greedy left→right pass drops one new bulb at each dark spot. Since a new bulb placed at i+1 illuminates i, i+1, i+2, we can safely jump ahead 3 after placing one.

Why greedy is optimal: the first dark position must be covered by some new bulb, and placing that bulb as far right as still covers it (i+1) maximizes forward reach — never worse than any other placement.

python
# python
# LC 3964
class Solution(object):
    def minLights(self, lights):
        n = len(lights)

        # 1) difference array (size n+1 so right+1 is always safe)
        diff = [0] * (n + 1)
        for i, v in enumerate(lights):
            if v > 0:
                left  = max(0, i - v)
                right = min(n - 1, i + v)
                diff[left]      += 1
                diff[right + 1] -= 1

        # 2) prefix sum -> coverage map
        covered = [0] * n
        run = 0
        for i in range(n):
            run += diff[i]
            covered[i] = run

        # 3) greedy fill
        ans = 0
        i = 0
        while i < n:
            if covered[i] == 0:
                ans += 1
                i += 3          # new bulb at i+1 covers i, i+1, i+2
            else:
                i += 1
        return ans
python
# python — compact variant: count dark runs, ceil-divide by bulb width 3
class Solution(object):
    def minLights(self, lights):
        n = len(lights)
        diff = [0] * (n + 1)
        for i, v in enumerate(lights):
            if v > 0:
                diff[max(0, i - v)]          += 1
                diff[min(n - 1, i + v) + 1]  -= 1

        cover = run = ans = 0
        for i in range(n):
            cover += diff[i]
            if cover == 0:
                run += 1                     # extend current dark run
            else:
                ans += (run + 2) // 3        # ceil(run / 3) bulbs for the run
                run = 0
        ans += (run + 2) // 3                # flush trailing dark run
        return ans

Pattern Selection Strategy

text
Difference Array Problem Analysis Flowchart:

1. Does the problem involve range updates?
   ├── YES → Check update pattern
   │   ├── Multiple ranges need same update? → Use Difference Array
   │   ├── Single element updates? → Use direct array
   │   └── Need immediate query results? → Consider Segment Tree
   └── NO → Not a difference array problem

2. What type of range operation?
   ├── Add/Subtract constant to range → Basic Difference Array (Template 1)
   ├── Track resource usage → Resource Allocation (Template 2)
   ├── Timeline/Event processing → Event Timeline (Template 3)
   └── 2D matrix updates → 2D Difference Array (Template 4)

3. Space/Time Trade-offs:
   ├── Large coordinate space? → Use Coordinate Compression (Template 5)
   ├── Many queries between updates? → Consider Lazy Propagation
   └── Only final result needed? → Basic Difference Array

4. Special Considerations:
   ├── Online vs Offline → Difference array is offline
   ├── Need range queries? → Combine with Prefix Sum
   └── Overlapping intervals? → Check maximum overlap

Decision Framework

  1. Identify range updates: Look for “update range [l, r]” operations
  2. Count operations: Multiple updates = good for difference array
  3. Check query pattern: Final result only vs intermediate queries
  4. Consider alternatives: Segment tree for dynamic queries

Summary & Quick Reference

Complexity Quick Reference

Operation Time Complexity Space Complexity Notes
Build Difference Array O(n) O(n) From original array
Range Update O(1) O(1) Add value to range
Reconstruct Array O(n) O(1) Get final result
M Updates + Reconstruct O(m + n) O(n) Total complexity
2D Range Update O(1) O(1) Rectangle update
2D Reconstruct O(mn) O(1) Get final matrix

Template Quick Reference

Template Best For Avoid When Key Pattern
Basic Difference Multiple range updates Single updates diff[i] = arr[i] - arr[i-1]
Resource Allocation Capacity constraints Unbounded resources Check max usage
Event Timeline Time-based events Spatial problems Timeline array
2D Difference Matrix range updates 1D problems 4-point update
Coordinate Compression Large sparse space Dense arrays Map coordinates

Common Patterns & Tricks

Pattern: Range Update Formula

python
# To add val to range [start, end]:
diff[start] += val
if end + 1 < n:
    diff[end + 1] -= val

Pattern: Off-by-One for Intervals

python
# If passengers get off at station x, they're on board [start, x-1]
# If event ends at time t, it's active [start, t]
# Be careful with inclusive/exclusive boundaries!

# Car pooling example:
for passengers, pickup, dropoff in trips:
    diff[pickup] += passengers
    diff[dropoff] -= passengers  # Not dropoff-1!

Pattern: Maximum Concurrent Events

python
def max_concurrent(intervals):
    events = []
    for start, end in intervals:
        events.append((start, 1))   # Start event
        events.append((end + 1, -1)) # End event
    
    events.sort()
    max_concurrent = current = 0
    
    for time, delta in events:
        current += delta
        max_concurrent = max(max_concurrent, current)
    
    return max_concurrent

Problem-Solving Steps

  1. Identify range operations: Look for [start, end] updates
  2. Initialize difference array: Usually all zeros
  3. Apply updates: O(1) per update using formula
  4. Reconstruct if needed: Prefix sum to get final array
  5. Validate constraints: Check capacity, overlaps, etc.

Common Mistakes & Tips

🚫 Common Mistakes:

  • Off-by-one errors: Careful with inclusive/exclusive ranges
  • Array bounds: Check end+1 before updating
  • Initial values: Don’t forget original array values
  • 2D formula errors: Four points need correct signs
  • Overflow: Large values × many updates

✅ Best Practices:

  • Use clear variable names: start/end not i/j
  • Comment boundary logic: Explain inclusive/exclusive
  • Test edge cases: Empty ranges, full array updates
  • Consider compression: For large coordinate spaces
  • Validate early: Check impossible cases first

Interview Tips

  1. Recognize the pattern: “Update multiple ranges” → Difference array
  2. Explain the technique: “Convert range updates to point updates”
  3. Mention trade-offs: Offline processing, O(n) reconstruction
  4. Know alternatives: Segment tree for online queries
  5. Handle edge cases: Empty input, single element, overlapping ranges
  • Prefix Sum: Opposite operation, range queries
  • Segment Tree: When need both updates and queries
  • Fenwick Tree (BIT): Alternative for range operations
  • Sweep Line: Related technique for interval problems
  • Coordinate Compression: Handling large sparse ranges

Looks like a difference array, but is not — know the tell

Problem LC # Why the diff array does not apply Go read
The Skyline Problem 218 Endpoint events look identical to +h / -h stamps, but the answer is the max active height, not a sum — you must remove one specific height from a live multiset/heap, which -h at end+1 cannot do scanning_line.md
Merge Intervals 56 Output is the intervals themselves, not a per-index value; a +1/-1 sweep only tells you where coverage is non-zero intervals.md
Subarray Sum Equals K 560 Prefix sum queried with a hash map — the inverse direction (range query, no range update) prefix_sum.md

The tell in one line: difference array needs (a) updates that are additive, (b) all updates known up front (offline), and © a final read of the whole array. Break (a) → segment tree (Template 7); break (b) → segment tree / BIT; break © with huge coordinates → compression (Template 5).

Java Implementation Notes

java
// Java Difference Array Class
class Difference {
    private int[] diff;
    
    public Difference(int[] nums) {
        diff = new int[nums.length];
        diff[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            diff[i] = nums[i] - nums[i-1];
        }
    }
    
    public void increment(int i, int j, int val) {
        diff[i] += val;
        if (j + 1 < diff.length) {
            diff[j + 1] -= val;
        }
    }
    
    public int[] result() {
        int[] res = new int[diff.length];
        res[0] = diff[0];
        for (int i = 1; i < diff.length; i++) {
            res[i] = res[i-1] + diff[i];
        }
        return res;
    }
}

Python Implementation Notes

python
# Python class implementation
class DifferenceArray:
    def __init__(self, nums):
        self.n = len(nums)
        self.diff = [0] * self.n
        if nums:
            self.diff[0] = nums[0]
            for i in range(1, self.n):
                self.diff[i] = nums[i] - nums[i-1]
    
    def update(self, start, end, val):
        self.diff[start] += val
        if end + 1 < self.n:
            self.diff[end + 1] -= val
    
    def get_result(self):
        result = [self.diff[0]]
        for i in range(1, self.n):
            result.append(result[-1] + self.diff[i])
        return result

Must-Know Problems for Interviews: LC 370, 1109, 1094, 253, 732 Advanced Problems: LC 732, 2132, 2251 Keywords: difference array, range update, interval modification, sweep line, prefix sum

← Back to Cheat Sheets Edit on GitHub →