1464. Maximum Product of Two Elements in an Array

#second fire day

Given the array of integers nums, you will choose two different indices i and j of that array. Return the maximum value of (nums[i]-1)*(nums[j]-1).

sol

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        maxi = 0
        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                now = (nums[i] - 1) * (nums[j] - 1)
                if now > maxi:
                    maxi = now
        return maxi

LeetCode - The World’s Leading Online Programming Learning Platform

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

LeetCode

I solve this problem in classic way. Since I seems to have to take two loop for i and j, took two loop (which will make this algorithm $O(n^2)$) and updated maxi when appeared maximum value of (nums[i]-1)*(nums[j]-1). This is classis way of brute force for this problem.

Brute force is not a good one, when there is other way to solve a problem. If there is better way to solve a problem, always recommend to take the other way. Show you way.

As you can see, the memory efficiency and runtime is not as good as other solutions. There must be other way to solve it

Other solution with heap

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        heap = [-num for num in nums]
        heapq.heapify(heap)
        n1 = -1 * heapq.heappop(heap)
        n2 = -1 * heapq.heappop(heap)

        return (n1-1) * (n2-1)

This hit my balls. Heap is a data structure which always spit the lowest number in the heap. So it called "minimum heap(최소힙)". As the numbers put in heap in reverse way with minus in front of it, it becomes a "maximun heap with minus".

So what this problem what is the maximun two integer. Pop twice will give you this. And just plus this. End...

It would be good for me and you to learn about heap structure. It used in computer memory and many other algorithms.