FilesExpand file tree

 master

/

LargerElementOnRight.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

52 lines (47 loc) · 1.58 KB

 master

/

LargerElementOnRight.java

Copy path

Top

File metadata and controls

• Code
• Blame

52 lines (47 loc) · 1.58 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

package com.interview.array;

import java.util.Deque;

import java.util.LinkedList;

/**

* http://www.geeksforgeeks.org/next-greater-element/

* Find next larger element on right side of a number in array for

* all positions in array

* This is different than finding largest element on right side which can

* be done by keeping max while iterating from right

* It is also different from find next higher number on right side which can

* be found by keeping AVL tree and finding ceiling.

*/

public class LargerElementOnRight {

public int[] larger(int input[]){

Deque<Integer> stack = new LinkedList<Integer>();

int result[] = new int[input.length];

for(int i=0; i < result.length; i++){

result[i] = -1;

}

stack.offerFirst(0);

for(int i=1; i < input.length; i++){

while(stack.size() > 0){

int t = stack.peekFirst();

if(input[t] < input[i]){

result[t] = i;

stack.pollFirst();

}else{

break;

}

}

stack.offerFirst(i);

}

return result;

}

public static void main(String args[]){

LargerElementOnRight leo = new LargerElementOnRight();

int input[] = {4,2,-8,6,0,-3,-1,1,9};

int result[] = leo.larger(input);

for(int i=0; i < result.length; i++){

if(result[i] != -1){

System.out.print(input[result[i]] + " ");

}else{

System.out.print("NIL ");

}

}

}

}