Leaders in arrays

Question

class LeadersInArray 
{

    void printLeaders(int arr[], int size)
    {
        int max_from_right =  arr[size-1];

        /* Rightmost element is always leader */
        System.out.print(max_from_right + " ");

        for (int i = size-2; i >= 0; i--)
        {
            if (max_from_right < arr[i])
            {           
            max_from_right = arr[i];
            System.out.print(max_from_right + " ");
            }
        }    
    }

    /* Driver program to test above functions */
    public static void main(String[] args) 
    {
        LeadersInArray lead = new LeadersInArray();
        int arr[] = new int[]{16, 17, 4, 3, 5, 2};
        int n = arr.length;
        lead.printLeaders(arr, n);
    }
}

the output of this program is 2,5,17 . MY question is can i print result in inplace manner i.e 17, 5 and then 2 (as they appear in original array) except for storing it in separate array and then traversing in reverse manner as that will add to space complexity of O(n).

see https://stackoverflow.com/questions/2137755/how-do-i-reverse-an-int-array-in-java — Scary Wombat, Jun 02 '17 at 08:14
Possible duplicate of [How do I reverse an int array in Java?](https://stackoverflow.com/questions/2137755/how-do-i-reverse-an-int-array-in-java) — Noel Widmer, Jun 02 '17 at 08:39

score 1 · Answer 1 · answered Jan 03 '19 at 03:59

Other possible solution is to use stack. Time complexity will be O(n)

import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
 {
    public static void main (String[] args)
     {
        Scanner scn = new Scanner(System.in);
        int tcs = scn.nextInt();
        int input = 0;
        int temp = 0;
        List<Stack<Integer>> stks = new ArrayList<Stack<Integer>>();
        for(int i=0;i<tcs;i++){
            int arrSize = scn.nextInt();
            Stack<Integer> stk = new Stack<Integer>();
            for(int j=0;j<arrSize;j++){
                input = scn.nextInt();
                if(stk.empty()){
                    stk.push(input);
                } else {
                    temp = stk.peek();
                    while(true) {
                        if(input>temp) {
                            stk.pop();
                            if(!stk.empty())
                                temp = stk.peek();
                            else
                                break;
                        } else {
                            break;
                        }
                    }
                    stk.push(input);
                }
            }
            stks.add(stk);
        }
        for(Stack<Integer> stk: stks) {
             System.out.println("");
             stk.forEach(x -> System.out.print(x+ " "));
        }
}
}

score 0 · Answer 2 · answered Jun 02 '17 at 08:38

You can use two loop because you need to check the element after the seeing element.But the complexity is O(N*N).Not consider to be a good solution

void printLeaders(int arr[], int size) {
        for (int i = 0; i < size; i++) {
            int j;
            for (j = i + 1; j < size; j++) {
                if (arr[i] <= arr[j])
                    break;
            }
            if (j == size) 
                System.out.print(arr[i] + " ");
        }
    }

score 0 · Answer 3 · answered Jun 02 '17 at 08:38

It is possible to prove that you cannot.

The only way to output the correct numbers in the order they appear in the array without using more space or increasing the algorithm complexity is by walking forward through the array.

Consider something like:

    int arr[] = new int[]{16, 17, 4, 3, /* ... many more numbers */, 18, 5, 2};

Imagine you are iterating through the array and have reached the 17. The only way to know whether to print it or not is to know about the 18 further down the array. If you are only walking forward you will not know.

Leaders in arrays

3 Answers3