Difference Array | Range update query in O(1)

Difficulty Level Hard
Frequently asked in Arcesium CodeNation Directi Expedia Google Qualcomm
Array Query ProblemViews 1925

You are given an integer array and two types of queries, one is to add a given number in a range and the other to print the whole array. The problem “Difference Array | Range update query in O(1)” requires us to perform the range updates in O(1).

Example

arr[] = {20, 30, 25, 50}

Update(0, 1, 10)

print()

update(0, 2, 20)

update(2, 3, 30)

print()
(30 40 25 50) (50 60 75 80)

Explanation

10 will be added to 20 and 30, so the array will become {30, 40, 25, 50}

Then we will print the whole array.

20 will be added to 30, 40, and 25, so the array will become {50, 60, 45, 50}

10 will be added to 45 and 50, so the array will become {50, 60, 75, 80}

Then again we will print the whole array.

The two sets of values will be printed after performing the queries.

Difference Array | Range update query in O(1)

 

Algorithm for Difference Array

  1. Create an array of the same size as the given array.
  2. Initialize the first index as given array’s first element, and last index with 0. And all other indices are filled with difference of current and previous element.
  3. For every update query, add the value X to the given left index of the created array and subtract X from the right index of the created array.
  4. For every print query, first we fill the input array using the formula A[i] = D[i] + A[i-1]. Then print the values.

Explanation

Given an array and a number and two types of queries. So we have to perform the two types of queries. We will have two numbers representing a range along with a number X. So, our task is to add the number X to all the indices between the given range. One of the methods could be to use a naive approach. For that, traverse the given array each time whenever we need to update the values.

A better solution is discussed here, which is to create an extra array that stores the difference. That’s why it is being called a difference array. First, initialize the first element of the difference array as the first element of the input array. Then assign the last element of the difference array to 0. After that, we are going to traverse through the array and store the difference of the current value and previous value at the current index in the difference array.

We will get the values as a range, if we get an update query. Along with we are also provided with a number. Then we are going to add that number at the left index of the range in difference array. Similarly subtract the value X from the right index of the difference array. For printing the array we will traverse through the array and for the zero index value we will update the value of the given array as the array we created, else we will get the sum of the created array and the previous value of the given array and print that value for the particular index.

Code

Implementation in C++ for Difference Array

#include<iostream>

using namespace std;

void buildArray(int arr[], int dummyArray[], int n)
{
    dummyArray[0] = arr[0];
    dummyArray[n] = 0;
    for (int i = 1; i < n; i++)
        dummyArray[i] = arr[i] - arr[i - 1];
}

static void update(int dummyArray[], int l, int r, int x)
{
    dummyArray[l] += x;
    dummyArray[r + 1] -= x;
}

void printArray(int arr[], int dummyArray[], int n)
{
    for (int i = 0; i <n; i++)
    {

        if (i == 0)
            arr[i] = dummyArray[i];
        else
            arr[i] = dummyArray[i] + arr[i - 1];

        cout<<arr[i] << " ";
    }

    cout<<endl;
}

int main()
{
    int arr[] = {20,30,25,50};
    int n = sizeof(arr)/sizeof(arr[0]);

    int dummyArray[n + 1];
    buildArray(arr, dummyArray, n);

    update(dummyArray, 0, 1, 10);
    printArray(arr, dummyArray, n);
    update(dummyArray, 0, 2, 20);
    update(dummyArray, 2, 3, 30);

    printArray(arr, dummyArray,n);
    return 0;
}

30 40 25 50
50 60 75 80

Implementation in Java for Difference Array

class differenceArray
{
    static void buildArray(int arr[], int dummyArray[])
    {

        int n = arr.length;

        dummyArray[0] = arr[0];
        dummyArray[n] = 0;
        for (int i = 1; i < n; i++)
            dummyArray[i] = arr[i] - arr[i - 1];
    }
    
    static void update(int dummyArray[], int left, int right, int x)
    {
        dummyArray[left] += x;
        dummyArray[right + 1] -= x;
    }
    
    static int printArray(int arr[], int dummyArray[])
    {
        for (int i = 0; i < arr.length; i++)
        {
            if (i == 0)
                arr[i] = dummyArray[i];
            else
                arr[i] = dummyArray[i] + arr[i - 1];

            System.out.print(arr[i] + " ");
        }

        System.out.println();

        return 0;
    }
    
    public static void main(String[] args)
    {
        int arr[] = {20, 30, 25, 50};
        int n = arr.length;
        int dummyArray[] = new int[n + 1];

        buildArray(arr, dummyArray);

        update(dummyArray, 0, 1, 10);
        printArray(arr, dummyArray);
        update(dummyArray, 0, 2, 20);
        update(dummyArray, 2, 3, 30);

        printArray(arr, dummyArray);
    }
}

30 40 25 50
50 60 75 80

Complexity Analysis

Time Complexity

O(q) where “q” is the number of print queries executed as an update query takes O(1) time.

Space Complexity

O(n) where “n” is the number of elements in the array. Since we created an extra difference array, we have linear space complexity.

Translate »