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

• Anirudh Thatipelli: Thank you so much @Kevin Raoofi. I realised that using BufferedReader is a huge overhead and time consuming too. I will keep in mind to keep the stylistic aspects and follow a proper coding convention.
• cbojar: If you start with largest being -1, you don't need a special case for the last element before you start the loop.
• Kevin Raoofi: You're right. That does make things a bit simpler. I've made the change.

Answer 2

enter image description here

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.

• Vogel612: Welcome to Code Reivew! We have MathJax support on this site, so you could make some tables with that. Posting only a screenshot does not constitute a review. Could you explain what your screenshot is showing and how this improves the code posted by the asker? Thanks
• rolfl: It is not trivial to sort the original array and also keep the index number of the unsorted values. Your statement "and the required result can be obtained in one cycle" is misleading because it applies to only the very last part of the solution.