Hi , I have a doubt.

Here the indices are starting from 1. So, we should be subtracting 1 from both lower index and upper index. Here you have done so for lower index, but haven't done for upper index.

Can you please explain the reason behind this ?

You don't have to do this:

for(int i=0;i<n;i++) arr[i]=0;

because long by default is 0

could you please explain me the working of the code?

no need to init array elements to 0 in Java

Hi, your solution works but I am not convinced!

I don't see how do you increment all elements between lower and upper!

• arr[lower-1]+=sum; This only increments the lower element by sum.
• if(upper
• arr[upper]-=sum; I don't understand why are you substructing sum!

Can you please explain? Thanks.

Using Java 8 syntaxis:

public static void main(String[] args) {
 Scanner in = new Scanner(System.in);
 int n = in.nextInt();
 int m = in.nextInt();
 long[] output = new long[n];
 IntStream.range(0,m).forEach(i -> { int a = in.nextInt()-1;
                                    int b = in.nextInt();
                                    int k = in.nextInt();
                                    output[a] += k;
                                    if(b < n) output[b] -= k; });
 AtomicLong sum = new AtomicLong(0);
 System.out.print(LongStream.of(output).map(sum::addAndGet)
                                       .max().getAsLong());
 in.close();
}

why temp += arr[i];

Array is already 0, you dont have to assign 0s to each array elements

scanner on large lines of input is not suitable solution, it reads too long

You don't need to loop the arr to put 0. Bydefault, it has the value zero when you initialize.

In java, we don't need to loop explicitly to assign zero to all the arr locations. When we create it, it has the zero as default values. I like your solution, thanks.

using an if statement inside the for loop will just contribute in complexity. you can replace it with Math.max function.

Is there a reason all the solutions posted above are written inside main() and not the provided function arrayManipulation() ? Or did hackerrank just change this over the past few years for readability?

// Complete the arrayManipulation function below.
static long arrayManipulation(int n, int[][] queries) {

// initialize array with 0's of size n
long arr[] = new long[n];

// each successive element contains the difference between itself and previous element

for (int i = 0; i < queries.length; i++) {
// when checking query, subtract 1 from both a and b since 0 indexed array
int a = queries[i][0] - 1;
int b = queries[i][1] - 1;
int k = queries[i][2];

arr[a] += k;
if (b+1 < n) {
arr[b+1] -= k;  
}
}

// track highest val seen so far as we go
long max = Long.MIN_VALUE;
for (int i = 1; i < arr.length; i++) {
arr[i] += arr[i-1];
max = Math.max(arr[i], max);
}

return max;
}

Same solution in Golang

func arrayManipulation(n int32, qs [][]int32) int64 {
	a := make([]int64, n + 1)
	qLen := len(qs)
	for i:=0; i<qLen; i++ {
		p := int(qs[i][0])
		q := qs[i][1]
		sum := int64(qs[i][2])
		a[p] += sum
		if((q + 1) <= n) {
			a[q + 1] -= sum
		}
	}

	var x, max int64 = 0, 0
	for i:=1; i<=int(n); i++ {
		x += a[i]
		if max < x {
			max = x
		}
	}

	return max
}

Clever solution!

import java.io.; import java.math.; import java.security.; import java.text.; import java.util.; import java.util.concurrent.; import java.util.regex.*;

public class Solution {

// Complete the arrayManipulation function below.
static long arrayManipulation(int n, int[][] queries) {
  int[] arr = new int[n];
  for(int i=0;i<n;i++){
    arr[i] = 0;
  }
  int m = queries.length;
  for(int i=0;i<m;i++){
    for(int j=queries[i][0]-1;j<queries[i][1];j++){
      arr[j] += queries[i][2];
    }
  }
  int max = arr[0];
  for(int i=1;i<n;i++){
    if(arr[i]>max){
      max = arr[i];
    }
  }
  return(max);








}

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException {
    BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    String[] nm = scanner.nextLine().split(" ");

    int n = Integer.parseInt(nm[0]);

    int m = Integer.parseInt(nm[1]);

    int[][] queries = new int[m][3];

    for (int i = 0; i < m; i++) {
        String[] queriesRowItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int j = 0; j < 3; j++) {
            int queriesItem = Integer.parseInt(queriesRowItems[j]);
            queries[i][j] = queriesItem;
        }
    }

    long result = arrayManipulation(n, queries);

    bufferedWriter.write(String.valueOf(result));
    bufferedWriter.newLine();

    bufferedWriter.close();

    scanner.close();
}

}

