Greater on the right side in Java

Question

Given an array of integers, replace every element with the next greatest element (greatest element on the right side) in the array. Since there is no element next to the last element, replace it with -1.

Input:

The first line of input contains an integer T denoting the number of test cases. The first line of each test case is N,N is the size of array. The second line of each test case contains N input A[i].

Output:

Print the modified array.

Constraints:

1 ≤ T ≤ 50 1 ≤ N ≤ 100 1 ≤ A[i] ≤ 1000

Example:

Input:

2 
6 
16 17 4 3 5 2
4
2 3 1 9

Output:

17 5 5 5 2 -1
9 9 9 -1

My approach:

/*package whatever //do not write package name here */

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.Collections;

class GFG {

    private static int [] calcNewArr(int [] arr)
        {
            int [] ans = new int[arr.length];
            ans[0] = getNextBiggest(arr,1);
            for (int i = 1; i < arr.length - 1; i++)
                {
                    ans[i] = getNextBiggest(arr,i+1);
                }
            ans[ans.length - 1] = -1;
            return ans;
        }

    private static int getNextBiggest (int [] arr, int start)
        {
            int max = Integer.MIN_VALUE;
            for (int i = start; i < arr.length; i++ )
                {
                    if ( max < arr[i])
                        {
                            max = arr[i];
                        }
                }
            return max;    
        }

    public static void main (String[] args) throws IOException {
       BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
       String line = br.readLine();

       int numTests = Integer.parseInt(line);
       String line2;
       String line3;
       int size;
       int [] arr;
       int [] result;

       for (int i = 0; i < numTests; i++)
        {
            line2 = br.readLine();
            size = Integer.parseInt(line2);
            line3 = br.readLine();
            String []inps = line3.split(" ");
            arr = new int[size];
            for (int j = 0; j < size; j++)
                {
                 arr[j] = Integer.parseInt(inps[j]);   
                }
            result = calcNewArr(arr);      
            for (int k = 0; k < size; k++)
                {
                    System.out.print(result[k] + " ");
                }
           System.out.println();     
        }

    }
}

I have the following questions with regards to the above code:

1. How can I further improve my approach?

   2.Is there a better way to solve this question?

2. Are there any grave code violations that I have committed?

3. Can space and time complexity be further improved?

Reference

Answer 1

You're doing a lot of work to parse the input. It seems like it'd be easier if you just used the Scanner class:

final Scanner sc = new Scanner(System.in);
final int numTests = sc.nextInt();

for (int i = 0; i < numTests; i++) {
    final int size = sc.nextInt();
    final int[] arr = new int[size];
    final int[] result;

    for (int j = 0; j < size; j++) {
        arr[j] = sc.nextInt();
    }
    result = calcNewArr(arr);
}

Your implementation runs at \$O(n^2)\$, however, this should be possible in \$O(n)\$ time if you just looked through the array right to left. If the question was asking for left to right on a reverse of the array, the problem would be pretty obvious since it's basically just iterate through and apply some simple rules:

1. The first element is -1
2. Copy the highest number seen so far into the position
3. If the value replaced is greater, set it as the largest number seen so far

So, I think something like this fulfills your calcNewArray:

int largest = -1;

for (int i = ans.length - 1; i >= 0; i--) {
    final int value = ans[i];
    ans[i] = largest;
    largest = Math.max(largest, value);
}

Obviously, comments can improve the code and there's some stylistic things that'll make most Java devs raise their eyebrows, but it's not a big deal. One thing, in particular, however, is to consistently use the following format for array types:

int[] arr = new int[size];

As opposed to int [] arr or int []arr

Answer 2

You can sort the original array first, and then sort the index number of the original array. In this way, we only need to compare the index number of the sorted array with the original data index number, and the required result can be obtained in one cycle.