Fast Solution: Maximum Pairwise Product

Fast solution for the Maximum Pairwise Product Problem.

Fast algorithm

In search of a faster algorithm, we play with small examples like [5,6,2,7,4][5,6,2,7,4]. Eureka—it suffices to multiply the two largest elements of the array: 77 and 66! Since we need to find the largest and the second-largest elements, we need only two scans of the sequence. During the first scan, we find the largest element. During the second scan, we find the largest element among the remaining ones by skipping the element found at the previous scan.

 MaxPairwiseProductFast(A[1...n])MaxPairwiseProductFast(A[1 . . . n]):
  index11index_1 \leftarrow 1
  for ii from 22 to nn:
       if A[i]>A[index1]A[i] > A[index_1]:
             index1iindex_1 \leftarrow i
  index21index_2 \leftarrow 1
  for ii from 22 to nn:
       if A[i]A[index1]A[i] \neq A[index_1] and A[i]>A[index2]A[i] > A[index_2]:
             index2iindex_2 \leftarrow i
  return A[index1]A[index2]A[index_1] \cdot A[index_2]

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.