What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Two Pointers & Sliding Window

Builds on Prefix Sum Map and Prefix Sums, which you haven’t finished yet.

P2MediumBuilt on Prefix Sums~3 min speedrun

Difference Array (Range Updates)

Built on

Prefix SumsWrite a mark at each end of a range, then take one prefix sum to read the total at every position.

Corporate Flight Bookings (LC 1109)(opens leetcode.com)

Flights are numbered from 1 to n. A booking [first, last, seats] adds seats reserved seats to each flight from first through last. After all of bookings, report each flight's total: position i of the result holds the seats reserved on flight i + 1.

Example 1

Input:bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5

Output:[10,55,45,25,25]

Booking 1 adds 10 to flights 1-2, booking 2 adds 20 to flights 2-3, and booking 3 adds 25 to flights 2-5. Flight 2 gets 10 + 20 + 25 = 55, flight 3 gets 20 + 25 = 45, and so on.

Difference Array

range updates ➔ +v at the start, -v just past the end ➔ one prefix sum

Spot it when: Many range updates arrive first and you only read the values after all of them (offline), or you need how many ranges cover each point.

Difference Array

Python

1	def corp_flight_bookings(bookings: list[list[int]], n: int) -> list[int]:
2	"""Corporate Flight Bookings: range adds via a difference array, read once by prefix sum.
3	Time: O(Q + N) \| Space: O(N)
4	"""
5	diff = [0] * (n + 1) # One extra slot so last + 1 never overflows
6	# 1. Mark Each Range's Start And End:
7	# Adding seats to every flight from first to last only changes the running total at two points: where the range starts, and one past where it ends.
8	for first, last, seats in bookings:
9	diff[first - 1] += seats # Range starts here (1-indexed input)
10	diff[last] -= seats # Range ends after flight `last`
11
12	# 2. Rebuild Every Total With One Prefix Sum:
13	# running accumulates diff left to right, so it equals the sum of every mark placed at or before i, which is exactly the total booked on flight i + 1.
14	answer, running = [], 0
15	for i in range(n):
16	running += diff[i]
17	answer.append(running)
18	return answer

Invariant: Once every booking is marked, diff[0] + ... + diff[i] is the total booked on flight i + 1.

Adding seats to every flight from first to last only changes the running total in two places: where the range starts and just after it ends. So record diff[first - 1] += seats and diff[last] -= seats, and one prefix sum over diff at the end rebuilds every flight's total. The trap is the end mark: it goes at diff[last], one past the range in 0-indexed terms, so diff needs n + 1 slots, or a booking that ends on the last flight writes out of bounds.

See it run

Difference Array, step by step

running 0

The top row is diff. The bottom row is the answer. Slot i belongs to flight i + 1, and the last slot belongs to no flight.

start mark a slot that gets +seats where a booking starts
end mark a slot that gets -seats just after a booking ends
read the diff slot added to running in this step
total the finished total of one flight

Start: 5 flights and 3 bookings. diff has 6 slots: one per flight and one extra slot at the end.

diff

answer

1 / 13

Gotchas1 of 3

The trap
Gotcha 1: Making diff only n slots long
Mistake
```
diff = [0] * n
```
Fix
```
diff = [0] * (n + 1)
```
What happens: A booking that ends on the last flight writes its end mark at diff[last], which is diff[n]. A list of n slots has indices 0 to n - 1 only. So Python raises an IndexError on that write.
Example: Corporate Flight Bookings (LC 1109), Example 1: bookings = [[1, 2, 10], [2, 3, 20], [2, 5, 25]], n = 5
Mistake: raises IndexErrorFix: returns [10, 55, 45, 25, 25]
Gotcha 2: Using the 1-indexed flight numbers as list indices
Mistake
```
diff[first] += seats
diff[last + 1] -= seats
```
Fix
```
diff[first - 1] += seats
diff[last] -= seats
```
What happens: Flights are numbered from 1, but diff is indexed from 0. So flight first is at index first - 1. The end mark goes right after flight last, at index last. Without the shift, every booking lands one flight too late.
Example: bookings = [[1, 2, 10]], n = 3
Mistake: returns [0, 10, 10]Fix: returns [10, 10, 0]
Gotcha 3: Applying a running shift without % 26
Mistake
```
chr(ord('a') + (ord(c) - ord('a') + running))
```
Fix
```
chr(ord('a') + (ord(c) - ord('a') + running) % 26)
```
What happens: Shifting Letters II (LC 2381) marks +1 for a forward shift and -1 for a backward shift. The running total can be negative or larger than 25. Take the new position modulo 26 before you turn it into a letter. Python's % returns a value from 0 to 25, even for a negative number.

