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.


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].


Print the modified array.


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



16 17 4 3 5 2
2 3 1 9


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] + " ");


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?



2 Answers 2


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

  • \$\begingroup\$ 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. \$\endgroup\$ Jun 19, 2018 at 5:51
  • 1
    \$\begingroup\$ If you start with largest being -1, you don't need a special case for the last element before you start the loop. \$\endgroup\$
    – cbojar
    Jun 20, 2018 at 3:40
  • \$\begingroup\$ You're right. That does make things a bit simpler. I've made the change. \$\endgroup\$ Jun 20, 2018 at 15:39

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.

  • 2
    \$\begingroup\$ 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 \$\endgroup\$
    – Vogel612
    Jun 19, 2018 at 8:27
  • \$\begingroup\$ 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. \$\endgroup\$
    – rolfl
    Jun 19, 2018 at 10:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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