Skip to main content

Special Techniques

Difference Array​

  • Overview:

  • A very efficient technique when facing problems where we have to perform range update operations on an array. Instead of updating all elements within a range for each operation, you update just two elements (or sometimes three, depending on implementation) in a difference array and use prefix sums to compute the resulting array.

Intuition Behind Difference Array

  • The main idea is to represent the range update in a compact form: • Instead of updating all elements within a range [l, r] of the original array, you update just the start (l) and end (r+1) indices in a separate array (the difference array). • Later, you can compute the cumulative effect of these updates by taking the prefix sum of the difference array, which restores the original array with all updates applied.

  • This reduces the time complexity of each range update operation from O(n) to O(1), making it especially useful when there are many such operations.

  • This problem demonstrate the technique directly

def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
    diff = [0] * (length + 1)
    for start, end, val in updates:
        diff[start] += val
        diff[end+1] -= val
    
    res = [0] * length
    cur_sum = 0
    for i in range(length):
        cur_sum += diff[i]
        res[i] = cur_sum
    
    return res

When to Use​

  1. Multiple Range Update Queries: • If you have a problem where you need to update ranges frequently (e.g., increment or decrement values within a subarray), this technique is ideal.
  2. Static Query* • If the problem requires querying or printing the final state of an array after applying all range updates, this technique is a good fit. • For example, you perform range updates on an array, and at the end, you need to know the array’s values.
  3. Increment/Decrement Operations: • This technique is best suited for additive updates. For other types of updates (like multiplication, setting a specific value, etc.), you may need modifications.
  4. Unordered Queries: • When the order of updates doesn’t matter, you can accumulate all updates and apply them in a single pass, making the technique more efficient.

Problems​

  • https://leetcode.com/problems/range-addition
  • Car Pooling: https://leetcode.com/problems/car-pooling
    • Each trip adds passengers at the startLocation and removes them at the endLocation.
    • This corresponds to a range update problem:
      • Add numPassengers to the range [startLocation, endLocation - 1].
    • Notices that we initiate the difference array with size of max end time instead of length of trips => We want the difference array to contains all the range the operation can happens, which sometimes we have to define ourselves
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        max_time = max(t[2] for t in trips) + 1
        passengers = [0] * (max_time +1)

        for val, start, end in trips:
            passengers[start] += val
            passengers[end] -= val

        cur_pass = 0
        for change in passengers:
            cur_pass += change
            if cur_pass > capacity:
                return False
        
        return True
def isCovered(self, ranges: List[List[int]], left: int, right: int) -> bool:
        max_range = max([r[1] for r in ranges])
        diff = [0] * (max_range + 2)

        for start, end in ranges:
            diff[start] += 1
            diff[end+1] -=1

        cur_sum = 0
        for  i in range(len(diff)):
            cur_sum += diff[i]
            diff[i] = cur_sum
            if i == left:
                if diff[i] > 0:
                    left += 1
                else:
                    return False
            if left > right:
                return True
        
        return False
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
    max_time = max([interval[1] for interval in intervals])
    diff = [0] * (max_time + 2)

    for start, end in intervals:
        diff[start] += 1
        diff[end] -= 1
    
    res = 0
    cur_sum = 0
    for val in diff:
        cur_sum += val
        res = max(res, cur_sum)

    return res

https://leetcode.com/problems/brightest-position-on-street

  • Can also use HashMap to store difference
def brightestPosition(self, lights: List[List[int]]) -> int:
    diff = collections.defaultdict(int)

    for i, dist in lights:
        diff[i-dist] += 1
        diff[i+dist+1] -= 1

    cur_sum = 0
    max_idx = 0
    max_val = 0

    for idx, val in sorted(diff.items()):
        cur_sum += val
        if cur_sum > max_val:
            max_val = cur_sum
            max_idx = idx
    
    return max_idx

Lazy Propagation​

  • We can also think about this as a Lazy Propagation strategy, where we delays a calculation until we absolutely need it

https://leetcode.com/problems/design-a-stack-with-increment-operation/

  • This problem even though not directly uses this [[Special Techniques#Difference Array]] techniques but has the same core idea of trying to delay the increment operation until we actually need the value (during pop operation)
class CustomStack:
    def __init__(self, maxSize: int):
        self.maxSize = maxSize
        self.stack = [0] * maxSize
        self.inc = [0] * maxSize
        self.topIndex = -1

    def push(self, x: int) -> None:
        if self.topIndex < self.maxSize - 1:
            self.topIndex += 1
            self.stack[self.topIndex] = x

    def pop(self) -> int:
        if self.topIndex < 0:
            return -1
        
        result = self.stack[self.topIndex] + self.inc[self.topIndex]

        if self.topIndex > 0:
            self.inc[self.topIndex - 1] += self.inc[self.topIndex]

        self.inc[self.topIndex] = 0
        self.topIndex -= 1
        return result

    def increment(self, k: int, val: int) -> None:
        if self.topIndex >= 0:
            index = min(self.topIndex, k - 1)
            self.inc[index] += val