Skip to content
Hello Python

Apply Range Additions

Practice ExerciseIntermediateMediumDifference ArrayArray

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement apply_range_additions(length, updates). Each update is [left, right, delta] with inclusive indexes. Start from length zeros and return the final list.

Starter code

def apply_range_additions(length, updates):
    pass
Test cases

overlapping-updates

{
  "args": [
    5,
    [
      [
        1,
        3,
        2
      ],
      [
        2,
        4,
        1
      ]
    ]
  ]
}

Expected: [0,2,3,3,1]

whole-range

{
  "args": [
    3,
    [
      [
        0,
        2,
        -2
      ]
    ]
  ]
}

Expected: [-2,-2,-2]

Wizard outline
  1. Step 1: Mark update starts

    Represent additions that continue through the end. Adding delta at left changes every recovered prefix from that point onward.

  2. Step 2: Stop one finite range after the right edge

    Encode both boundaries for a single inclusive update. A focused one-range checkpoint makes the start and cancellation pair observable before ranges are superposed.

  3. Step 3: Combine overlapping updates

    Complete the contract for multiple positive and negative ranges. Difference boundaries add linearly, so one prefix scan resolves every overlap.

Footguns and prerequisites
  • Writing the negative boundary at right instead of right + 1 shortens the update.
  • The cancellation boundary may lie exactly one past the array.
  • arrays strings two pointers sliding window
Reviewed references
Recommended approach and implementation

Accumulate start and post-end boundary deltas, then prefix-sum the difference array once.

Why it works: Each update contributes delta beginning at left and removes it immediately after right. Therefore the running prefix at every index equals the sum of exactly the updates covering that index.

def apply_range_additions(length, updates):
    difference = [0] * length
    for left, right, delta in updates:
        difference[left] += delta
        if right + 1 < length:
            difference[right + 1] -= delta
    values = []
    running = 0
    for delta in difference:
        running += delta
        values.append(running)
    return values