Algorithm


Problem Name: Data Structures - Array Manipulation

Problem Link: https://www.hackerrank.com/challenges/crush/problem?isFullScreen=true

In this HackerRank in Data Structures - Array Manipulation solutions

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.

The maximum value is 200.

 

 

 

 

 

 

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;
}
Copy The Code & Try With Live Editor

#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;
}
Copy The Code & Try With Live Editor

#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);
    }
}
Copy The Code & Try With Live Editor

#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);
});
Copy The Code & Try With Live Editor

#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)))
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Find Maximum Index Product solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Kitty's Calculations on a Tree solution in Hackerrank - Hacerrank solution C, C++, java,js, Python