leaky relu

Exercise

Difficulty : Medium

Statement

The LeakyReLU function can be split into two parts :

The identity function (left hand side), e.g. $y = x$
The leaky part (left hand side), that is, the identity function multiplied by a small factor such as 0.2 (this factor is always between 0 and 1 excluded), e.g. $y = 0.2 \times x$

Credit: paperswithcode.com

We provide the array $A$ of length $N$ such that $A_i = \text{LeakyReLU}(i + \alpha) + \beta$ where $\alpha$ is an integer and $\beta$ is a floating point value.

That is, the array $A$ contains values of the LeakyReLU function added to a constant $\beta$.

Find the index of the value belonging to the two parts of this function (at the point (0, 0) if $\beta = 0$ as in the image).

Example

Given this array of length 7 :

$A_i$	1	1.2	1.4	1.6	2.6	3.6	4.6
$i$	0	1	2	3	4	5	6

Values from 0 to 3 included are the leaky part
Values from 3 to 4 included are the identity part

Thus, the value 1.6 at index 3 belongs to both parts.

Answer : 3

Constraints

$0 \le N \le 10^5$

Complexity

Time : $O(\log N)$

Follow-up

Can you do this in O(1) ? This won’t use any binary search of course…

Solution

Let’s suppose that the provided array contains both linear and leaky parts, that is, the array is neither full linear nor full leaky.

The initial search interval is $[0, N - 1]$ (indices start from 0).

At each iteration, mid is the pivot point. To find whether the target point is at the left or right hand side to this point, we can deduce a criterion :

leaky_part(i) is a function returning a boolean, it returns true when the part containing the index i is the leaky part (the left part of the function) and false otherwise.

This function can be easily implemented : leaky_part(i) = true $\Leftrightarrow A_{i + 1} - A_i < 1$.

Thus, when mid is before the target point (at its left), leaky_part(mid) is true and the new interval is $[mid + 1, r]$.

The last $l$ value is the target point.

Code

// Returns whether it is the leaky part
bool leaky_part(const vector<float> &values, int i) {
    // Float precision...
    return abs(values[i] - values[i + 1]) < .99f;
}

int leaky_relu(const vector<float> &values) {
    int l = 0;
    int r = values.size() - 1;
    while (l < r) {
        int mid = l + (r - l) / 2;

        // Find the first time this function returns true w.r.t. mid
        if (leaky_part(values, mid)) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }

    // The array is only leaky
    if (l == values.size() - 1 && leaky_part(values, values.size() - 2)) {
        return values.size();
    }

    return l;
}

Full code