What is wrong with this code. Please help.

Thanks for the clean code and the comment! It helped more than the entire discussion!

This line is unnecessary due to the fact that the default value of long in Java is 0L and there is no need for assigning them again to 0.

for(int i=0;i<n;i++) arr[i]=0;

Thanks for the enlightenment.

Here is the same solution in Swift:

func arrayManipulation(n: Int, queries: [[Int]]) -> Int {

    var numbers = Array(repeating: 0, count: n + 1)
    var ans = 0

    for i in 0 ..< queries.count {
        var a = queries[i][0]
        var b1 = queries[i][1] + 1
        var k = queries[i][2]

        numbers[a] += k
        
        if b1 <= n {
            numbers[b1] -= k
        }
    }

    for i in 1...n {
        numbers[i] += numbers[i - 1]
				
        if numbers[i] > ans {
            ans = numbers[i]
        }
    }
		
    return ans
}

I think

for(int i=0;i

is not needed.

very smart,here is follow output to help me understand the idea

Compilation Successful
Input (stdin)
5 1
1 2 100
Your Output (stdout)
Slope List [ 100, 0, -100, 0, 0 ]
Actual List[100,100,0,0,0]

Compilation Successful
Input (stdin)
5 2
1 2 100
2 5 100
Your Output (stdout)
Slope List [ 100, 100, -100, 0, 0 ]
Actual List[100,200,100,100,100]


Compilation Successful
Input (stdin)
5 3
1 2 100
2 5 100
3 4 100
Your Output (stdout)
Slope List [ 100, 100, 0, 0, -100 ]
Actual List[100,200,200,200,100]

why are you subtracting???? "( b < n ) res [ b ] -= k;"

The "Apply operation part" is O(k) here. In the diff array version, apply operation is O(1)

hey did u passed all with this...i used same logic in C#..but passes till 6

your code is only passing 3 test cases out of 10 . Don't post the code unless it pass all the test cases dude !!!!

Thanks, that helped understanding the optimization.

in the code there are two steps to acquire a new array filled with zeroes:

1. At first step the allocation itself: int *a=(int )malloc(sizeof(int)(n+1));
2. Second step is to propagate zero values using for-loop upon newly created array.

In my opinion, we can do the same with single call of "calloc". It supposed to be faster in theory, cause calloc is hardware dependent and probably we don't have to loop over N items again just for get them zero valued, since calloc could know is it actually required or not, so on some harware it could be already zeroes or hardware knows better how to zero during allocation faster

Yeah, if we went with the brute force solution with two nested for loops, we will get a graph as below for the array if we used the data below

arrayManipulation(40,[[19, 28, 419],
[4, 23, 680],
[5, 6, 907],
[19, 33, 582],
[5, 9, 880],
[10, 13, 438],
[21, 39, 294],
[13, 18, 678],
[12, 26, 528],
[15, 30, 261],
[8, 9, 48],
[21, 23, 131],
[20, 21, 7],
[13, 40, 65],
[13, 23, 901],
[15, 15, 914],
[14, 35, 704],
[20, 39, 522],
[10, 18, 379],
[16, 27, 8],
[25, 40, 536],
[5, 9, 190],
[17, 20, 809],
[8, 20, 453],
[22, 37, 298],
[19, 37, 112],
[2, 5, 186],
[21, 29, 184],
[23, 30, 625],
[2, 8, 960]])

but if we used the second method which is adding at the first index and subtracting at the index afer the last we get this graph

and then we can get the maximum out of summing the results as below