Improve the Time Complexity Facebook
Dumb_dev
127
Interview

Given two unsorted arrays A1 and A2 containing negative and positive integers of different lengths,
find the kth maximum product of A1[i] * A2[j] ( a number from A1 * number from A2)
Example: A1=[7,-20,3,0,10,-70] A2=[0,1,-12, 100, -30] k=3
1st max = -70 * -30 = 2100
2nd max = 100 * 10 = 1000
k = 3rd max = -70 * -12 = 840 ( answer)

public class KthMaximumProduct {
    public static void main(String[] args)
    {


            int[] a1 = {7,-20,3,0,10,-70 };
            int[] a2 = { 0,1,-12, 100, -30 };

            int kmaxProd = 3;
            int lenA1 = a1.length;
            int lenA2 = a2.length;
            int[] A3 = new int[lenA1*lenA2];
            int cnt = 0;
             for(int m=0; m<lenA1; m++){
                for(int n=0; n<lenA2; n++){
                    A3[cnt] = a1[m]*a2[n];
                    cnt++;
                }

            }

        Arrays.sort(A3);
            int kIndex = A3.length - kmaxProd;
             System.out.println("\nkth maximum product: "+A3[kIndex]);

    }
}

How can i improve the timecomplexity . Can someone please share the code.

Comments (2)