Not this one if…

The positions are huge or not whole numbers, as in Meeting Rooms II (LC 253), so you can't allocate one slot per position; sort the start and end events instead. See Sweep Line
Updates and sum queries arrive mixed together, as in Range Sum Query - Mutable (LC 307), so values must be readable between updates. See Fenwick Tree

Deep Dive

Why two marks describe a whole range

The Prefix Sums card turns a list of values into running totals. A difference array is the reverse. You write marks into diff, and one prefix sum over diff gives the final values.

A booking adds seats to every flight from first to last. In the running total, a +seats mark at the start raises every flight from there on. A -seats mark just after the end cancels it. The flights between the two marks get seats, and the flights after the end get 0.

So each booking costs two writes, whatever the length of its range. All bookings are marked first. Then one pass computes running += diff[i] for every flight. The cost is O(Q + N) for Q bookings and N flights. Adding to every flight of every range costs up to O(Q * N).

The method works because all updates come before any read. If reads are mixed with updates, one prefix sum at the end is not enough. The Fenwick Tree card handles that case.

Corporate Flight Bookings traced

The input is bookings = [[1, 2, 10], [2, 3, 20], [2, 5, 25]] and n = 5. The flights are numbered from 1, and diff is indexed from 0, so flight first is at diff[first - 1].

Booking [1, 2, 10] writes diff[0] += 10 and diff[2] -= 10. Booking [2, 3, 20] writes diff[1] += 20 and diff[3] -= 20. Booking [2, 5, 25] writes diff[1] += 25 and diff[5] -= 25.

The result is diff = [10, 45, -10, -20, 0, -25]. The running totals are 10, 55, 45, 25, 25, which is the answer of the problem.

The last write is diff[5]. A booking that ends on the last flight writes at index n, so diff needs n + 1 slots. With n slots, Python raises an IndexError.

The end mark, and the same card with 0-indexed ranges

The end mark goes one past the last position of the range. In Corporate Flight Bookings (LC 1109), flights are numbered from 1, so the index just past flight last is diff[last]. That is why the card writes diff[last] -= seats.

In Range Addition (LC 370), positions start at 0 and end is the last position of the range. The end mark is diff[end + 1] -= inc. For length = 5 and updates = [[1, 3, 2], [2, 4, 3], [0, 2, -2]], the result is [-2, 0, 3, 5, 3].

In Car Pooling (LC 1094), a trip [passengers, from, to] lets the passengers get off at to. They are in the car at positions from to to - 1. The marks are diff[from] += passengers and diff[to] -= passengers. The car is over capacity if any running total exceeds capacity. For trips = [[2, 1, 5], [3, 5, 7]] and capacity = 3, the answer is True, because the 2 passengers get off at 5 before the 3 get on.

In Shifting Letters II (LC 2381), the mark is +1 for a forward shift and -1 for a backward shift. The running total can be negative or larger than 25, so take the final position modulo 26.

60-Second Pitch

"Every booking adds the same amount to a whole range of flights. If I add it flight by flight, the cost is the length of each range. Instead I write two marks: +seats where the range starts and -seats just after it ends. One prefix sum over these marks then gives the total on every flight. The array has n + 1 slots, because a booking that ends on the last flight writes the end mark at index n. I also convert the 1-indexed flight numbers to list indices. The time is O(Q + N) and the space is O(N). This works because all updates come before the reads."

Common Questions

Why does one prefix sum over the marks give the right totals?: The running total at flight i + 1 is the sum of all marks at or before it. A +seats mark counts for every flight from the start of its range. The matching -seats mark cancels it after the end. So a booking adds seats only inside its range.
Why does diff need n + 1 slots?: A booking that ends on the last flight writes its end mark at index n. A list of n slots has indices 0 to n - 1, so that write fails. The extra slot is never read for an answer.
How do you handle 0-indexed inclusive ranges, as in Range Addition (LC 370)?: Write diff[start] += inc and diff[end + 1] -= inc. The end mark goes one position past the last position of the range. Use n + 1 slots, or skip the write when end + 1 equals n.
When is a difference array the wrong tool?: It is wrong when reads come between updates. It is also wrong when the positions are huge numbers or not whole numbers, because one slot per position does not fit in memory. The Sweep Line card sorts the start and end events for that case.
What is the cost, compared with updating every position?: The marks cost O(1) per update and the final pass costs O(N), so the total is O(Q + N). Updating every position of every range costs up to O(Q * N).

