Maximum Product of Two Elements in an Array - Video Solutions

Problem Overview: You are given an integer array nums. Choose two different indices i and j such that the value (nums[i] - 1) * (nums[j] - 1) is maximized. The task reduces to finding the two largest numbers in the array because subtracting 1 from both still preserves the order of maximum values.

Approach 1: Sorting Maximum Two Elements (Time: O(n log n), Space: O(1) or O(log n))

Sort the array and use the last two elements since they are the largest values. After sorting, compute (nums[n-1] - 1) * (nums[n-2] - 1). This approach relies on sorting to organize values so the largest elements appear at the end. The implementation is short and reliable because sorting handles all ordering logic. Use this method when code simplicity matters more than strict linear time performance.

Approach 2: Single Pass for Maximum Two Elements (Time: O(n), Space: O(1))

Iterate through the array once while tracking the largest and second largest values. For each number, compare it with the current maximum; if it becomes the new maximum, shift the previous maximum to second place. Otherwise update the second maximum when appropriate. After the loop, compute (max1 - 1) * (max2 - 1). This method uses the core idea behind many array scanning problems: maintain running candidates during a single traversal. It avoids sorting entirely and achieves optimal linear time.

Approach 3: Max Heap (Priority Queue) (Time: O(n log n) or O(n + log n), Space: O(n))

Insert all elements into a max heap and extract the top two values. A heap (priority queue) always keeps the largest element accessible at the root. After removing the two largest values, compute the product using the required formula. This approach is helpful when the problem extends to repeatedly retrieving largest elements, though it is unnecessary overhead for a single query.

Recommended for interviews: The single-pass solution is what interviewers usually expect. It demonstrates that you recognized the key observation: only the two largest numbers matter. The sorting approach still shows correct reasoning and is acceptable for an easy problem, but the O(n) scan highlights stronger algorithmic awareness and space efficiency.