# Adding k to many elements in a sequence

First line will contain two integers N and M separated by a single space. Then the next M lines will contain three integers a, b and k separated by a single space. N is the length of the sequence. M is the number of operations performed on that sequence. a is the starting index from a sequence and b is ending index from a sequence. I have to add k to all elements in between a and b. (I have to do this M times on N length sequence)

Here is my code:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Solution {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
List l= new ArrayList(Collections.nCopies(n, 0));
//System.out.println(l);

for(int i=1;i<=m;i++){
int a=sc.nextInt();
int b=sc.nextInt();
int k=sc.nextInt();
for(int j=0;j<n;j++){
//if((a-j)<=b){
if(j+1>=a && j+1<=b){
int ab= (int) l.get(j);
int sum=ab+k;
l.set(j,sum);
}
}
}
int total=0;
total=(int) l.get(0);
for(int i=0;i<n;i++){
int num=(int) l.get(i);
if(num>total){
total=num;
}
}
System.out.println(total);
}
}


Question: My code fails due to time out, and may be due to some other issues which i'm not aware of..please help to solve this or optimize my code. It works for small inputs (100 lines)..

I guess the problem is in the inner loop:

for(int j=0;j<n;j++){
if(j+1>=a && j+1<=b){
//...
}
}


If 'n' value is big and the gap between 'a' and 'b' is small enough iterations will be useless most of the time. Also in my opinion, using of int[] array is more suitable here.

You can try in this way:

public final class Solution {

public static void main(String[] args) {
final Scanner scanner = new Scanner(System.in);
final int n = scanner.nextInt();
final int m = scanner.nextInt();
final int[] l = new int[n];

for (int i = 1; i <= Math.min(m, n - 1); i++) {
final int a = Math.max(0, Math.min(scanner.nextInt() - 1, n - 1));
final int b = Math.max(0, Math.min(scanner.nextInt(), n - 1));
final int k = scanner.nextInt();
for (int j = a; j < b; j++) { // iteration in useful range
l[j] += k;
}
}
int total = l[0];
for (int i = 1; i < n; i++) {
if (l[i] > total) {
total = l[i];
}
}
System.out.println(total);
}
}


This is weird:

int total=0;
total=(int) l.get(0);
for(int i=0;i<n;i++){
int num=(int) l.get(i);
if(num>total){
total=num;
}
}
System.out.println(total);


That code finds the maximum element of the list, not the total. So why is the variable called total? You could replace that entire code block with System.out.println(Collections.max(l));.