Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Given an array of number find the next greater no in the right of each element.

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);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment