import java.util.Optional;
/**
* Given an array of numbers and an index i, return the index of the nearest larger number of the number at index i, where distance is measured in array indices. Assume your array is unsorted and there can be duplicates.
* E.g.
* Given int[] array = [4, 1, 3, 5, 6] and index 0, you should return 3.
* As index array[0] = 4, and the next highest value is at array[3] = 5.
* If two distances to larger numbers are equal, then return any one of them.
* If the array at i doesn't have a nearest larger integer, then return null.
*/
public class NearestLargestPosition {
public Optional<Integer> nearestLargerNumberDistance(int[] array, int index) {
if (array.length < 1) return Optional.ofNullable(null);
final int max = Math.max(Math.abs(array.length - index), index);
int distanceOfIndexFromStart = index - 0; // 0
int distanceOfIndexFromEnd = array.length - index; // 5
if ((distanceOfIndexFromEnd - distanceOfIndexFromStart >= 0)) {
for (int i = index; i <= array.length; i++) {
Optional<Integer> x = findDistance(array, index, i);
if (x != null) return x;
}
} else {
for (int i = index; i > 0; i--) {
if (array[i - 1] > array[index]) return Optional.ofNullable(Math.abs(i - 1 - index));
if (i + 1 < array.length - 1) {
if (array[i + 1] > array[index]) return Optional.ofNullable(Math.abs(i + 1 - index));
}
}
}
return Optional.ofNullable(null);
}
private Optional<Integer> findDistance(int[] array, int index, int i) {
if (i - 1 >= 0) {
if (array[i - 1] > array[index]) return Optional.ofNullable(Math.abs(i - 1 - index));
}
if (i + 1 < array.length - 1) {
if (array[i + 1] > array[index]) return Optional.ofNullable(Math.abs(i + 1 - index));
}
return null;
}
}
And here is the Test to verify
@Test
public void shouldReturnNearestDistanceOfLargest() {
final NearestLargestPosition nearestLargestPosition = new NearestLargestPosition();
int[] array = { 9, 2, 10, -3, 6, 7, 6, 7, 1, 9 };
Assert.assertEquals(7, (int) nearestLargestPosition.nearestLargerNumberDistance(array, 9).get());
Assert.assertEquals(2, (int) nearestLargestPosition.nearestLargerNumberDistance(array, 4).get());
Assert.assertEquals(1, (int) nearestLargestPosition.nearestLargerNumberDistance(array, 1).get());
}