The problem: pick four distinct indices w, x, y, z and maximise `(nums[w] * nums[x]) - (nums[y] * nums[z])`. All values are positive (1 to 10^4).
## The insight
Because every number is positive, the biggest product comes from the two largest values and the smallest product from the two smallest. So the answer is `max1 * max2 - min1 * min2`.
## Sorting: easy to explain
```python
def maxProductDifference(nums):
nums.sort()
return nums[-1] * nums[-2] - nums[0] * nums[1]
```
O(n log n). Good as a first answer.
## One pass: what the interviewer wants next
```python
def maxProductDifference(nums):
max1 = max2 = 0
min1 = min2 = float('inf')
for x in nums:
if x > max1:
max1, max2 = x, max1
elif x > max2:
max2 = x
if x < min1:
min1, min2 = x, min1
elif x < min2:
min2 = x
return max1 * max2 - min1 * min2
```
O(n) time, O(1) space. Note the two `if` blocks are independent: a single value can update both the max and min trackers, which matters when the array has exactly four elements.
## Follow-up: what if negatives are allowed?
Then "largest product" might be two very negative numbers, and "smallest product" might be a large positive times a large negative. You would track the top two and bottom two values and evaluate the few candidate pairs. Raising this unprompted shows you checked the constraint that made the simple answer valid.
---
Notes from the team behind https://www.linkjob.ai/, an AI interview assistant. (Disclosure: affiliated.)