-1
\$\begingroup\$

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\$ \$(1\le i\le 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 \$x\lt i\$ such that \$A[x]\gt A[i]\$, then take \$x=-1\$. Similarly, if there is no \$y\gt 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+" ");
    }
}
\$\endgroup\$
1
\$\begingroup\$
  • 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-1}\gt 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-1}\le 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-1}\le a_i\$), so we can skip all these elements and jump to \$a_{x_{i-1}}\$.

    If \$a_{x_{i-1}}\gt 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).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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