Find K-Th Element From Product Array.

• Check for the base case i.e. if k > N * (N - 1) / 2, simply return -1.
• Initialize a vector named ‘product’.
• Now we will push all possible products of pairs into the array.
• while(i < N)
  • while(j > i and j < N)
    • product.push(arr[i] * arr[j])
• Sort the ‘product’ and return the Kth number in the array ‘product’.

• Check for the base case i.e. if K > N * (N-1) / 2, simply return -1.
• Initialize a vector named ‘product’.
• Now we will push all possible products of pairs into the array.
• while(i < N)
  • while(j > i and j < N)
    • ‘product’.push(array[i] * array[j])
• Instead of sorting used in approach 1, we can use some data structures to reduce the time complexity. Notice the fact that if there are only k elements in the array, then the kth smallest element will be nothing but the largest element of that array. This observation clearly hints at using heaps as they help find either the minimum or maximum element efficiently.
• We will be using a max-heap as we are interested in the largest element among the K smallest elements of the array ‘product’. In most programming languages, heaps are implemented using priority queues.
• Maintain a priority queue giving priority to the max element( Max-heap), and insert the first K elements of the array ‘product’ into the priority queue.
• Now traverse the remaining (N * (N-1)) / 2 - K elements one by one and check if the element at the top of the priority queue is larger than the element being traversed then pop the element present at the top of the queue and insert the element being traversed in the priority queue. And do the same for all the (N * (N-1)) / 2  - K elements. We want to make sure that at any instance our queue will only have K elements.
• After performing the above operation, return the element at the top of the priority queue, which will be our answer. Because after performing the above operations the priority queue will be containing the K smallest elements of the array. And the max of these k elements will be the Kth smallest element which will be present at the top of the queue because we are maintaining a max priority queue (max-heap).
• Let's examine the working of the above algorithm with the help of an example:

Consider the array product { -1, -2, -3, 2, 3, 6 } and let k = 2. 

Let's take an empty priority queue(max heap)

• After performing the first step of the algorithm the queue will be:

( (-1) -> (-2) ) (in the same order i.e. -1 will be at the top of the queue and -2 at the bottom).

• Now we start traversing the rest of the (N * (N-1)) / 2 - K elements i.e step2 of the algorithm.
• We start from -3 since it is less than -2, so we will pop the element from the top(-1) and push -3 into the queue. Now, the queue will be like  ( (-2) -> (-3) ).
• Then we come to 2 since it is greater than -2 so we will continue.
• Then we come to 3 since it is greater than -2 so we will continue.
• Then we come to 6 since it is greater than -2 so we will continue.
• After completing this step we can observe that our queue contains the 2 smallest elements of the array product with the 2nd smallest element at the top of the queue.
• Now we return the element at the top of the queue(-2) which is our answer.

• Initialize two vectors named pos and neg.
• Traverse the array and push the element of the array in pos if the element is greater than or equal to 0. Else push in neg.
• Sort both vectors i.e. pos and neg.
• Initialize two variables named l = -1 * 10 ^ 9, and r = 10 ^ 9 .
• We can apply Binary Search int range (l, r) to search the Kth number of sorted product array.
• Initialize a variable named ‘ans’ which will be the Kth number of sorted product array after binary search. We can binary search its value as follow -:
• While( l <= r )
  • Mid  = ( l + r ) / 2
  • Check whether the number of pairs having product less than or equal to ‘Mid’ is less than ‘K’ or not.  This can be done easily by first counting the number of positive-positive pairs (i.e those having both elements positive) having product less than ‘Mid’, then counting negative-negative pairs and then counting positive-negative pairs having product less than ‘Mid’  Since both pos and neg array is sorted, we can easily count these pairs in linear time using the two-pointers approach.  I.e we can count all positive-positive pair having product less than ‘Mid’ by fixing pointer ‘p’, ‘q’ at start and end of it, and then for each ‘p’, move ‘q’ backward until pos[p] *pos[q] become less than or equal to Mid. then increment count of such pairs by number elements between p and ‘q’. And then increment ‘p’ by ‘1’, similarly, we can count negative-negative and negative-positive pairs having product less than or equal to ‘Mid’
  • If previous return True:
    • Update ans to Mid.
    • Update r to Mid-1.
  • Else
    • Update l to Mid + 1.
• Return ans.