SWE Reasoning

Spot it

Many updates each add a value to a whole range, and the values are read only after all updates.
The question asks for every final value, or for how many ranges cover each point.
The positions are small whole numbers, so one slot per position fits in memory.
Example problems: Corporate Flight Bookings (LC 1109), Range Addition (LC 370), Car Pooling (LC 1094).

The invariant, step by step

diff starts as n + 1 zeros.
A booking writes +seats at diff[first - 1] and -seats at diff[last].
The sum diff[0] + ... + diff[i] counts the +seats marks at or before flight i + 1, minus the -seats marks at or before it.
A booking is counted exactly when first - 1 <= i and last > i, which means flight i + 1 is inside its range.
So the sum is the total booked on flight i + 1, and the loop running += diff[i] computes it for every flight.

Traps

Making diff only n slots long. A booking that ends on the last flight writes at diff[n] and raises an IndexError.
Using the 1-indexed flight numbers as list indices. Every booking shifts one flight too late. For [[1, 2, 10]] and n = 3, the result is [0, 10, 10] instead of [10, 10, 0].
Putting the end mark on the last position of the range. The -seats then cancels the last flight too early.
Reading values between updates. Marks give correct values only after the prefix sum, so reads and updates cannot be mixed.

Practice

Canonical LeetCode:Corporate Flight Bookings (LC 1109)Range Addition (LC 370)Car Pooling (LC 1094)Maximum Population Year (LC 1854)Shifting Letters II (LC 2381)Minimum Number of K Consecutive Bit Flips (LC 995)Maximum Sum Obtained of Any Permutation (LC 1589)

Theory Context•Two Pointers & Sliding Window

Builds on Prefix Sum Map and Prefix Sums, which you haven’t finished yet.

P2MediumBuilt on Prefix Sums~3 min speedrun

Difference Array (Range Updates)

Built on

Prefix SumsWrite a mark at each end of a range, then take one prefix sum to read the total at every position.

Corporate Flight Bookings (LC 1109)(opens leetcode.com)

Example 1

Input:bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5

Output:[10,55,45,25,25]

Booking 1 adds 10 to flights 1-2, booking 2 adds 20 to flights 2-3, and booking 3 adds 25 to flights 2-5. Flight 2 gets 10 + 20 + 25 = 55, flight 3 gets 20 + 25 = 45, and so on.

Difference Array

range updates ➔ +v at the start, -v just past the end ➔ one prefix sum

Spot it when: Many range updates arrive first and you only read the values after all of them (offline), or you need how many ranges cover each point.

Difference Array

Python

1	def corp_flight_bookings(bookings: list[list[int]], n: int) -> list[int]:
2	"""Corporate Flight Bookings: range adds via a difference array, read once by prefix sum.
3	Time: O(Q + N) \| Space: O(N)
4	"""
5	diff = [0] * (n + 1) # One extra slot so last + 1 never overflows
6	# 1. Mark Each Range's Start And End:
7	# Adding seats to every flight from first to last only changes the running total at two points: where the range starts, and one past where it ends.
8	for first, last, seats in bookings:
9	diff[first - 1] += seats # Range starts here (1-indexed input)
10	diff[last] -= seats # Range ends after flight `last`
11
12	# 2. Rebuild Every Total With One Prefix Sum:
13	# running accumulates diff left to right, so it equals the sum of every mark placed at or before i, which is exactly the total booked on flight i + 1.
14	answer, running = [], 0
15	for i in range(n):
16	running += diff[i]
17	answer.append(running)
18	return answer

Invariant: Once every booking is marked, diff[0] + ... + diff[i] is the total booked on flight i + 1.

See it run

Difference Array, step by step

running 0

The top row is diff. The bottom row is the answer. Slot i belongs to flight i + 1, and the last slot belongs to no flight.

start mark a slot that gets +seats where a booking starts
end mark a slot that gets -seats just after a booking ends
read the diff slot added to running in this step
total the finished total of one flight

Start: 5 flights and 3 bookings. diff has 6 slots: one per flight and one extra slot at the end.

