Difference Array

Difference arrays are the mirror image of prefix sums. Prefix sums make repeated range reads cheap. Difference arrays make repeated range writes cheap when you can delay reading the final result.

Boundary Markers Instead of Repeated Writes

If you need to add +5 to every item from index l to r, updating each cell costs O(r-l+1). A difference array marks where the change starts and where it stops: diff[l] += 5 and diff[r + 1] -= 5. Later, a prefix pass reconstructs the final values.

Scenario: Promotion Calendar

An ecommerce platform plans hundreds of overlapping promotional boosts across 365 days. Each campaign adds a score boost to a day range. Updating every day for every campaign is unnecessary. Mark campaign starts and stops in a difference array, then run one prefix pass to compute final daily boost.

Same Pattern in Java, Python, and JavaScript

class DifferenceArray {
    static int[] apply(int length, int[][] updates) {
        int[] diff = new int[length + 1];
        for (int[] update : updates) {
            int left = update[0];
            int right = update[1];
            int delta = update[2];
            diff[left] += delta;
            if (right + 1 < diff.length) diff[right + 1] -= delta;
        }
        int[] result = new int[length];
        int running = 0;
        for (int i = 0; i < length; i++) {
            running += diff[i];
            result[i] = running;
        }
        return result;
    }
}

Field judgmentEngineering Notes

• Use difference arrays for many range updates followed by final reconstruction.
• Mark both the start and the stop boundary.
• Allocate one extra slot to simplify r + 1 handling.
• State O(k + n) total cost for k updates and n positions.
• Do not use this pattern blindly for online query/update workloads.

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

• Apply many updates of the form add delta to every index from left to right, then return the final array.
• Each booking adds seats to every flight number in a range. Return seats booked per flight.
• Campaigns add score boosts to day ranges. Return final daily boost after all campaigns.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Solved modelInterview Question Solutions

class RangeUpdates {
    static int[] apply(int length, int[][] updates) {
        int[] diff = new int[length + 1];
        for (int[] update : updates) {
            int left = update[0], right = update[1], delta = update[2];
            diff[left] += delta;
            if (right + 1 < diff.length) diff[right + 1] -= delta;
        }
        int[] result = new int[length];
        int running = 0;
        for (int i = 0; i < length; i++) {
            running += diff[i];
            result[i] = running;
        }
        return result;
    }
}

class FlightBookings {
    static int[] seats(int flightCount, int[][] bookings) {
        int[] diff = new int[flightCount + 1];
        for (int[] booking : bookings) {
            int first = booking[0] - 1;
            int last = booking[1] - 1;
            int seats = booking[2];
            diff[first] += seats;
            if (last + 1 < diff.length) diff[last + 1] -= seats;
        }
        int[] result = new int[flightCount];
        int running = 0;
        for (int i = 0; i < flightCount; i++) {
            running += diff[i];
            result[i] = running;
        }
        return result;
    }
}

class PromotionCalendar {
    static int[] boosts(int days, int[][] campaigns) {
        int[] diff = new int[days + 1];
        for (int[] campaign : campaigns) {
            int start = campaign[0];
            int end = campaign[1];
            int boost = campaign[2];
            diff[start] += boost;
            if (end + 1 < diff.length) diff[end + 1] -= boost;
        }
        int[] result = new int[days];
        int running = 0;
        for (int day = 0; day < days; day++) {
            running += diff[day];
            result[day] = running;
        }
        return result;
    }
}

Solved modelWorked Interview Answer

Apply many range increment updates and return the final array. Mark only the start and stop boundaries for each update, then reconstruct with one prefix pass.

class RangeUpdates {
    static int[] apply(int length, int[][] updates) {
        int[] diff = new int[length + 1];
        for (int[] update : updates) {
            int left = update[0], right = update[1], delta = update[2];
            diff[left] += delta;
            if (right + 1 < diff.length) diff[right + 1] -= delta;
        }
        int[] result = new int[length];
        int running = 0;
        for (int i = 0; i < length; i++) {
            running += diff[i];
            result[i] = running;
        }
        return result;
    }
}

Hands-on drillTry It Yourself

Failure patternsCommon Mistakes to Avoid

• Forgetting the stop marker at r + 1.
• Not allocating an extra diff slot.
• Using difference arrays when the system needs immediate online reads after each update.

Execution guardrailQuick-Start Checklist

• Create diff with length n + 1.
• Mark diff[left] plus equals delta.
• Mark diff[right + 1] minus equals delta when in bounds.
• Run one prefix pass.
• State O(k + n) for k updates and n positions.

Recall drillKnowledge Check

VocabularyKey Terms

Next practiceFurther Reading

• Compare difference arrays with lazy propagation.
• Study booking, calendar, and capacity simulation problems.
• Review prefix sums because reconstruction uses a prefix pass.