Difference Array

Today I am going to introduce you to a pretty cool algorithm, which would allow you to update multiple ranges in an array in O(n) time !

Let’s say you got an array, and you need to update ranges of it with given values. So as an input you would receive a two dimensional array with inclusive ranges and a values to update, i.e. [[1 4 5], [2 3 7]]. So it means update your array starting with index 1 and finishing on index 4 with a value of 5, then update your array starting at index 2 finish at index 3 with value of 7.

If the original array would be [0 0 0 0 0 0 0]

After the first update it would be equal to [0 5 5 5 5 0 0]

After the second update it would be equal to [0 5 12 12 5 0 0]

So one possible naive approach is really simple and it would involve going through the array with two loops, something like (in pseudo code):

for each_update_row in update_values
     start = get_start_from_update_values()
     end = get_end_from_update_values()
     value_to_update = get_update_value_from_update_values()
     
     for index in original_array
         if index between start and end
             update original_array with value_to_update

Possible implementation in python:

def naive_update(num_of_update_rows, update_values):
    array = [0] * num_of_update_rows
    for update_index in range(len(update_values)):
        start = update_values[update_index][0]
        end = update_values[update_index][1]
        value = update_values[update_index][2]

        for index in range(len(array)):
            if index >= start and index <= end:
                array[index] += value

Which works well for small inputs, but it has a O(n²) time complexity. So we can do better then that!

Difference Array comes to the rescue !

Who said you have to update all the values in a given range? Apparently it is enough if you just update the first index with the required value and the one past the end index with the same required value but negative.

So, instead of updating original array from [0 0 0 0 0 0 0] to [0 5 5 5 5 0 0],

you update it as follows: [ 0 5 0 0 -5 0 0]

And the second update, from [ 0 5 0 0 -5 0 0] to [0 5 7 0 -7 -5 0],

Note: If you would want to update up to last index in the array then you would just ignore adding a negative value to the array as you would already reached the end of it.

The new approach using difference array (in pseudo code):

for each_update_row in update_values
      start = get_start_from_update_values()
      end = get_end_from_update_values()
      value_to_update = get_update_value_from_update_values()

      update original_array[start] with value_to_update

      if end is <= to the last index in original array
          update original_array[end + 1] with -value_to_update

Possible implementation in python:

def improved_update(num_of_update_rows, update_values):
    array = [0] * num_of_update_rows
    for update_index in range(len(update_values)):
        start = update_values[update_index][0]
        end = update_values[update_index][1]
        value = update_values[update_index][2]

        array[start] += value

        if end + 1 <= len(array) - 1:
        	array[end + 1] -= value

Now we have achieved the same results but with O(n) complexity, how cool is that?!

If you want to reconstruct a “normal” array from the difference array, you would need to go through it and add a value of a previous index to the current one, starting from index = 1. If you would do that on our after second update difference array [0 5 7 0 -7 -5 0] you would get [0 5 12 12 5 0 0], which equals what we have achieved with our naive solution.