diff

answer

1 / 13

Gotchas1 of 3

The trap
Gotcha 1: Making diff only n slots long
Mistake
```
diff = [0] * n
```
Fix
```
diff = [0] * (n + 1)
```
What happens: A booking that ends on the last flight writes its end mark at diff[last], which is diff[n]. A list of n slots has indices 0 to n - 1 only. So Python raises an IndexError on that write.
Example: Corporate Flight Bookings (LC 1109), Example 1: bookings = [[1, 2, 10], [2, 3, 20], [2, 5, 25]], n = 5
Mistake: raises IndexErrorFix: returns [10, 55, 45, 25, 25]
Gotcha 2: Using the 1-indexed flight numbers as list indices
Mistake
```
diff[first] += seats
diff[last + 1] -= seats
```
Fix
```
diff[first - 1] += seats
diff[last] -= seats
```
What happens: Flights are numbered from 1, but diff is indexed from 0. So flight first is at index first - 1. The end mark goes right after flight last, at index last. Without the shift, every booking lands one flight too late.
Example: bookings = [[1, 2, 10]], n = 3
Mistake: returns [0, 10, 10]Fix: returns [10, 10, 0]
Gotcha 3: Applying a running shift without % 26
Mistake
```
chr(ord('a') + (ord(c) - ord('a') + running))
```
Fix
```
chr(ord('a') + (ord(c) - ord('a') + running) % 26)
```
What happens: Shifting Letters II (LC 2381) marks +1 for a forward shift and -1 for a backward shift. The running total can be negative or larger than 25. Take the new position modulo 26 before you turn it into a letter. Python's % returns a value from 0 to 25, even for a negative number.

Not this one if…

The positions are huge or not whole numbers, as in Meeting Rooms II (LC 253), so you can't allocate one slot per position; sort the start and end events instead. See Sweep Line
Updates and sum queries arrive mixed together, as in Range Sum Query - Mutable (LC 307), so values must be readable between updates. See Fenwick Tree

Deep Dive

Why two marks describe a whole range

The Prefix Sums card turns a list of values into running totals. A difference array is the reverse. You write marks into diff, and one prefix sum over diff gives the final values.

The method works because all updates come before any read. If reads are mixed with updates, one prefix sum at the end is not enough. The Fenwick Tree card handles that case.

Corporate Flight Bookings traced

The input is bookings = [[1, 2, 10], [2, 3, 20], [2, 5, 25]] and n = 5. The flights are numbered from 1, and diff is indexed from 0, so flight first is at diff[first - 1].

Booking [1, 2, 10] writes diff[0] += 10 and diff[2] -= 10. Booking [2, 3, 20] writes diff[1] += 20 and diff[3] -= 20. Booking [2, 5, 25] writes diff[1] += 25 and diff[5] -= 25.

The result is diff = [10, 45, -10, -20, 0, -25]. The running totals are 10, 55, 45, 25, 25, which is the answer of the problem.

The last write is diff[5]. A booking that ends on the last flight writes at index n, so diff needs n + 1 slots. With n slots, Python raises an IndexError.

The end mark, and the same card with 0-indexed ranges

In Shifting Letters II (LC 2381), the mark is +1 for a forward shift and -1 for a backward shift. The running total can be negative or larger than 25, so take the final position modulo 26.

60-Second Pitch

Common Questions

Why does one prefix sum over the marks give the right totals?: The running total at flight i + 1 is the sum of all marks at or before it. A +seats mark counts for every flight from the start of its range. The matching -seats mark cancels it after the end. So a booking adds seats only inside its range.
Why does diff need n + 1 slots?: A booking that ends on the last flight writes its end mark at index n. A list of n slots has indices 0 to n - 1, so that write fails. The extra slot is never read for an answer.
How do you handle 0-indexed inclusive ranges, as in Range Addition (LC 370)?: Write diff[start] += inc and diff[end + 1] -= inc. The end mark goes one position past the last position of the range. Use n + 1 slots, or skip the write when end + 1 equals n.
When is a difference array the wrong tool?: It is wrong when reads come between updates. It is also wrong when the positions are huge numbers or not whole numbers, because one slot per position does not fit in memory. The Sweep Line card sorts the start and end events for that case.
What is the cost, compared with updating every position?: The marks cost O(1) per update and the final pass costs O(N), so the total is O(Q + N). Updating every position of every range costs up to O(Q * N).

