Maximum Pairwise Product

Cloistered Monkey

2018-06-24 16:42

Since the test only uses python standard library I'll try and stick to that, but since the stress-test isn't part of the assignment I'll cheat and use numpy to generate the random input.

Problem Statement

Find the maximum product of two distinct numbers in a sequence of non-negative integers.

  • Input: A sequence of non-negative integers.
  • Output: The maximum value that can be obtained by multiplying two different elements from the sequence.

Given a sequence of non-negative numbers \(a_1,\ldots,a_n\), compute

\[ \max_{1 \le i \neq j \le n} a_i a_j \]

\(i\) and \(j\) should be different, although \(a_i\) and \(a_j\) might be equal.

Example Values

Some constants.

This is just a translation of some of the problem statement values to python so we can use them.

These are some functions to help validate the algorithms.

Brute Force Implementation

This is given as part of the problem. It traverses all the values and finds the largest product.

Because we are traversing all the numbers twice, the brute-force version has a run time of \(O(n^2)\). Since the \(n\) can be from \(2\) to \(2 \times 10^5\) that means our maximum run time will be \(4 \times 10^10\), which is too large.

Running this through the grader gives this output.

Instead of using nested for-loops, we can search the numbers twice to find the two biggest numbers, this changes the run time to \(2n\) or \(O(n)\).

This one passes the grader, doing surprisingly well, even though I was thinking it would need more optimizing.

Another Improvement

Rather than go through the second loop, I thought that since the previous maximum value is always the next highest value so far, we can just save it directly.

Stress Test

Even thought we're already passing, part of the assignment was to create a stress test to really exercise the algorithm once you have it passing.

Boosted Brute Force

To try and get this working I'm going to use numba to (hopefully) speed it enough to make the stress test runnable.

Since we need the top two values we can get a more efficient algorithm by sorting the values.

  • Coursera-Algorithmic-Toolbox
  • assignment solutions
  • 1.2 max pairwise product.py

Anoubhav Agarwaal's avatar

Fast Solution: Maximum Pairwise Product

Fast solution for the Maximum Pairwise Product Problem.

  • Testing and debugging

Fast algorithm

In search of a faster algorithm, we play with small examples like [ 5 , 6 , 2 , 7 , 4 ] [5,6,2,7,4] [ 5 , 6 , 2 , 7 , 4 ] . Eureka—it suffices to multiply the two largest elements of the array: 7 7 7 and 6 6 6 ! 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.

  M a x P a i r w i s e P r o d u c t F a s t ( A [ 1... n ] ) MaxPairwiseProductFast(A[1 . . . n]) M a x P ai r w i se P ro d u c tF a s t ( A [ 1... n ]) :   i n d e x 1 ← 1 index_1 \leftarrow 1 in d e x 1 ​ ← 1   for i i i from 2 2 2 to n n n :        if A [ i ] > A [ i n d e x 1 ] A[i] > A[index_1] A [ i ] > A [ in d e x 1 ​ ] :              i n d e x 1 ← i index_1 \leftarrow i in d e x 1 ​ ← i   i n d e x 2 ← 1 index_2 \leftarrow 1 in d e x 2 ​ ← 1   for i i i from 2 2 2 to n n n :        if A [ i ] ≠ A [ i n d e x 1 ] A[i] \neq A[index_1] A [ i ]  = A [ in d e x 1 ​ ] and A [ i ] > A [ i n d e x 2 ] A[i] > A[index_2] A [ i ] > A [ in d e x 2 ​ ] :              i n d e x 2 ← i index_2 \leftarrow i in d e x 2 ​ ← i   return A [ i n d e x 1 ] ⋅ A [ i n d e x 2 ] A[index_1] \cdot A[index_2] A [ in d e x 1 ​ ] ⋅ A [ in d e x 2 ​ ]

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

Maximum pairwise product →

Sep 2, 2017 • algorithms , C++

Let’s take a quick look at a simple problem:

Given a list of numbers, how would you determine the maximum pairwise product of numbers in the list?

For example, if we have the list [1; 3; 5; -2] the maximum pairwise product is 15 , which is the product of 3 and 5 .

