Using Difference Array Pattern
1. Building Difference Array
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Initialize | Create a difference array of size n with all zeros | O(n) | O(n) |
| Update Range | Add value to range [l, r] using difference array technique | O(1) | O(1) |
| Reconstruct | Convert difference array back to original array | O(n) | O(1) |
Example: Building Difference Array
function buildDifferenceArray(n, updates) {
const diff = new Array(n).fill(0);
// Apply updates to difference array
for (const [l, r, inc] of updates) {
diff[l] += inc;
if (r + 1 < n) {
diff[r + 1] -= inc;
}
}
// Reconstruct original array from difference array
const result = new Array(n);
result[0] = diff[0];
for (let i = 1; i < n; i++) {
result[i] = result[i - 1] + diff[i];
}
return result;
}
// Example usage:
const updates = [[2, 4, 10], [3, 5, 15]];
const result = buildDifferenceArray(6, updates);
console.log(result); // [0, 0, 10, 25, 25, 15]
2. Constructing Difference Array
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Initialize | Create a difference array of size n+1 with all zeros | O(n) | O(n) |
| Update Range | For range [l, r] with value v: diff[l] += v, diff[r+1] -= v |
O(1) | O(1) |
| Compute Prefix Sum | Convert difference array to actual array: arr[i] = arr[i-1] + diff[i] |
O(n) | O(1) |
Example: Range Update Operations
const n = 5;
const diff = new Array(n + 1).fill(0);
// Range update: [1, 3] with value 2
diff[1] += 2;
diff[4] -= 2;
// Compute actual array
const arr = new Array(n);
arr[0] = diff[0];
for (let i = 1; i < n; i++) {
arr[i] = arr[i-1] + diff[i];
}
console.log(arr); // [0, 2, 2, 2, 0]
3. Implementing Range Update
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| rangeUpdate(array, left, right, value) | Updates all elements from index left to right by adding value |
O(1) | O(1) |
Example: Range Update Implementation
function rangeUpdate(array, left, right, value) {
array[left] += value;
if (right + 1 < array.length) {
array[right + 1] -= value;
}
}
// Example usage:
const arr = [0, 0, 0, 0, 0];
rangeUpdate(arr, 1, 3, 5);
console.log(arr); // [0, 5, 0, -5, 0]
Note: The difference array technique requires a separate pass to compute the actual values using prefix sums.
4. Computing Final Array
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Build Difference Array | Initialize difference array with zeros, apply range updates using start and end indices. | O(n + k) | O(n) |
| Reconstruct Final Array | Compute prefix sum of difference array to get the actual values. | O(n) | O(1) extra |
Example: Building and Using Difference Array
const n = 5;
const diff = new Array(n + 1).fill(0);
// Range update: [1, 3] with value 2
diff[1] += 2;
diff[4] -= 2;
// Compute prefix sum to get final array
const result = new Array(n);
result[0] = diff[0];
for (let i = 1; i < n; i++) {
result[i] = result[i - 1] + diff[i];
}
console.log(result); // [0, 2, 2, 2, 0]
Note: The difference array technique is particularly useful for handling multiple range updates efficiently.
5. Solving Range Addition
The Difference Array pattern is particularly useful for efficiently handling range updates and queries. It allows us to perform multiple range updates in O(1) time and then compute the final array in O(n) time.
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Range Update | Add a value to all elements in a range [left, right] | O(1) | O(1) |
| Final Array Computation | Compute the actual array from difference array | O(n) | O(1) |
Example: Range Addition
function getModifiedArray(length, updates) {
const diff = new Array(length + 1).fill(0);
// Apply range updates
for (const [start, end, inc] of updates) {
diff[start] += inc;
diff[end + 1] -= inc;
}
// Compute final array
const result = new Array(length);
result[0] = diff[0];
for (let i = 1; i < length; i++) {
result[i] = result[i - 1] + diff[i];
}
return result;
}
// Example usage
const length = 5;
const updates = [[1, 3, 2], [2, 4, 3], [0, 2, -2]];
console.log(getModifiedArray(length, updates)); // [-2, 0, 4, 4, 3]
Note: The difference array is extended by one element to simplify boundary handling.
Key Points
- Use a difference array to efficiently apply multiple range updates.
- Each update modifies only two positions in the difference array.
- The final array is computed by taking prefix sums of the difference array.
6. Implementing 2D Difference Array
Example: 2D Difference Array Implementation
class DifferenceArray2D {
constructor(rows, cols) {
this.diff = Array(rows).fill().map(() => Array(cols).fill(0));
this.rows = rows;
this.cols = cols;
}
updateRange(row1, col1, row2, col2, inc) {
this.diff[row1][col1] += inc;
if (row2 + 1 < this.rows) {
this.diff[row2 + 1][col1] -= inc;
}
if (col2 + 1 < this.cols) {
this.diff[row1][col2 + 1] -= inc;
}
if (row2 + 1 < this.rows && col2 + 1 < this.cols) {
this.diff[row2 + 1][col2 + 1] += inc;
}
}
getResult() {
const result = Array(this.rows).fill().map(() => Array(this.cols).fill(0));
result[0][0] = this.diff[0][0];
for (let i = 1; i < this.rows; i++) {
result[i][0] = result[i - 1][0] + this.diff[i][0];
}
for (let j = 1; j < this.cols; j++) {
result[0][j] = result[0][j - 1] + this.diff[0][j];
}
for (let i = 1; i < this.rows; i++) {
for (let j = 1; j < this.cols; j++) {
result[i][j] = result[i - 1][j] + result[i][j - 1] - result[i - 1][j - 1] + this.diff[i][j];
}
}
return result;
}
}
// Example usage:
const diff2D = new DifferenceArray2D(3, 3);
diff2D.updateRange(0, 0, 1, 1, 1);
const finalMatrix = diff2D.getResult();
console.log(finalMatrix); // [[1, 1, 0], [1, 1, 0], [0, 0, 0]]
| Method | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| updateRange(row1, col1, row2, col2, inc) | Updates a rectangular region in the difference array | O(1) | O(1) |
| getResult() | Computes the actual matrix from difference array | O(rows × cols) | O(rows × cols) |
Note: The 2D difference array is useful for efficiently applying multiple range updates to a matrix.
7. Applying to Car Pooling
The Difference Array pattern is particularly useful in problems involving ranges and updates, such as car pooling scenarios where we need to track how many passengers are on a vehicle at any point in time.
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Initialize Difference Array | Create an array of size n+1 initialized to zero, where n is the maximum stop index. |
O(n) | O(n) |
| Update Range | Add passengers to index start and subtract passengers from index end + 1. |
O(1) | - |
| Compute Prefix Sum | Iterate through the difference array to compute actual passenger count at each stop. | O(n) | O(1) |
Example: Car Pooling
function carPooling(trips, capacity) {
const maxStop = Math.max(...trips.map(trip => trip[2]));
const diff = new Array(maxStop + 2).fill(0);
for (const [passengers, start, end] of trips) {
diff[start] += passengers;
diff[end + 1] -= passengers;
}
let currentPassengers = 0;
for (let i = 0; i <= maxStop; i++) {
currentPassengers += diff[i];
if (currentPassengers > capacity) return false;
}
return true;
}
// Example usage:
const trips = [[2,1,5],[3,3,7]];
const capacity = 4;
console.log(carPooling(trips, capacity)); // false
Note: The difference array technique allows efficient range updates and is ideal for scenarios where we need to apply multiple range-based operations.
8. Solving Corporate Flight Bookings
The Corporate Flight Bookings problem is a classic application of the difference array pattern. It involves efficiently updating ranges in an array and then computing the final values.
Given a list of flight bookings, where each booking specifies a range of flights and the number of seats reserved for each flight in that range, we need to compute the total number of seats reserved for each flight.
Example: Corporate Flight Bookings
const corpFlightBookings = [[1, 2, 10], [2, 3, 20], [2, 5, 25]];
const n = 5;
// Difference array approach
const diff = new Array(n + 1).fill(0);
for (const [first, last, seats] of corpFlightBookings) {
diff[first - 1] += seats;
diff[last] -= seats;
}
// Compute prefix sum to get actual seat counts
const result = new Array(n).fill(0);
result[0] = diff[0];
for (let i = 1; i < n; i++) {
result[i] = result[i - 1] + diff[i];
}
console.log(result); // [10, 55, 45, 25, 25]
| Input | Description | Output |
|---|---|---|
| bookings | Array of bookings, each with [first, last, seats] | Array of total seats per flight |
| n | Number of flights (1-indexed) | Array of size n |
Note: The difference array technique allows efficient range updates in O(1) time per update, making the overall solution O(m + n), where m is the number of bookings.
9. Finding Maximum After K Operations
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Update Range | Increment values in a range [l, r] by value x | O(1) | O(1) |
| Apply Updates | Compute final array from difference array | O(n) | O(1) |
Example: Range Update Operations
const n = 5;
const diff = new Array(n + 1).fill(0);
const updates = [[1, 3, 2], [2, 4, 3], [0, 2, -1]];
// Apply updates to difference array
for (const [l, r, x] of updates) {
diff[l] += x;
diff[r + 1] -= x;
}
// Compute final array
const result = new Array(n);
result[0] = diff[0];
for (let i = 1; i < n; i++) {
result[i] = result[i - 1] + diff[i];
}
console.log(result); // [-1, 1, 5, 5, 3]
Note: The difference array technique allows efficient range updates in O(1) time per operation, making it ideal for problems involving multiple range modifications.
10. Optimizing Space Usage
Example: Difference Array for Range Updates
const diff = new Array(n + 1).fill(0);
function updateRange(left, right, value) {
diff[left] += value;
diff[right + 1] -= value;
}
function getResult() {
const result = new Array(n);
result[0] = diff[0];
for (let i = 1; i < n; i++) {
result[i] = result[i - 1] + diff[i];
}
return result;
}| Operation | Space Complexity | Description |
|---|---|---|
| Initialization | O(n) |
Creates difference array of size n+1 |
| Range Update | O(1) |
Modifies only two elements in difference array |
| Result Computation | O(n) |
Computes prefix sum to get actual values |
Note: This approach trades initial space for efficient updates. Instead of updating each element in a range, we only update the boundaries.