Given an array of number find the next greater no in the right of each element.
Example-
Input 12 15 22 09 07 02 18 23 27
Output 15 22 27 18 18 18 23 27 -1
import java.util.Stack; | |
public class FindNextGreatestGivenArray { | |
// works in O(n*n) | |
public int[] findNextGreatestNumbers(int[] numbers) { | |
if (numbers == null) { | |
throw new IllegalArgumentException("Given array is null"); | |
} | |
int[] output = new int[numbers.length]; | |
for (int i = 0; i < output.length; i++) { | |
output[i] = -1; | |
} | |
for (int i = 0; i < output.length; i++) { | |
for (int j = i + 1; j < output.length; j++) { | |
if (numbers[j] > numbers[i]) { | |
output[i] = numbers[j]; | |
break; | |
} | |
} | |
} | |
return output; | |
} | |
// works in O(n) with using stack | |
public void printNextLarger(int numbers[]) { | |
if (numbers.length <= 0) | |
return; | |
Stack<Integer> stack = new Stack<>(); | |
stack.push(numbers[0]); | |
for (int i = 1; i < numbers.length; i++) { | |
int currentElement = numbers[i]; | |
while (!stack.isEmpty()) { | |
int leftElement = stack.pop(); | |
if (leftElement < currentElement) { | |
System.out.println(leftElement + " Next Largerst --> " + currentElement); | |
} else { | |
stack.push(leftElement); | |
break; | |
} | |
} | |
stack.push(currentElement); | |
} | |
while (!stack.isEmpty()) { | |
int leftOverElement = stack.pop(); | |
System.out.println(leftOverElement + " Next Largerst --> None"); | |
} | |
} | |
} |
import static org.junit.Assert.assertArrayEquals; | |
import org.junit.Before; | |
import org.junit.Test; | |
public class FindNextGreatestGivenArrayTest { | |
private FindNextGreatestGivenArray testClass; | |
@Before | |
public void setUp() { | |
testClass = new FindNextGreatestGivenArray(); | |
} | |
@Test | |
public void testGivenArray() { | |
int[] numbers = { 12, 15, 22, 9, 7, 2, 18, 23, 27 }; | |
int[] expected = { 15, 22, 23, 18, 18, 18, 23, 27, -1 }; | |
assertArrayEquals(expected, testClass.findNextGreatestNumbers(numbers)); | |
} | |
@Test | |
public void testName() throws Exception { | |
int[] numbers = { 40, 50, 11, 32, 55, 68, 75 }; | |
testClass.printNextLarger(numbers); | |
} | |
} |