The straigt-forward approach is to compute all possible pairwise products and identify the maximum among the intermediate results:

Since we have two loops that iterate over the list of numbers, the time complexity is O(n 2 ).

Can we do better? Yes, we can. The idea is to find the maximum and the second maximum elements in the list - and their product would be the maximum pairwise product.

Simple and sweet!

Search This Blog

Makingcodesimple.

Simple solutions with explanation for the problems on competitive sites like hackerearth and many many more things like how to make your code faster, shorter and simple only at makingcodesimple.blogspot.com

Coursera's Algorithmic toolbox assignment solutions( Sum of Two Digits, Maximum Pairwise Product ) :

Problem 1: sum of two digits, solution: (in c++), ( please guys before moving to the solution try it yourself at least 3-4 times , if you really wanna become a good coder).

This code is simple. There's no need for any explanation.  

Problem 2: Maximum Pairwise Product

Guys , if you have any queries related to a question or need more explanation, comment down below!  

Post a Comment

Popular posts from this blog, hackerearth's basic programming solutions( seating arrangement, zoos, anagrams ) :, hackerearth's basic programming solutions( minimize cost, magical word, best index ) :.

Navigation Menu

Search code, repositories, users, issues, pull requests..., provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

  • Notifications

This repository will contain my work from the Master Algorithmic Programming Techniques Specialization that was created by UC San Diego and delivered through Coursera.

mablatnik/Algorithmic-Toolbox

Folders and files, repository files navigation, data structures and algorithms.

This repository will contain my work from the Master Algorithmic Programming Techniques Specialization that was created by UC San Diego and delivered through Coursera. I will be implementing solutions in Python3, Java, and C++.

About This Specialization

