Your browser (Unknown 0) is no longer supported. Some parts of the website may not work correctly. Please update your browser.

#### ArrayClosestAscenders

For each element of an array of integers, find the closest larger element.

Consider an array A of N integers. Indices of this array are integers from 0 to N−1. Take an index K. Index J is called an ascender of K if A[J] > A[K]. Note that if A[K] is a maximal value in the array A, then K has no ascenders.

Ascender J of K is called the closest ascender of K if abs(K−J) is the smallest possible value (that is, if the distance between J and K is minimal). Note that K can have at most two closest ascenders: one smaller and one larger than K.

For example, let us consider the following array A:

A = 4 A = 3 A = 1 A = 4 A = -1 A = 2 A = 1 A = 5 A = 7

If K = 3 then K has two ascenders: 7 and 8. Its closest ascender is 7 and distance between K and 7 equals abs(K−7) = 4.

Write a function:

class Solution { public int[] solution(int[] A); }

that, given an array A of N integers, returns an array R of N integers, such that (for K = 0,..., N−1):

• if K has the closest ascender J, then R[K] = abs(K−J); that is, R[K] is equal to the distance between J and K,
• if K has no ascenders then R[K] = 0.

For example, given the following array A:

A = 4 A = 3 A = 1 A = 4 A = -1 A = 2 A = 1 A = 5 A = 7

the function should return the following array R:

R = 7 R = 1 R = 1 R = 4 R = 1 R = 2 R = 1 R = 1 R = 0

Result array should be returned as an array of integers.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [0..50,000];
• each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].