Teaching Kids Programming – Max Product of Two Numbers


Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a list of integers nums, find the largest product of two distinct elements.

Constraints
n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [5, 1, 7]
Output
35
Explanation
35 is the largest product that can be made from 5 * 7

Example 2
Input
nums = [7, 1, 7]
Output
49
Explanation
49 is the largest product that can be made from 7 * 7. The values can be the same but they must be separate elements.

Example 3
Input
nums = [-5, 1, -7]
Output
35
Explanation
35 is the largest product that can be made from -5 * -7.

We can do it in O(N) by calculating the smallest two numbers and the largest two numbers and calculating the maximum products.
What if some numbers are negative? Could other numbers give larger products?

Max Product of Two by Sorting

We can sort the numbers in O(NLogN) and then compare the product of the max two numbers and min two numbers.

1
2
3
4
class Solution:
    def solve(self, nums):
        nums.sort()
        return max(nums[0]*nums[1], nums[-1]*nums[-2])
class Solution:
    def solve(self, nums):
        nums.sort()
        return max(nums[0]*nums[1], nums[-1]*nums[-2])

Optimial Algorithm to compute the Max Product of Two

We only need to store the maximum two and the minimum two, so we can perform a linear scan:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def solve(self, nums):
        big1 = big2 = -math.inf
        small1 = small2 = math.inf
        for i in nums:
            if i >= big1:
                big2 = big1
                big1 = i
            elif i >= big2:
                big2 = i
            if i <= small1:
                small2 = small1
                small1 = i
            elif i <= small2:
                small2 = i
        return max(big1*big2, small1*small2)
class Solution:
    def solve(self, nums):
        big1 = big2 = -math.inf
        small1 = small2 = math.inf
        for i in nums:
            if i >= big1:
                big2 = big1
                big1 = i
            elif i >= big2:
                big2 = i
            if i <= small1:
                small2 = small1
                small1 = i
            elif i <= small2:
                small2 = i
        return max(big1*big2, small1*small2)

The time complexity is O(N).

Max product of either two numbers or three numbers:

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
498 words
Last Post: GoLang: Check if the Sentence Is Pangram
Next Post: Automate Freeze (Stake) Balance on Tron Blockchain using NodeJs with TronWeb/TronGrid

The Permanent URL is: Teaching Kids Programming – Max Product of Two Numbers

Leave a Reply