trjhtr

The given code gives correct output but exceeds the time limit and I have no idea how to optimize it. I know it is of $O(n^2)$ complexity but I am not able to get anywhere near to optimizing it. Even a few hints would be appreciated.

The question is this:

The problem is given an array $A$ having $N$ integers, for each $i$ $(1le ile N)$, find $x+y$, where $x$ is the largest number less than $i$ such that $A[x]gt A[i]$ and $y$ is the smallest number greater than $i$ such that $A[y]gt A[i]$. If there is no $xlt i$ such that $A[x]gt A[i]$, then take $x=-1$. Similarly, if there is no $ygt i$ such that $A[y]gt A[i]$, then take $y=-1$.

import java.util.*;
import java.io.*;

class Alpha{
 public static void main(String args) throws IOException

 int n=0,i=0,x=-1,y=-1,sum=0,m1,m2;
 BufferedReader br = new BufferedReader(new 
 InputStreamReader(System.in));
 StringTokenizer st = new StringTokenizer(br.readLine());
 n=Integer.parseInt(st.nextToken());
 Stack<Integer> stk=new Stack<>();
 long arr = new long[n];
 String str=br.readLine().split(" ");
 for(i=0;i<n;i++)
 
 arr[i]=Long.parseLong(str[i]);
 
 for(i=n-1;i>=0;i--)
 
 x=-1;
 y=-1;
 for(int j=i-1;j>=0;j--)
 
 if(arr[j]>arr[i])
 
 x=j+1;
 break;
 
 
 stk.push(x);
 for(int j=i+1;j<n;j++)
 
 if(arr[j]>arr[i])
 
 y=j+1;
 break;
 
 
 stk.push(y);

 
 while(!stk.isEmpty())
 
 m1=stk.peek();
 stk.pop();
 m2=stk.peek();
 stk.pop();
 sum=m1+m2;
 System.out.print(sum+" ");
 

• 
  

  In the following explanations, I'm going to use 1-based indexes just like the description does, even though it's confusing seeing as Java arrays have zero-based indexes.

  
  
  

  Obviously, $x_1=-1$. Also, if $a_i-1gt a_i$, then $x_i=i-1$. So as long as every integer is less than the last one, we can just store the $x$ for every array element one by one.

  
  
  

  But what if we encounter an $a_i$ where $a_i-1le a_i$? Do we need to iterate over all the preceding elements to find the nearest greater integer? No, because we already know the position of the next greater integer before $a_i-1$, namely $x_i-1$. Every element between $a_i-1$ and $a_x_i-1$ will be less than or equal to $a_i-1$, and therefore also less than or equal to $a_i$ (since $a_i-1le a_i$), so we can skip all these elements and jump to $a_x_i-1$.

  
  
  

  If $a_x_i-1gt a_i$, we have found $x_i=x_i-1$. Otherwise, we repeat the process, i.e. jumping to the next greater integer before $a_x_i-1$ by querying $x_x_i-1$, and so on, until we arrive at an integer that is greater than $a_i$ (or until there are no more array elements).

  
  
  

  The same process can be repeated in the other direction of the array to find all $y$ values. So instead of calculating $x$ and $y$ for every array element independently, you can use the already calculated values to speed up the process, based on the relationships explained above.

  
  


• 
  

  Apart from that, your code is a bit chaotic. I would suggest separating user interface from program logic, for example writing one method that accepts an int (or long) as a parameter and returns an int of equal length containing the sum of $x$ and $y$ for every array element, and another method that reads user input from the command line (or from wherever), converts this input to an int or long, passes this array to the other method, and converts the int returned by the method to the required output format.

  
  
  

  Note that $x+y$ may overflow an int, but a Java array can only contain a maximum of Integer.MAX_VALUE ($=2^31-1$) elements (and that's only in theory, I think I've read that, in practice, even with memory implications aside, the maximum length of an array might be slightly lower), so the maximum sum that could ever occur is Integer.MAX_VALUE + Integer.MAX_VALUE - 2 for an element at the one-based index Integer.MAX_VALUE - 1, and Integer.MAX_VALUE + Integer.MAX_VALUE - 2 $=2^32-4$ still fits into 32 bits, so no information is lost if you store the value in an int, it's just that Java treats the highest-order bit of an int as a sign-bit because Java doesn't support unsigned 32-bit integers.

  
  
  

  Also, $2^32-4$ overflows to -4, and the smallest possible non-overflowing result of $x+y$ is $-2$, so it will always be possible to tell an overflow and a truly negative result apart. An int would therefore suffice to store the necessary results.

  
  



• The class Stack is antiquated – the documentation recommends to use Deque implementations instead.



• 
  

  Reduce the scope of variables to the smallest extent necessary to make the code less confusing. x and y are only needed in the second for loop (the outer for loop), and they also don't need to keep their state from one iteration to the next, so they should not only be initialized, but also declared there. Likewise, sum, m1 and m2 can be declared in the last while loop.

  
  
  

  Also, declaring one int variable i outside the for loops and using this variable in both loops gives the illusion that the value of i in the second for loop somehow depends on its final value after the first loop. This is not true, as you manually set it to n-1, so it would be less confusing if you either declared a separate i in every loop so that these is don't exist outside the loop for which they are relevant, or you don't explicitly set i to n-1 at the beginning of the second loop. I would prefer the first version because it keeps the loop variables in their loop, even if it takes a few microseconds longer because the new i has to be initialized to n-1.

  
  


• 
  

  Instead of storing an entire input String in memory, you could wrap a Scanner around an InputStream to parse it into a long:

  
  
  

  Scanner inputScanner = new Scanner(System.in);
  
  int n = inputScanner.nextInt();
  inputScanner.nextLine();
  
  long arr = new long[n];
  for (int i = 0; i < n; i++) 
   arr[i] = inputScanner.nextLong();
  
  

  
  
  

  This is not equivalent to your code, because it doesn't require the array elements to be on one line. I doubt that this matters, but theoretically, you could configure the scanner to exlude line terminators from its delimiter pattern after you read the value of n and skip the rest of the line by invoking Scanner.useDelimiter(String) and passing a custom regular expression that matches whitespace excluding line terminators (the default delimiter pattern of a Scanner is whitespace).