Return to Answer

solution(A)
    Filter non-positive values from A
    Filter values larger than min(N-1, 100000) from A
    For each int in filtered
        Let a zero-based index be the absolute value of the int - 1
    For each index in filtered
        if filtered[index] is positive, return the index + 1 (to one-based)
    otherwise return the length of filtered + 1 (to one-based)

solution(A)
    Filter non-positive values from A
    Filter values larger than min(N-1, 999999) from A
    For each int in A that wasn't filtered out
        Let a zero-based index be the absolute value of the int - 1
    For each index upto min(N-1, 999999)
        if A[index] is positive, return the index + 1 (to one-based)
    otherwise return min(N, 100000)

solution(A)
    Filter non-positive values from A
    For each int in filtered
        Let a zero-based index be the absolute value of the int - 1
        If the filtered range can be accessed by that index
            Make the value in filtered[index] negative
    For each index in filtered
        if filtered[index] is positive, return the index + 1 (to one-based)
    otherwise return the length of filtered + 1 (to one-based)

abs(A[0]) = 1, to_0idx = 0, A[0] = 1, make_negative(A[0]), A = [-1,  2,  3,  5,  6]
abs(A[1]) = 2, to_0idx = 1, A[1] = 2, make_negative(A[1]), A = [-1, -2,  3,  5,  6]
abs(A[2]) = 3, to_0idx = 2, A[2] = 3, make_negative(A[2]), A = [-1, -2, -3,  5,  6]
abs(A[3]) = 5, to_0idx = 4, A[4] = 6, make_negative(A[4]), A = [-1, -2, -3,  5, -6]
abs(A[4]) = 6, to_0idx = 5, A[5] is inaccessible,          A = [-1, -2, -3,  5, -6]

solution(A)
    Filter non-positive values from A
    Filter values larger than min(N-1, 100000) from A
    For each int in filtered
        Let a zero-based index be the absolute value of the int - 1
    For each index in filtered
        if filtered[index] is positive, return the index + 1 (to one-based)
    otherwise return the length of filtered + 1 (to one-based)

abs(A[0]) = 1, to_0idx = 0, A[0] = 1, make_negative(A[0]), A = [-1,  2,  3,  5,  6]
abs(A[1]) = 2, to_0idx = 1, A[1] = 2, make_negative(A[1]), A = [-1, -2,  3,  5,  6]
abs(A[2]) = 3, to_0idx = 2, A[2] = 3, make_negative(A[2]), A = [-1, -2, -3,  5,  6]
abs(A[3]) = 5, to_0idx = 4, A[4] = 6, make_negative(A[4]), A = [-1, -2, -3,  5, -6]

While using a boolean array does meet your space complexity requirement, a constant space solution does exist. Remember that every element in your filtered array is positive, so we can repurpose the sign bit of each value as a signal that we've witnessed a value of the sequence. We can use the indices of the filtered array the same way we did the boolean array above. Rather than search for the first element marked false (unwitnessed), we search for the first value that is still positive.

Note - Since you know the upper-bound, you can narrow your range further by making a second filter pass which removes any elements larger than the array length. Would help with data locality if you have smallish arrays loaded with largish values.

While using a boolean array does meet your space complexity requirement, a constant space solution does exist. Remember that every element in your filtered array is positive, so we can repurpose the sign bit of each value as a signal that we've witnessed a value of the sequence. We can use the indices of the filtered array the same way we did the boolean array above. Rather than search for the first element marked false (unwitnessed), we search for the first value that is still positive.