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):

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

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

<?php
    function compareFn($a, $b) {
        if ($a != $b && $a != -$b) {
            return abs($a) < abs($b) ? -1 : 1;
        } else {
            return $a < $b ? -1 : 1;
        }
    }

    function findNumbersWithOpposites($A) {
        usort($A, 'compareFn');

        for ($i = 1; $i < count($A); $i++) {
            if ($A[$i] > 0 && $A[$i - 1] == -$A[$i]) {
                echo $A[$i] . " ";
            }
        }
        echo "\n";
    }

    // To call the function
    $A = [-7, 4, -3, 2, 2, -8, -2, 3, 3, 7, -2, 3, -2];
    findNumbersWithOpposites($A);
?>

O(N) Solution