Finding the maximum of an array to solve a rope-burning puzzle

Question

I am trying to get the maximum value out of this array.

There is a long rope of length totalLength at its each unit length some ropes are tied pointing in upper and lower directions with their length given. I am saving them in upper and lower arrays. Question is if we light up the front end how much time it will take to burn the whole rope. The fire spreads at 1m/s.

These two arrays upper and lower they have some value and the I am adding the max of them in each iteration and at the end I am finding the max value.

My idea is the total time taken will be equal to burning the longest part of the rope. I am finding the longest part and displaying it. It seems like this code is not good enough and is not clearing the time limits.

import java.util.*;

class TestClass {
    public static void main(String args[] ) throws Exception {

        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();//total test cases;
        int totalLength = 0;
        int maxSum = 0, maxUL = 0;
        int[] upper;
        int[] lower;
        int[] result;
        while(N-- > 0) {

              maxSum = 0;

              totalLength = scan.nextInt();// total length of a base graph
              upper = new int[totalLength - 1];
              lower = new int[totalLength - 1];
              result = new int[totalLength - 1];
              for(int i = 0; i < totalLength - 1; i++){
                upper[i] = scan.nextInt();
              }


             for(int i = 0; i < totalLength - 1; i++){
                lower[i] = scan.nextInt();
              }


              for(int i = 0; i <= totalLength - 2; i++){
                   maxUL = (upper[i] > lower[i]) ? upper[i]: lower[i];
                   maxSum = i+1 + maxUL;
                   result[i] = maxSum;
              }

              int maxVal = 0;
              for(int i = 0; i < result.length; i++){
                if(maxVal < result[i]){
                    maxVal = result[i];
                } 
              }
              System.out.println(maxVal);
        }
    }
}

Sample Input

1 // for the test cases
5 // the totallength of the main rope
1 0 2 2
1 1 1 0

Output

6

Answer 1

Space complexity

In terms of space, you can solve this in \$O(1)\$ space. In other words, you don't need upper, lower, and result arrays. You can calculate the rolling max while parsing the values of upper and lower without storing them.

Time complexity

You are performing \$N\$ operations several times, where \$N\$ is the total length - 1:

• scan the elements of upper
• scan the elements of lower
• find the max of upper - lower pairs
• find the max of the max values

That looks like \$O(4N)\$. If you rewrite as I suggested, without extra storage and calculating the rolling max as you go, this can be reduced to \$O(2N)\$, since only the first two traversals remain, which is inevitable to read the input.

That being said, since \$O(4N)\$ and \$O(2N)\$ are of the same magnitude (linear), I'd be surprised if this made a difference for the time limit exceeded result. Usually TLE happens when there is a magnitude of difference between the expected solution and the actual (for example quadratic instead of linear).

Extra tips

Use an enhanced for loop when you don't need the value of the index. For example instead of:

          for(int i = 0; i < result.length; i++){
            if(maxVal < result[i]){
                maxVal = result[i];
            } 
          }

Write as:

          for(int val : result) {
            if(maxVal < val){
                maxVal = val;
            } 
          }

---

These loop conditions are identical, but written differently:

         for(int i = 0; i < totalLength - 1; i++){
         // ...
         for(int i = 0; i <= totalLength - 2; i++){
         // ...

It's easier to read if you adopt a more consistent writing style.

---

Instead of doing all the work in the main method, it would be better to decompose this to multiple methods. In the decomposed solution you should have a method that takes some input (possibly even a Scanner), and return some output instead of printing it directly. When written that way, unit testing becomes possible. And then of course, add some unit tests.