 # help for TLE

i guess this is the problem code,

``````		while(h != n)
{
l=(h+1);
while(l != n)
{
if(goals[l] > goals[h] && (goals[l]-goals[h]) > diff)
{
diff=goals[l]-goals[h];
}
l++;
}
h++;
}
``````

i tried using both for and while loop, but as obvious, it doesn’t change anything. Please suggest me how to shorten this code snippet or get rid of TLE anyhow.

Hi,

You are doing a brute force. Your code takes at least `N(N-1)/2` steps. When `N` is as big as `100000` (`10``5`), this is at least `4999950000` operations to be done in 2 seconds.

Of course, using an `O(N``2``)` algorithm will time-out.

You need to have an algorithm, whose complexity is something like `O(N)`.

1 Like

@tijoforyou : though i’ve been programming from school days, but i’m relatively new to making programs with time limit hence need no ask even small things.

i’ve used nested for/while loops making it of O(N2) complexity. Would it be better if instead i introduce 2 new arrays and store the max and min goal scored with their index, and accordingly compare and print the answer ? will this thing be cool ?
[you’ve answered many of my doubts, so thanks :)]

Yup. Calculating the values of one of the arrays (say, the min-array) will need only a single loop. Similarly, that for the other array (say, the max-array) will also need only a single loop. Since there are no nested loops, it takes only `O(N)` steps. Now the solution is maximum among difference between the corresponding entries of the two arrays. This will also be `O(N)`. Hence, total complexity stays at `O(N)`.

PS: All the above words taken from the editorial, just to re-assure you You can even find the links to the problem setter’s and the problem tester’s solutions in the editorial. YOu may go through them, if you wish to have some reference! There need not be any “thanks” in here. Discuss is here, so than we can learn and help. I learned a lot. Now, I try and help others, as much as I can, with what limited knowledge I have! 