SWE Reasoning

Spot it

Many updates each add a value to a whole range, and the values are read only after all updates.
The question asks for every final value, or for how many ranges cover each point.
The positions are small whole numbers, so one slot per position fits in memory.
Example problems: Corporate Flight Bookings (LC 1109), Range Addition (LC 370), Car Pooling (LC 1094).

The invariant, step by step

diff starts as n + 1 zeros.
A booking writes +seats at diff[first - 1] and -seats at diff[last].
The sum diff[0] + ... + diff[i] counts the +seats marks at or before flight i + 1, minus the -seats marks at or before it.
A booking is counted exactly when first - 1 <= i and last > i, which means flight i + 1 is inside its range.
So the sum is the total booked on flight i + 1, and the loop running += diff[i] computes it for every flight.

Traps

Making diff only n slots long. A booking that ends on the last flight writes at diff[n] and raises an IndexError.
Using the 1-indexed flight numbers as list indices. Every booking shifts one flight too late. For [[1, 2, 10]] and n = 3, the result is [0, 10, 10] instead of [10, 10, 0].
Putting the end mark on the last position of the range. The -seats then cancels the last flight too early.
Reading values between updates. Marks give correct values only after the prefix sum, so reads and updates cannot be mixed.

Practice

Theory Context•Two Pointers & Sliding Window

Builds on Prefix Sum Map and Prefix Sums, which you haven’t finished yet.

P2MediumBuilt on Prefix Sums~3 min speedrun

Difference Array (Range Updates)

Built on

Prefix SumsWrite a mark at each end of a range, then take one prefix sum to read the total at every position.

Corporate Flight Bookings (LC 1109)(opens leetcode.com)

Example 1

Input:bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5

Output:[10,55,45,25,25]

Booking 1 adds 10 to flights 1-2, booking 2 adds 20 to flights 2-3, and booking 3 adds 25 to flights 2-5. Flight 2 gets 10 + 20 + 25 = 55, flight 3 gets 20 + 25 = 45, and so on.

Difference Array

range updates ➔ +v at the start, -v just past the end ➔ one prefix sum

Spot it when: Many range updates arrive first and you only read the values after all of them (offline), or you need how many ranges cover each point.

Difference Array

Python

1	def corp_flight_bookings(bookings: list[list[int]], n: int) -> list[int]:
2	"""Corporate Flight Bookings: range adds via a difference array, read once by prefix sum.
3	Time: O(Q + N) \| Space: O(N)
4	"""
5	diff = [0] * (n + 1) # One extra slot so last + 1 never overflows
6	# 1. Mark Each Range's Start And End:
7	# Adding seats to every flight from first to last only changes the running total at two points: where the range starts, and one past where it ends.
8	for first, last, seats in bookings:
9	diff[first - 1] += seats # Range starts here (1-indexed input)
10	diff[last] -= seats # Range ends after flight `last`
11
12	# 2. Rebuild Every Total With One Prefix Sum:
13	# running accumulates diff left to right, so it equals the sum of every mark placed at or before i, which is exactly the total booked on flight i + 1.
14	answer, running = [], 0
15	for i in range(n):
16	running += diff[i]
17	answer.append(running)
18	return answer

Invariant: Once every booking is marked, diff[0] + ... + diff[i] is the total booked on flight i + 1.

See it run

Difference Array, step by step

running 0

The top row is diff. The bottom row is the answer. Slot i belongs to flight i + 1, and the last slot belongs to no flight.

start mark a slot that gets +seats where a booking starts
end mark a slot that gets -seats just after a booking ends
read the diff slot added to running in this step
total the finished total of one flight

Start: 5 flights and 3 bookings. diff has 6 slots: one per flight and one extra slot at the end.

diff

answer

1 / 13

Gotchas1 of 3