The Specialization covers algorithmic techniques for solving problems arising in computer science applications. It is a mix of theory and practice: you will not only design algorithms and estimate their complexity, but you will get a deeper understanding of algorithms by implementing them in the programming language of your choice (C, C++, C#, Haskell, Java, JavaScript, Python2, Python3, Ruby, and Scala).

This Specialization is unique, because it offers two real-world projects. Advanced Shortest Paths project is offered in the end of the Algorithms on Graphs course. In this project, you'll deal with road network analysis and social network analysis. You'll learn how to compute the fastest route between New York and Mountain View thousands of times faster than classic algorithms and close to those used in Google Maps. Through Genome Assembly culminating project at the end of the Specialization, you'll learn how to assemble genomes from millions of short pieces and how algorithms fuel recent developments in personalized medicine.

Algorithmic Toolbox

Assignments for Algorithmic Toolbox on Coursera with time and memory results from grader

Solving a Simple Code Problem

Problem: Maximum Pairwise Product

  • Python: Max time used: 0.14/5.00, max memory used: 26456064/536870912
  • Java: Max time used: 0.07/1.00, max memory used: 21037056/536870912
  • C++: Max time used: 0.12/1.00, max memory used: 21045248/536870912

Prgramming Assignment: Introduction

Problem: Small Fibonacci Number

  • Python: Max time used: 0.02/5.00, max memory used: 8740864/536870912
  • Java: Max time used: 0.21/1.50, max memory used: 24145920/536870912
  • C++: Max time used: 0.00/1.00, max memory used: 8744960/536870912

Problem: The Last Digit of a Large Fibonacci Number

  • Python: Max time used: 0.17/5.00, max memory used: 8699904/536870912
  • Java: Max time used: 0.19/1.50, max memory used: 28651520/536870912
  • C++: Max time used: 0.00/1.00, max memory used: 8699904/536870912

Problem: Greatest Common Divisor

  • Python: Max time used: 0.05/5.00, max memory used: 9568256/536870912
  • Java: Max time used: 0.21/1.50, max memory used: 24121344/536870912
  • C++: Max time used: 0.00/1.00, max memory used: 9560064/536870912

Problem: Least Common Multiple

  • Python: Max time used: 0.09/5.00, max memory used: 9601024/536870912
  • Java: Max time used: 0.17/1.50, max memory used: 24133632/536870912
  • C++: Max time used: 0.00/1.00, max memory used: 9580544/536870912

Advanced Problem: Huge Fibonacci Number modulo m

  • Python: Max time used: 0.21/5.00, max memory used: 30359552/536870912
  • Java: Max time used: 0.17/1.50, max memory used: 30363648/536870912
  • C++: Max time used: 0.00/1.00, max memory used: 30363648/536870912

Advanced Problem: Last Digit of a Sum of Fibonacci Numbers

  • Python: Max time used: 0.06/5.00, max memory used: 9564160/536870912
  • Java: Max time used: 0.21/1.50, max memory used: 24285184/536870912
  • C++: Max time used: 0.00/1.00, max memory used: 8720384/536870912

Advanced Problem: Last Digit of a Partial Sum of Fibonacci Numbers

  • Python: Max time used: 0.05/5.00, max memory used: 8720384/536870912

Programming Assignment: Greedy Algorithms

Problem: Changing Money

  • Python: Max time used: 0.05/5.00, max memory used: 8716288/536870912
  • Java: Max time used: 0.17/1.50, max memory used: 24166400/536870912
  • C++: Max time used: 0.00/1.00, max memory used: 8716288/536870912

Problem: Fractional Knapsack

  • Python: Max time used: 0.05/5.00, max memory used: 8761344/671088640
  • Java: Max time used: 0.36/1.50, max memory used: 33243136/671088640
  • C++: Max time used: 0.00/1.00, max memory used: 8769536/671088640

Problem: Minimum Dot Product

  • Python: Max time used: 0.02/5.00, max memory used: 8945664/536870912
  • Java: Max time used: 0.31/1.50, max memory used: 32632832/536870912
  • C++: Max time used: 0.00/1.00, max memory used: 8957952/536870912

Problem: Covering Segments by Points

  • Python: Max time used: 0.03/5.00, max memory used: 9023488/536870912
  • Java: Max time used: 0.20/1.50, max memory used: 24457216/536870912
  • C++: Max time used: 0.00/1.00, max memory used: 9019392/536870912

Problem: Pairwise Distinct Summands

  • Python: Max time used: 0.07/5.00, max memory used: 9617408/536870912
  • Java: Max time used: 0.69/1.50, max memory used: 47325184/536870912
  • C++: Max time used: 0.00/1.00, max memory used: 9613312/536870912

Programming Assignment: Divide and Conquer

Problem: Binary Search

  • Python: Max time used: 0.82/10.00, max memory used: 37974016/536870912
  • Java: Max time used: 1.13/3.00, max memory used: 74174464/536870912
  • C++: Max time used: 0.10/2.00, max memory used: 37974016/536870912

Problem: Majority Element

  • Python: Max time used: 0.66/5.00, max memory used: 21393408/536870912
  • Java: Max time used: 0.36/1.50, max memory used: 42090496/536870912
  • C++: Max time used: 0.05/1.00, max memory used: 21393408/536870912

Problem: 3-Way Partition

  • Python: Max time used: 1.02/11.00, max memory used: 28880896/536870912
  • Java: Max time used: 1.16/5.50, max memory used: 70074368/536870912
  • C++: Max time used: 0.08/2.20, max memory used: 29736960/536870912

Advanced Problem: Number of Inversions

  • Python: Max time used: 0.77/15.00, max memory used: 21364736/536870912
  • Java: Max time used: 0.87/4.50, max memory used: 112693248/536870912
  • C++: Max time used: 0.05/3.00, max memory used: 21360640/536870912

Advanced Problem: Points and Segments

  • Python: Max time used: 0.41/20.00, max memory used: 44896256/536870912

Programming Assignment: Dynamic Programming

Problem: Primitive Calculator

  • Python: Max time used: 1.08/7.50, max memory used: 13688832/536870912
  • Java: Max time used: 0.19/2.25, max memory used: 32600064/536870912
  • C++: Max time used: 0.01/1.50, max memory used: 9396224/536870912

Problem: Take as Much Gold as Possible

  • Python: Max time used: 0.61/10.00, max memory used: 20611072/536870912

Problem: Compute the Edit Distance Between Two Strings

Problem: Maximize the Value of an Arithmetic Expression

Advanced Problem: Longest Common Subsequence of Three Sequences

  • Python 27.3%

Nkwachi's Cave

Solving the maximum pairwise product algorithm.

Nkwachi Nwamaghinna's photo

What is the Maximum Pairwise Product? It means that we have to find the maximum product of two distinct numbers in a given array of non-negative numbers.

Problem Statement

Given a sequence of non-negative integers a0,…,an−1, find the maximum pairwise product, that is, the largest integer that can be obtained by multiplying two different elements from the sequence.

Input format:

The first line of the input contains an integer n. The next line contains n non-negative integers a0,…,an−1 (separated by spaces).

Constraints:

2≤n≤2⋅105; 0≤a0,…,an−1≤105.

Output format:

Output a single number — the maximum pairwise product.

One approach is finding the two largest numbers in the array and storing their value in two variables and then multiplying both numbers but this approach makes you run into a problem when you have an array where the largest number is repeated e.g [2,5,9,9]. When finding the second largest number you compare against the largest number to ensure they aren't the same and you'll end up with 9 and 5 giving a maximum pairwise product of 45 instead of 81.

A better approach is to store the indices of the largest number and the second-largest number, this approach eliminates the error stated above.

My solution

Here is my solution implemented in Kotlin.

First of I created two variables to store the indices of the largest number and second-largest number. The next step was to find the largest number which was quite straightforward. When finding the second largest number I had to check if the index of the largest number is 0 and initialize the index of the second largest number to 1 instead or else I get 0 as the index of the second-largest number which is wrong.

Conclusion:

My solution has a complexity of O(n) but it can be better as I go through the array twice and it's possible to go through the array once while keeping track of the largest number and the second-largest number simultaneously. I intend to solve the algorithm using that approach so look out for part 2 on "Solving the Maximum Pairwise Product Algorithm".

  • Python Basics
  • Interview Questions
  • Python Quiz
  • Popular Packages
  • Python Projects
  • Practice Python
  • AI With Python
  • Learn Python3
  • Python Automation
  • Python Web Dev
  • DSA with Python
  • Python OOPs
  • Dictionaries
  • Python - Pair with Maximum product
  • Python - Row with Maximum Product
  • Python | Maximum of Product Pairs in Tuple List
  • Python - Minimum Product Pair in List
  • Python | Pair Product combinations
  • Python | Matrix Tuple pair Column product
  • Python program maximum of three
  • Python - Maximum product using K elements
  • Python Program for Number of pairs with maximum sum
  • Python | Maximum modulo pair
  • Python - Maximum Quotient Pair in List
  • Python - Dictionary with maximum count of pairs
  • Python Program for Maximum Product Subarray
  • Python - Itertools.Product()
  • Python | Keys with Maximum value
  • Maximum XOR pair product with a given value
  • Path with maximum product in 2-d array
  • Queries to find maximum product pair in range with updates
  • Count ordered pairs with product less than N
  • Maximum Product Subarray

Python – Pair with Maximum product

Sometimes, we need to find the specific problem of getting the pair which yields the maximum product, this can be computed by getting initial two elements after sorting. But in some case, we don’t with to change the ordering of list and perform some operation in the similar list without using extra space. Let’s discuss certain ways in which this can be performed. 

Method #1 : Using list comprehension + max() + combination() + lambda This particular task can be performed using the combination of above functions in which we use list comprehension to bind all the functionalities and max function to get the maximum prod, combination function finds all prods internally and lambda function is used to compute the product. 

Time complexity: O(n*n), where n is the length of the test_list. The list comprehension + max() + combination() + lambda takes O(n*n) time Auxiliary Space: O(n), extra space of size n is required

  Method #2 : Using list comprehension + nlargest() + combination() + lambda This method has potential of not only finding a single maximum but also k maximum product pairs if required and uses nlargest function instead of max function to achieve this functionality. 

Time Complexity: O(n), where n is the length of the input list. This is because we’re using list comprehension + nlargest() + combination() + lambda which has a time complexity of O(n) in the worst case. Auxiliary Space: O(n), as we’re using additional space res other than the input list itself with the same size of input list

Method #3 : Using max() and zip()

This method uses the zip() function to pair up adjacent elements in the input list, and the max() function to find the pair with the maximum product. The lambda function is used to extract the product of each pair.

Time Complexity: O(n) Space Complexity: O(n)

Method #4 : Using numpy:

  • Convert the input list to a NumPy array using np.array().
  • Generate a 2D array of all possible pairs of the input array using np.meshgrid().
  • Reshape the 2D array into a 1D array of pairs using np.reshape().
  • Filter out the pairs where both elements are equal using comb[:, 0] != comb[:, 1].
  • Calculate the product of each pair using np.prod() along the second axis.
  • Find the index of the maximum absolute product using np.argmax().
  • Retrieve the pair with the maximum product from the original array using the index found in step 6.
  • Convert the result to a tuple using tuple().

The time complexity : O(n^2) due to the use of np.meshgrid(), which generates a full 2D array of all possible pairs. 

The space complexity : O(n^2) due to the storage of the 2D array.

Method #5: Using itertools.product() and max()

This method involves using itertools.product() to find all possible pairs of elements in the list, and then finding the pair with the maximum product using the max() function.

step-by-step approach:

  • Import itertools  
  • Find all possible pairs of elements in the list using itertools.product()  
  • Filter out the pairs where both elements are the same using a lambda function and list comprehension Find the pair with the maximum product using the max() function and a lambda function  
  • Print the result

Time complexity: O(n^2), where n is the length of the list Auxiliary space: O(n^2) to store all the possible pairs

Please Login to comment...

Similar reads.

author

  • Python list-programs
  • Python Programs

Improve your Coding Skills with Practice

 alt=

What kind of Experience do you want to share?

IMAGES

  1. Maximum Pairwise Product

    assignment 1 maximum pairwise product

  2. Maximum Pairwise Product

    assignment 1 maximum pairwise product

  3. Let’s solve the Maximum Pairwise Product Algorithm Problem

    assignment 1 maximum pairwise product

  4. Maximum Pairwise Product Algorithm

    assignment 1 maximum pairwise product

  5. Solved Problem 1 [2pts] Find the pairwise dot products of

    assignment 1 maximum pairwise product

  6. The maximum pairwise product · For loop and ranges · Hyperskill

    assignment 1 maximum pairwise product

VIDEO

  1. Proportional meta analysis funnel forest plot in R Statistics

  2. Marketing Managers, Marketing Research, Advertising 6 4 5 6 5 6 7 4 5 7 5 5 5 4 5 4 5 5 Use α = 0 0

  3. MAX & MIN Problem

  4. 🎄 Advent of code 2023 in F#

  5. Factorial ANOVA in R is Quite Easy

  6. Max Dot Product Of Two Subsequences

COMMENTS

  1. Abd-ELrahmanHamza/Algorithmic-Toolbox

    Programming Assignment 1: Programming Challenges (OPTIONAL) Solving The Maximum Pairwise Product Programming Challenge in C++; Maximum Pairwise Product Programming Challenge; Using PyCharm to solve programming challenges (optional experimental feature) Acknowledgements (Optional)

  2. anoubhav/Coursera-Algorithmic-Toolbox

    The assignment solutions are in Python3. Disclaimer: ... Week 1- Programming Challenges . Sum of Two Digits; Maximum Pairwise Product; Week 2- Algorithmic Warm-up . Fibonacci Number; Last Digit of a Large Fibonacci Number; Greatest Common Divisor; ... (Maximum Dot Product) Collecting Signatures (Covering Segments by Points) Maximum Number of ...

  3. python

    Given a sequence of non-negative integers a0,…,an−1, find the maximum pairwise product, that is, the largest integer that can be obtained by multiplying two different elements from the sequence (or, more formally, max0≤i≠j≤n−1aiaj). Different elements here mean ai and aj with i≠j (it can be the case that ai=aj). Input format.

  4. Maximum Pairwise Product

    the maximum pairwise product from the input. Constraints \(2 \le n \le 2 \times 10^5; 0 \le a_1,\ldots,a_n\le 2 \times 10^5\) Example Values. First Input Second Input Output; 5: 5 6 2 7 4: 42: 3: ... Even thought we're already passing, part of the assignment was to create a stress test to really exercise the algorithm once you have it passing.

  5. assignment solutions/1.2 max pairwise product.py · master · rithik

    assignment solutions; 1.2 max pairwise product.py; Find file Blame History Permalink added folder assignment solutions. Moved all files to that folder · 1f7cd5cb Anoubhav Agarwaal authored Sep 12, 2018.

  6. Coursera

    Things I learnt from assignment 1 — max pairwise product problem: The dreaded O(N) Copying a list in Python is as simple as list.copy() What a "naive solution" means;

  7. Algorithmic Toolbox Course by University of California San Diego

    Solving the Maximum Pairwise Product Programming Challenge: Improving the Naive Solution, Testing, ... Programming Assignment 1: Maximum Pairwise Product ...

  8. Fast Solution: Maximum Pairwise Product

    Fast algorithm. In search of a faster algorithm, we play with small examples like [5, 6, 2, 7, 4] [5,6,2,7,4] [5, 6, 2, 7, 4].Eureka—it suffices to multiply the two largest elements of the array: 7 7 7 and 6 6 6!Since we need to find the largest and the second-largest elements, we need only two scans of the sequence.

  9. Maximum pairwise product

    For example, if we have the list [1; 3; 5; -2] the maximum pairwise product is 15, which is the product of 3 and 5. The straigt-forward approach is to compute all possible pairwise products and identify the maximum among the intermediate results: long long MaxPairwiseProduct(const vector<int>& numbers) { long long result = 0; // result to hold ...

  10. Problem 1: Sum of Two Digits

    Simple solutions for coursera's Algorithmic toolbox assignment questions: Sum of Two Digits, Maximum Pairwise Product by Making code simple! ... Problem 2: Maximum Pairwise Product Solution: (in c++) ( please guys before moving to the solution try it yourself at least 3-4 times , if you really wanna become a good coder) ...

  11. mablatnik/Algorithmic-Toolbox

    This repository will contain my work from the Master Algorithmic Programming Techniques Specialization that was created by UC San Diego and delivered through Coursera. - mablatnik/Algorithmic-Toolbox

  12. Course 1

    Problem 1: Maximum Pairwise Product. Solution: We just need to multiply 2 largest numbers. Problem 2: Great Common Devisor(GCD) The greatest common divisor GCD(a,b) of two non-negative integers a and b (which are not both equal to 0) is the greatest integer d that divides both a and b.

  13. Solving the Maximum Pairwise Product Algorithm

    What is the Maximum Pairwise Product? It means that we have to find the maximum product of two distinct numbers in a given array of non-negative numbers. Given a sequence of non-negative integers a0,…,an−1, find the maximum pairwise product, that is, the largest integer that can be obtained by multiplying two different elements from the ...

  14. Algorithmic Toolbox

    Solving the Maximum Pairwise Product Programming Challenge: Improving the Naive Solution, Testing, ... Programming Assignment 1: Maximum Pairwise Product ...

  15. python

    This python program takes user input of the number of elements in a list in the variable b and then takes user input of the list elements in list a. It then finds out the maximum product of a pair of the list elements. For example, if the list elements are 5,4 and 6, then the maximum product is 30. Can we simplify it in a way such that it takes ...

  16. Python for maximum pairwise product

    # Uses python3 def MaxPairwiseProduct(n,a,c): for i in range(0,n): for j in range (1,n): if a[i] != a[j]: m = a[i]*a[j] c.append(m) else: continue Product1 = max(c) return Product1 def MaxPairwiseProductFast(n,a): max_index1 = -1 for i in range(0,n): if a[i] > a[max_index1]: max_index1 = i else: continue #the value of the other index should be different compared to the #first, else it will ...

  17. Python

    print("The maximum product pair is : " + str(res)) Output. The original list : [3, 4, 1, 7, 9, 8] The maximum product pair is : (9, 8) This method uses the zip () function to pair up adjacent elements in the input list, and the max () function to find the pair with the maximum product. The lambda function is used to extract the product of each ...

  18. problem calculating the Maximum Pairwise Product C++

    0. This is my code for the maximum pairwise product. It takes an array of numbers, sorts them to find the first and second maximum numbers, then return the product of them. The code works for small arrays and small values. But it fails with some numbers, and also it epically fails with large numbers such as 10000 and so.