Thought Process

A very fun problem, requires precise implementation.

Obviously we can just find all the products, sort and the take the middle element, but this will take O(n^2 + nlog(n)) time to append all the elements and the sort it, where n = 1,000,003. This will take far too long.

This problem reminded me of a much simpler problem: See if a number is a sum of 2 elements in a list. The common solution is to loop through the list and then see if (required sum - current element) is inside the list.

I did something similar, I detail my algorithm below

1. First lets sort the set S = {S0, ... Sn-1}

2. Using a binary search let low = S0*S1, high = Sn-2*Sn-1, and m be the middle value. Let this m be our initial guess for the median

   1. There are going to be nC2 = n(n - 1)/2 pairwise products and therefore if there are n(n-1)/4 products which are less than m, then m is the median of this set by definition.

   2. Therefore, we need loop through the set S only once for each m, which is the crucial part to lower the time complexity (Same as the easy example problem), let's say we are on element Si, then we find the maximal element, j, such that Si*Sj ≤ m, we can do this with a binary search again in S by search for the closest Sj to m/Si

      1. Once we have found j, it means that there will be j - i products which do not exceed m because we must have that i < j by the problem definition

   3. Once we have found the total products less than m, if the number is greater than our goal (n(n-1)/4), then we know that this guess is too high, we let high = mid, otherwise, if we have too little then let low = mid

3. After the binary search we will have found our median

It takes O(nlog(n)) time to sort the set S, Then the remaining part takes nlog(n)log(Sn-2*Sn-1), because we perform a binary search for each element in n and then log(Sn-2*Sn-1) is due to the guesses of m.

Therefore our new time complexity is O(nlog(n) +nlog(n)log(Sn-2*Sn-1)) = O(nlog(n)log(Sn-2*Sn-1)) which is considerably faster than before!