The trap
Gotcha 1: Making diff only n slots long
Mistake
```
diff = [0] * n
```
Fix
```
diff = [0] * (n + 1)
```
What happens: A booking that ends on the last flight writes its end mark at diff[last], which is diff[n]. A list of n slots has indices 0 to n - 1 only. So Python raises an IndexError on that write.
Example: Corporate Flight Bookings (LC 1109), Example 1: bookings = [[1, 2, 10], [2, 3, 20], [2, 5, 25]], n = 5
Mistake: raises IndexErrorFix: returns [10, 55, 45, 25, 25]
Gotcha 2: Using the 1-indexed flight numbers as list indices
Mistake
```
diff[first] += seats
diff[last + 1] -= seats
```
Fix
```
diff[first - 1] += seats
diff[last] -= seats
```
What happens: Flights are numbered from 1, but diff is indexed from 0. So flight first is at index first - 1. The end mark goes right after flight last, at index last. Without the shift, every booking lands one flight too late.
Example: bookings = [[1, 2, 10]], n = 3
Mistake: returns [0, 10, 10]Fix: returns [10, 10, 0]
Gotcha 3: Applying a running shift without % 26
Mistake
```
chr(ord('a') + (ord(c) - ord('a') + running))
```
Fix
```
chr(ord('a') + (ord(c) - ord('a') + running) % 26)
```
What happens: Shifting Letters II (LC 2381) marks +1 for a forward shift and -1 for a backward shift. The running total can be negative or larger than 25. Take the new position modulo 26 before you turn it into a letter. Python's % returns a value from 0 to 25, even for a negative number.

Not this one if…

The positions are huge or not whole numbers, as in Meeting Rooms II (LC 253), so you can't allocate one slot per position; sort the start and end events instead. See Sweep Line
Updates and sum queries arrive mixed together, as in Range Sum Query - Mutable (LC 307), so values must be readable between updates. See Fenwick Tree

Deep Dive

Why two marks describe a whole range

The Prefix Sums card turns a list of values into running totals. A difference array is the reverse. You write marks into diff, and one prefix sum over diff gives the final values.

The method works because all updates come before any read. If reads are mixed with updates, one prefix sum at the end is not enough. The Fenwick Tree card handles that case.

Corporate Flight Bookings traced

The input is bookings = [[1, 2, 10], [2, 3, 20], [2, 5, 25]] and n = 5. The flights are numbered from 1, and diff is indexed from 0, so flight first is at diff[first - 1].

Booking [1, 2, 10] writes diff[0] += 10 and diff[2] -= 10. Booking [2, 3, 20] writes diff[1] += 20 and diff[3] -= 20. Booking [2, 5, 25] writes diff[1] += 25 and diff[5] -= 25.

The result is diff = [10, 45, -10, -20, 0, -25]. The running totals are 10, 55, 45, 25, 25, which is the answer of the problem.

The last write is diff[5]. A booking that ends on the last flight writes at index n, so diff needs n + 1 slots. With n slots, Python raises an IndexError.

The end mark, and the same card with 0-indexed ranges

In Shifting Letters II (LC 2381), the mark is +1 for a forward shift and -1 for a backward shift. The running total can be negative or larger than 25, so take the final position modulo 26.

60-Second Pitch

Common Questions

Why does one prefix sum over the marks give the right totals?: The running total at flight i + 1 is the sum of all marks at or before it. A +seats mark counts for every flight from the start of its range. The matching -seats mark cancels it after the end. So a booking adds seats only inside its range.
Why does diff need n + 1 slots?: A booking that ends on the last flight writes its end mark at index n. A list of n slots has indices 0 to n - 1, so that write fails. The extra slot is never read for an answer.
How do you handle 0-indexed inclusive ranges, as in Range Addition (LC 370)?: Write diff[start] += inc and diff[end + 1] -= inc. The end mark goes one position past the last position of the range. Use n + 1 slots, or skip the write when end + 1 equals n.
When is a difference array the wrong tool?: It is wrong when reads come between updates. It is also wrong when the positions are huge numbers or not whole numbers, because one slot per position does not fit in memory. The Sweep Line card sorts the start and end events for that case.
What is the cost, compared with updating every position?: The marks cost O(1) per update and the final pass costs O(N), so the total is O(Q + N). Updating every position of every range costs up to O(Q * N).

SWE Reasoning

Spot it

Many updates each add a value to a whole range, and the values are read only after all updates.
The question asks for every final value, or for how many ranges cover each point.
The positions are small whole numbers, so one slot per position fits in memory.
Example problems: Corporate Flight Bookings (LC 1109), Range Addition (LC 370), Car Pooling (LC 1094).

The invariant, step by step

diff starts as n + 1 zeros.
A booking writes +seats at diff[first - 1] and -seats at diff[last].
The sum diff[0] + ... + diff[i] counts the +seats marks at or before flight i + 1, minus the -seats marks at or before it.
A booking is counted exactly when first - 1 <= i and last > i, which means flight i + 1 is inside its range.
So the sum is the total booked on flight i + 1, and the loop running += diff[i] computes it for every flight.

