Three approaches will be addressed in this article: approach for O(N²) time, approach for O(N log₂ N) time, and approach for O(N) time. Only the approach for O(N.log₂N) time will be described in detail.

Also not that absolute value means the value without sign, which is just the positive value.

O(N²) Solution

With this solution, for each positive number, it is verified (compared) if any other number in the array is the opposite. The number of opposite pairs gives the answer. This solution has O(N²) time complexity. Any good computer programmer can code this solution, so it will not be addressed any further, in this article.

O(N.log₂N) Solution

Consider the example list:

    -7, 4, -3, 2, 2, -8, -2, 3, 3, 7, -2, 3, -2

By inspection, though inspecting is rather time consuming, the answer is [2, 2, 3, 7]. The subset (-2, -2, 2, 2) produces 2 pairs; the subset (-3 3) produces 1 pair; and the subset (-7 7) produces the last pair, making 4 pairs altogether. The set (-2, -2, 2, 2) has the pairs (-2, 2) and (-2, 2) which is same pair occurring twice.

Need for Special Custom Sorting

The special custom sorting is as follows:

If the numbers are not equal or opposite, they are sorted by their absolute value; but if they are (else), they are sorted by their sign. This leads to the following special custom sort (arrangement):

The 4 pairs required can be seen or inferred.

This is not ordinary sort ascending or ordinary sort descending. A compare function is needed for this special custom sorting. The sort function will use the compare function. The code for this compare function is given along with the principal code below.

Principal Code

There is an issue with this problem and its solution at toptal.com/algorithms/interview-questions. At toptal.com/algorithms/interview-questions, the answer is [2 3 7 ] instead of [2, 2, 3, 7] . This means that the problem actually requires unique positive numbers and not just positive numbers with opposites. The principal code below produces unique positive numbers.

Complete Program

The complete program is (read the comments as well):

    #include <stdio.h>
    #include <stdlib.h>     //for abs() and qsort() functions
    
    //compare function
    int compareFn(const void *a, const void *b) {
        int int_a = *((int *)a);
        int int_b = *((int *)b);
        if (int_a != int_b && int_a != -int_b)
        return abs(int_a) > abs(int_b);    //from stdlib.h library
    else
            return int_a > int_b;
    }
    
    //principal code
    void find_numbers_with_opposites(int A[], int N) {
        qsort(A, N, sizeof(int), compareFn);    //from stdlib.h library
        for (int i=1; i<N; i++) {
        if (A[i] > 0 && A[i - 1] == -A[i])
                printf("%i ", A[i]);
        }
    }

    int main(int argc, char **argv)
    {
        int A[] = {-7, 4, -3, 2, 2, -8, -2, 3, 3, 7, -2, 3, -2};
        int N = sizeof(A) / sizeof(A[0]);    //no. of elements in A
        find_numbers_with_opposites(A, N);
        printf("\n");

        return 0;
    }

This implementation has an optimal average case runtime complexity of O(N.log₂N), with the sorting algorithm being the bottleneck.

O(N) Solution

This solution needs a hash function. The C language does not have a hash function. The C++ language has a hash function. So only the pseudo code using a hash function is provided below, so that anyone who has studied C++ can implement it. The pseudo code is:

FUNCTION find_numbers_with_opposites(numbers)
    table = HashTable<number, number>
    answer = List
    FOR number IN numbers
        IF number == 0
            CONTINUE
        END IF
        key = abs(number)
        IF key not in table
            table[key] = number
        ELSE IF table[key] = -number
            answer.push(key)
            table[key] = 0
        END IF
    END FOR