Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each 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
between the indices and
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:
- int n - the number of elements in the array
- int queries[q][3] - a two dimensional array of queries where each queries[i] contains three integers, a, b, and k.
Returns
- 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 m lines contains three space-separated integers a, b and k he left index, right index and summand.
Constraints
- 3 <= n <= 10**7
- 1 <= m <= 2 * 10**5
- 1 <= a <= b <= n
- 0 <= k <= 10**9
Sample Input
5 3
1 2 100
2 5 100
3 4 100
Sample Output
200
Explanation
After the first update the list is 100 100 0 0 0.
After the second update list is 100 200 100 100 100.
After the third update list is 100 200 200 200 100.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include<stdio.h>
long A[10000009] = {0},CF[10000009 + 1] = {0};
int main()
{
long N,Q;
long val,left,right,i,count = 0;
long maxv = -1;
scanf("%ld%ld",&N,&Q);
for(i = 0; i < Q; i++)
{
scanf("%ld%ld%ld",&left,&right,&val);
CF[left - 1] += val;
CF[right] -= val;
}
for(i = 0; i < N; i++)
{
count += CF[i];
A[i] = count;
if(count > maxv) maxv = count;
}
printf("%ld\n",maxv);
return 0;
}
#2 Code Example with C++ Programming
Code -
C++ Programming
#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;
}
#3 Code Example with Java Programming
Code -
Java Programming
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long size = scanner.nextLong();
Map < Long, Long> map = new HashMap<>();
long operations = scanner.nextLong();
for (long i = 0; i < operations; i++) {
long start = scanner.nextLong();
long end = scanner.nextLong();
long value = scanner.nextLong();
map.put(start, (map.containsKey(start) ? map.get(start) : 0) + value);
map.put(end + 1, (map.containsKey(end + 1) ? map.get(end + 1) : 0) - value);
}
long max = 0;
long value = 0;
for (long i = 0; i < size; i++) {
value += (map.containsKey(i + 1) ? map.get(i + 1) : 0);
max = Math.max(max, value);
}
System.out.println(max);
}
}
#4 Code Example with Javascript Programming
Code -
Javascript Programming
function processData(input) {
var splitInput = input.split("\n");
var listSize = parseInt(splitInput[0].split(" ")[0]);
var numInserts = parseInt(splitInput[0].split(" ")[1]);
var max = 0;
var amounts = Array(listSize);
for (var i = 0; i < numInserts; i++) {
// input is 1 based
var start = parseInt(splitInput[i+1].split(" ")[0]) - 1;
var end = parseInt(splitInput[i+1].split(" ")[1]);
var amount = parseInt(splitInput[i+1].split(" ")[2]);
amounts[start] = amounts[start] || 0;
amounts[start] = amounts[start] + amount;
amounts[end] = amounts[end] || 0;
amounts[end] = amounts[end] - amount;
}
var current = 0;
for (var i = 0; i < listSize; i++) {
current += (amounts[i] || 0);
if (current > max) {
max = current;
}
}
console.log(max);
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});
#5 Code Example with Python Programming
Code -
Python Programming
import itertools, sys
if __name__ == '__main__':
N, M = list(map(int, sys.stdin.readline().split()))
x = [0] * N
for _ in range(M):
a, b, k = list(map(int, sys.stdin.readline().split()))
x[a - 1] += k
if b < N:
x[b] -= k
print(max(itertools.accumulate(x)))