↓Skip to main content
  1. LeetCode/

LeetCode 1464: Maximum Product of Two Elements in an Array

·1 min· ·
LeetCode Easy Array Sorting Heap-Priority-Queue
Wei Yi Chung
Author
Wei Yi Chung
Working at the contributing of open source, distributed systems, and data engineering.
Table of Contents

Meta Data
#

Difficulty: easy First Attempt: 2022-11-21

  • Submissions: Accepted (first try)

Approach
#

Since nums[i] >= 1, every (x - 1) is non-negative, so the two largest values maximize the product. Track the largest and second largest in one pass (or pop twice from a heap, Heap).

My Attempts
#

Passed on the first try by negating everything into a heap and popping twice for the two largest.

Solution
#

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        a = b = 0
        for x in nums:
            if x > a:
                a, b = x, a
            elif x > b:
                b = x
        return (a - 1) * (b - 1)

Complexity
#

Time O(n), space O(1).

Mistakes to Avoid
#

  • When a new maximum arrives, the old maximum becomes the second largest.

Interview Explanation
#

With positive values the best product uses the two largest numbers minus one each, which I track in one pass. Time O(n), space O(1).

Related

LeetCode 1337: The K Weakest Rows in a Matrix
·1 min
LeetCode Easy Array Binary-Search Sorting Heap-Priority-Queue
LeetCode 1337 note: soldiers come first in each row, so binary search the first 0 for the count; sort by (count, row index) and take k
LeetCode 506: Relative Ranks
·1 min
LeetCode Easy Array Sorting Heap-Priority-Queue
LeetCode 506 note: sort indices by score descending, give medals to the top three and rank strings to the rest, writing back into the original positions
LeetCode 2357: Make Array Zero by Subtracting Equal Amounts
·1 min
LeetCode Easy Array Hash-Table Greedy Sorting
LeetCode 2357 note: each operation zeroes the group of the smallest positive value, so the answer is the number of distinct positive values
LeetCode 215: Kth Largest Element in an Array
·2 mins
LeetCode Medium Array Divide-and-Conquer Sorting Heap-Priority-Queue
LeetCode 215 note: keep a min-heap of size k whose top is the k-th largest, or use quickselect for O(n) on average
LeetCode 1122: Relative Sort Array
·1 min
LeetCode Easy Array Hash-Table Sorting Counting-Sort
LeetCode 1122 note: count first, emit values in arr2’s order, then append the remaining values in ascending order
LeetCode 1030: Matrix Cells in Distance Order
·2 mins
LeetCode Easy Array Math Geometry Sorting
LeetCode 1030 note: list every coordinate and sort by Manhattan distance to the center; return coordinates, not distances