Array Manipulation


Problem Statement :


Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array.

Example:
n=10
queries=[[1,5,3], [4,8,7], [6,9,1]]

Queries are interpreted as follows:

    a b k
    1 5 3
    4 8 7
    6 9 1

Add the values of k between the indices a and b inclusive:

index->	 1 2 3  4  5 6 7 8 9 10
	[0,0,0, 0, 0,0,0,0,0, 0]
	[3,3,3, 3, 3,0,0,0,0, 0]
	[3,3,3,10,10,7,7,7,0, 0]
	[3,3,3,10,10,8,8,8,1, 0]

The largest value is 10 after all operations are performed.


Function Description:

Complete the function arrayManipulation in the editor below.

arrayManipulation has the following parameters:

i   1. nt n - the number of elements in the array
    2.int queries[q][3] - a two dimensional array of queries where each queries[i] contains three integers, a, b, and k.

Returns:
     1. int - the maximum value in the resultant array


Input Format:

The first line contains two space-separated integers n and m, the size of the array and the number of operations.
Each of the next  lines contains three space-separated integers a, b and k, the left index, right index and summand.


Constraints:
    1.  3<=n<=10^7
    2.  1<=m<=2*10^5
    3.  1<=a,b<=n
    4.  0<=k<=10^9



Solution :


                        In C:

#include <stdio.h>

long long arr[10000005];
long long diff[10000005];
    
int main(void)
{
    int a,b,k,n,m,i;
    long long max,val;
    
    scanf("%d%d",&n,&m);
    
    
    while(m--)
    {
    	scanf("%d%d%d",&a,&b,&k);
    	
    	if(a==1)
    	{
    	 arr[1] += k; 
    	
     	 if(b<n)
    	  diff[b] -= k;
    	}
    	else if(b<n)
    	{
    	 diff[a-1] += k;
    	 diff[b] -= k;
    	}
    	else if(b==n)
    	 diff[a-1] += k;
    }
    
    max = arr[1];
    val = arr[1];
    
    for(i=1;i<n;i++)
    {
      val += diff[i];
      if(val > max)
       max = val;
    } 
    
    printf("%lld\n",max);
    
	return 0;
}








In C++:

#include <iostream>

using namespace std;
const int NMAX = 1e7+2;
long long a[NMAX];
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i=1;i<=m;++i){
        int x, y, k;
        cin >> x >> y >> k;
        a[x] += k;
        a[y+1] -= k;
    }
    long long x = 0,sol=-(1LL<<60);
    for(int i=1;i<=n;++i){
        x += a[i];
        sol = max(sol,x);
    }
    cout<<sol<<"\n";
    return 0;
}








In Java:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;


public class Solution {

	public static void main(String[] args) throws Exception {
		new Solution().run();
	}
	
	StreamTokenizer st;
	
	private void run() throws Exception {
		st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		int n = nextInt();
		int m = nextInt();
		long[] a = new long[n + 1];
		for (int i = 0; i < m; i++) {
			int l = nextInt() - 1;
			int r = nextInt();
			int v = nextInt();
			a[l] += v;
			a[r] -= v;
		}
		long cur = 0;
		long max = 0;
		for (int i = 0; i < n; i++) {
			cur += a[i];
			max = Math.max(max, cur);
		}
		System.out.println(max);
	}

	private int nextInt() throws Exception {
		st.nextToken();
		return (int) st.nval;
	}
}









In Python 3:

N,M = [int(_) for _ in input().split(' ')]

Is = {}
for m in range(M) :
    a,b,k = [int(_) for _ in input().strip().split(' ')]
    if k == 0 :
        continue
    Is[a] = Is.get(a,0) + k
    Is[b+1] = Is.get(b+1,0) - k
    
m,v = 0,0
for i in sorted(Is) :
    v += Is[i]
    if v > m :
        m = v

print(m)