1
\$\begingroup\$

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)..

\$\endgroup\$
0

2 Answers 2

1
\$\begingroup\$

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);
  }
}
\$\endgroup\$
1
\$\begingroup\$

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));.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.