Traps

Making diff only n slots long. A booking that ends on the last flight writes at diff[n] and raises an IndexError.
Using the 1-indexed flight numbers as list indices. Every booking shifts one flight too late. For [[1, 2, 10]] and n = 3, the result is [0, 10, 10] instead of [10, 10, 0].
Putting the end mark on the last position of the range. The -seats then cancels the last flight too early.
Reading values between updates. Marks give correct values only after the prefix sum, so reads and updates cannot be mixed.

Practice

Theory Context•Two Pointers & Sliding Window

Builds on Prefix Sum Map and Prefix Sums, which you haven’t finished yet.

P2MediumBuilt on Prefix Sums~3 min speedrun

Difference Array (Range Updates)

Built on

Prefix SumsWrite a mark at each end of a range, then take one prefix sum to read the total at every position.

Corporate Flight Bookings (LC 1109)(opens leetcode.com)

Example 1

Input:bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5

Output:[10,55,45,25,25]

Booking 1 adds 10 to flights 1-2, booking 2 adds 20 to flights 2-3, and booking 3 adds 25 to flights 2-5. Flight 2 gets 10 + 20 + 25 = 55, flight 3 gets 20 + 25 = 45, and so on.

Difference Array

range updates ➔ +v at the start, -v just past the end ➔ one prefix sum

Spot it when: Many range updates arrive first and you only read the values after all of them (offline), or you need how many ranges cover each point.

Difference Array

Python

1	def corp_flight_bookings(bookings: list[list[int]], n: int) -> list[int]:
2	"""Corporate Flight Bookings: range adds via a difference array, read once by prefix sum.
3	Time: O(Q + N) \| Space: O(N)
4	"""
5	diff = [0] * (n + 1) # One extra slot so last + 1 never overflows
6	# 1. Mark Each Range's Start And End:
7	# Adding seats to every flight from first to last only changes the running total at two points: where the range starts, and one past where it ends.
8	for first, last, seats in bookings:
9	diff[first - 1] += seats # Range starts here (1-indexed input)
10	diff[last] -= seats # Range ends after flight `last`
11
12	# 2. Rebuild Every Total With One Prefix Sum:
13	# running accumulates diff left to right, so it equals the sum of every mark placed at or before i, which is exactly the total booked on flight i + 1.
14	answer, running = [], 0
15	for i in range(n):
16	running += diff[i]
17	answer.append(running)
18	return answer

Invariant: Once every booking is marked, diff[0] + ... + diff[i] is the total booked on flight i + 1.

See it run

Difference Array, step by step

running 0

The top row is diff. The bottom row is the answer. Slot i belongs to flight i + 1, and the last slot belongs to no flight.

start mark a slot that gets +seats where a booking starts
end mark a slot that gets -seats just after a booking ends
read the diff slot added to running in this step
total the finished total of one flight

Start: 5 flights and 3 bookings. diff has 6 slots: one per flight and one extra slot at the end.

diff

answer

1 / 13

Gotchas1 of 3

The trap
Gotcha 1: Making diff only n slots long
Mistake
```
diff = [0] * n
```
Fix
```
diff = [0] * (n + 1)
```
What happens: A booking that ends on the last flight writes its end mark at diff[last], which is diff[n]. A list of n slots has indices 0 to n - 1 only. So Python raises an IndexError on that write.
Example: Corporate Flight Bookings (LC 1109), Example 1: bookings = [[1, 2, 10], [2, 3, 20], [2, 5, 25]], n = 5
Mistake: raises IndexErrorFix: returns [10, 55, 45, 25, 25]
Gotcha 2: Using the 1-indexed flight numbers as list indices
Mistake
```
diff[first] += seats
diff[last + 1] -= seats
```
Fix
```
diff[first - 1] += seats
diff[last] -= seats
```
What happens: Flights are numbered from 1, but diff is indexed from 0. So flight first is at index first - 1. The end mark goes right after flight last, at index last. Without the shift, every booking lands one flight too late.
Example: bookings = [[1, 2, 10]], n = 3
Mistake: returns [0, 10, 10]Fix: returns [10, 10, 0]
Gotcha 3: Applying a running shift without % 26
Mistake
```
chr(ord('a') + (ord(c) - ord('a') + running))
```
Fix
```
chr(ord('a') + (ord(c) - ord('a') + running) % 26)
```
What happens: Shifting Letters II (LC 2381) marks +1 for a forward shift and -1 for a backward shift. The running total can be negative or larger than 25. Take the new position modulo 26 before you turn it into a letter. Python's % returns a value from 0 to 25, even for a negative number.

