Regarding the ascenders problem from codility.com.

ascenders.c

#include <stdio.h>
#include <stdlib.h>

struct Results {
    int * R;
    int N;
};

struct Results solution(int A[], int N) {
    struct Results result;
    result.R = malloc(N * sizeof(int));
    result.N = N;

    // index of previous unfinished element -1 if no one exists
    int *prev = malloc(N * sizeof(int));
    prev[0] = -1;
    int last = 0; // index of last unfinished element yet
    // the sequence last, prev[last], prev[prev[last]], ...
    // is decreasing, while A[last], A[prev[last]], ... is increasing
    // these are all currently unfinished elements

    int i; // iteration index of current element
    int j; // index for iterating previous unfinished elements
    int offset_right; // index offset to next asdender to the right
    int offset_left;  // index offset to next asdender to the left

    for (i = 1; i < N; i++) {
        // if left neighbor is greater than current, then the current element
        // can be quickly finished with offset 1 (can't get better later)
        if (A[i] < A[i-1]) {
            result.R[i] = 1;
            continue;
        }

        // iterate through list of unfinished elements smaller than A[i] and
        // finish them
        for (j = last; j != -1 && A[j] < A[i]; j = prev[j]) {
            offset_right = i - j;
            offset_left = result.R[j];
            if (offset_left == 0 || offset_left > offset_right)
                result.R[j] = offset_right;
        }

        if (j == -1) {
            // all previous elements are finished
            prev[i] = -1;
            result.R[i] = 0;
        } else if (A[j] == A[i]) {
            // element at position j is unfinished and equal to current
            prev[i] = j;
            if (result.R[j] == 0)
                result.R[i] = 0;
            else
                result.R[i] = result.R[j] + i - j;
        } else {
            // element at position j is unfinished and greater than current
            prev[i] = j;
            result.R[i] = i - j;
        }
        last = i; // current element is not finished yet
    }

    return result;
}

int main() {
    int arr[] = { 4,  3,  1,  4, -1,  2,  1,  5,  7 };
    struct Results result = solution(arr, 9);
    for (int i = 0; i < result.N; i++) {
        printf(" %d", result.R[i]);
    }
    printf("\n");
}

problem.txt

Consider a zero-indexed 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[0] = 4     A[1]  = 3    A[2]  = 1
  A[3] = 4     A[4]  = -1   A[5]  = 2
  A[6] = 1     A[7]  = 5    A[8]  = 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.

struct Results {
  int * R;
  int N;
};

Write a function:
that, given a zero-indexed array A of N integers, returns a zero-indexed 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[0] = 4     A[1]  = 3    A[2]  = 1
  A[3] = 4     A[4]  = -1   A[5]  = 2
  A[6] = 1     A[7]  = 5    A[8]  = 7

the function should return the following array R:
  R[0] = 7     R[1]  = 1    R[2]  = 1
  R[3] = 4     R[4]  = 1    R[5]  = 2
  R[6] = 1     R[7]  = 1    R[8]  = 0

Array R should be returned as:
- a structure Results (in C), or
- a vector of integers (in C++), or
- a record Results (in Pascal), or
- an array of integers (in any other programming language).

Assume that:
- 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].

Complexity:
- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.


C:
struct Results solution(int A[], int N) {
    struct Results result;
    // write your code here...
    result.R = ...
    result.N = ...
    return result;
}

C++:
// you can also use includes, for example:
// #include <algorithm>
vector<int> solution(const vector<int> &A) {
    // write your code here...
}

Java:
// you can also use imports, for example:
// import java.math.*;
class Solution {
    public int[] solution(int[] A) {
        // write your code here...
    }
}

Python:
def solution(A):
    # write your code here...
    pass

Example invocation:

gcc -O3 -std=c99 ascenders.c -o ascenders && time ./ascenders
 7 1 1 4 1 2 1 1 0
./ascenders  0.00s user 0.00s system 59% cpu 0.003 total