Find the pairs (2 Elements) from an array whose product must be greater then given Integer

Question

I got this question in an Interview. Suppose you have an unsorted integer array with possible values positive, negative and zero. You also have a variable k which holds an Integer. Now find the pair or pairs, non-repetitive, if exists, whose product is greater then k. k can be anything, +ve, -ve, or zero

Constraints: You cannot manipulate the array, means any sorting or making a copy of original and then sorting or changing the values is restricted.

If possible it should be lower then O(n^2) Time Complexity and minimum Space (not mentioned clearly for space, but they said use lowest possible)

For Example: given Array [0,-1, 5, 45, 4, 1, -3] and k = 20 My Solution is given during interview:

My Solution: First one was Brute-Force using O(N^2) and trying to get the product for that pair and checking. Now I improvised that to the following logic

Suppose k = 40, and I got array[i] = 2. Now int divide = k/array[i]. divide+ = 1. If I encounter any number say array[j] > divide, and array[j] < k, then the product of int product = array[i] * array[j] will be product > k.

Logic: If I have a number 1000 and I got the array[i] = 3 for some value of i. If I get n = 1000 / array[i] and increment n = n+1, and if n is present in array then the product of n * array[i] > 1000

EDIT: +ve means Positive, -ve Means Negative, And find all the pairs instead of stopping at first pair. EDIT 2 We can store minimum number of entries in any new Data Structure, but it should be Minimum, not a full copy of original or too many elements in that Data Struction

Answer 1

Let's assume we have:

int[] values;
int k;
// Found pairs will be fed to this consumer
BiConsumer<Integer, Integer> results;

The naive brute-force implementation is O(n^2). The question is, if it is possible to make it better. I personally do not think so. In the worst case all elements of the array could form pairs. For instance if array contains distinct positive integers and k=0. Even if you'd sort an array, you'd still need to actually produce pairs. This means that brute-force is actually good enough.

Now for the space complexity. The problem is that you need to produce non-repetetive pairs. So you need some tracking of which pairs you have already seen and which not. Naively that's O(n^2) but I think this could be reduced to O(n).

Here's a sketch of code:

Set<Integer> seenNumbers = new HashSet<>();
for (int i = 0; i < values.length - 1; i++) {
    int left = values[i];

    if (seenNumbers.contains(right)) {
        continue;
    }

    for (int j = i + 1; j < values.length; j++) {
        int right = values[j];

        if (seenNumbers.contains(right)) {
            continue;
        }

        if (((long)left*(long)right) > k) {
            results.accept(left, right);
            if (left != right) {
                results.accept(right, left);
            }
        }
    }
    seenNumbers.add(left);
}

This code uses O(n) of additional space for seenNumbers. I think it is enough to only track already encountered numbers. If we encounter certain number again, it means it was already processed as values[i], which means that all possible pairs with this number were already generated.

I've desided again the "division" solution you've suggested. Because it's quite tricky. You can't just k/values[i] + 1 and use it as minimum for right. You need to account for values[i]==0 as well as for negative values[i]. Not that it's impossible but it is very cumbersome and extremely easy to make a mistake. I'd probably mention this on the interview but rather not do it. Simple multiplication is much easier.

But even with simple multiplication you have to consider integer overflow. Therefor (long)left*(long)right. This is often a catch on interviews, Google loves it. :)