0
\$\begingroup\$

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
\$\endgroup\$
6
  • 2
    \$\begingroup\$ A short description would be helpful. What does the program compute, what is the input format and the output? \$\endgroup\$
    – Martin R
    Apr 26, 2015 at 14:06
  • \$\begingroup\$ There are pictures in that challenge I dont know how to display all of that here. I will try to describe the problem in words here. \$\endgroup\$
    – John Doe
    Apr 26, 2015 at 14:19
  • 1
    \$\begingroup\$ Please include a link to the original problem as well, if possible. \$\endgroup\$ Apr 26, 2015 at 14:21
  • \$\begingroup\$ Its not accessible the contest has ended, and I am not able to access it now. My code is correct atleast partailly and not totally off the mark, its passing the 6 test cases but not all of them. \$\endgroup\$
    – John Doe
    Apr 26, 2015 at 14:22
  • \$\begingroup\$ Please make the title more specific to the code's purpose (as I've attempted). Review requests are just for the post body. \$\endgroup\$
    – Jamal
    Apr 26, 2015 at 18:03

1 Answer 1

2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

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

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