Not this one if…

The positions are huge or not whole numbers, as in Meeting Rooms II (LC 253), so you can't allocate one slot per position; sort the start and end events instead. See Sweep Line
Updates and sum queries arrive mixed together, as in Range Sum Query - Mutable (LC 307), so values must be readable between updates. See Fenwick Tree

Deep Dive

Why two marks describe a whole range

The Prefix Sums card turns a list of values into running totals. A difference array is the reverse. You write marks into diff, and one prefix sum over diff gives the final values.

The method works because all updates come before any read. If reads are mixed with updates, one prefix sum at the end is not enough. The Fenwick Tree card handles that case.

Corporate Flight Bookings traced

The input is bookings = [[1, 2, 10], [2, 3, 20], [2, 5, 25]] and n = 5. The flights are numbered from 1, and diff is indexed from 0, so flight first is at diff[first - 1].

Booking [1, 2, 10] writes diff[0] += 10 and diff[2] -= 10. Booking [2, 3, 20] writes diff[1] += 20 and diff[3] -= 20. Booking [2, 5, 25] writes diff[1] += 25 and diff[5] -= 25.

The result is diff = [10, 45, -10, -20, 0, -25]. The running totals are 10, 55, 45, 25, 25, which is the answer of the problem.

The last write is diff[5]. A booking that ends on the last flight writes at index n, so diff needs n + 1 slots. With n slots, Python raises an IndexError.

The end mark, and the same card with 0-indexed ranges

In Shifting Letters II (LC 2381), the mark is +1 for a forward shift and -1 for a backward shift. The running total can be negative or larger than 25, so take the final position modulo 26.

60-Second Pitch

Common Questions

Why does one prefix sum over the marks give the right totals?: The running total at flight i + 1 is the sum of all marks at or before it. A +seats mark counts for every flight from the start of its range. The matching -seats mark cancels it after the end. So a booking adds seats only inside its range.
Why does diff need n + 1 slots?: A booking that ends on the last flight writes its end mark at index n. A list of n slots has indices 0 to n - 1, so that write fails. The extra slot is never read for an answer.
How do you handle 0-indexed inclusive ranges, as in Range Addition (LC 370)?: Write diff[start] += inc and diff[end + 1] -= inc. The end mark goes one position past the last position of the range. Use n + 1 slots, or skip the write when end + 1 equals n.
When is a difference array the wrong tool?: It is wrong when reads come between updates. It is also wrong when the positions are huge numbers or not whole numbers, because one slot per position does not fit in memory. The Sweep Line card sorts the start and end events for that case.
What is the cost, compared with updating every position?: The marks cost O(1) per update and the final pass costs O(N), so the total is O(Q + N). Updating every position of every range costs up to O(Q * N).

SWE Reasoning

Spot it

Many updates each add a value to a whole range, and the values are read only after all updates.
The question asks for every final value, or for how many ranges cover each point.
The positions are small whole numbers, so one slot per position fits in memory.
Example problems: Corporate Flight Bookings (LC 1109), Range Addition (LC 370), Car Pooling (LC 1094).

The invariant, step by step

diff starts as n + 1 zeros.
A booking writes +seats at diff[first - 1] and -seats at diff[last].
The sum diff[0] + ... + diff[i] counts the +seats marks at or before flight i + 1, minus the -seats marks at or before it.
A booking is counted exactly when first - 1 <= i and last > i, which means flight i + 1 is inside its range.
So the sum is the total booked on flight i + 1, and the loop running += diff[i] computes it for every flight.

Traps

Making diff only n slots long. A booking that ends on the last flight writes at diff[n] and raises an IndexError.
Using the 1-indexed flight numbers as list indices. Every booking shifts one flight too late. For [[1, 2, 10]] and n = 3, the result is [0, 10, 10] instead of [10, 10, 0].
Putting the end mark on the last position of the range. The -seats then cancels the last flight too early.
Reading values between updates. Marks give correct values only after the prefix sum, so reads and updates cannot be mixed.