Maximum Product of First and Last Elements of a Subsequence solution and explanation
4 more videos on this problem
LeetCode 3584. Maximum Product of First and Last Elements of a Subsequence | Prefix Max && MinLeet's Code · 20:29 · 900 views
3584. Maximum Product of First and Last Elements of a Subsequence (Leetcode Medium)Programming Live with Larry · 11:21 · 609 views
LeetCode 3584 - Maximum Product of First and Last Elements of a Subsequence | C++ | Contest 454BEASTCODES · 14:56 · 318 views
Q3. Maximum Product of First and Last Elements of a Subsequence || Weekly Contest 454 LolCode · 5:08 · 206 views
3584. Maximum Product of First and Last Elements of a Subsequence | Weekly Contest 454 | Java CodingExpertFunda · 38:01 · 116 views
The problem
You are given an integer array nums and an integer m.
Return the maximum product of the first and last elements of any subsequence of nums of size m.
Example 1:
Input: nums = [-1,-9,2,3,-2,-3,1], m = 1
Output: 81
Explanation:
The subsequence [-9] has the largest product of the first and last elements: -9 * -9 = 81. Therefore, the answer is 81.
Example 2:
Input: nums = [1,3,-5,5,6,-4], m = 3
Output: 20
Explanation:
The subsequence [-5, 6, -4] has the largest product of the first and last elements.
Example 3:
Input: nums = [2,-1,2,-6,5,2,-5,7], m = 2
Output: 35
Explanation:
The subsequence [5, 7] has the largest product of the first and last elements.
Constraints:
1 <= nums.length <= 105-105 <= nums[i] <= 1051 <= m <= nums.length
Approach overview
Problem Overview: You are given an array and must choose a subsequence with at least two elements. The score of the subsequence is the product of its first and last elements. The task is to compute the maximum possible product across all valid subsequences.
The key observation: once the first and last elements are chosen, the elements in between do not affect the score. Any subsequence that starts at index i and ends at index j (with i < j) produces the value nums[i] * nums[j]. The problem reduces to selecting two indices in order that maximize this product.
Approach 1: Brute Force Pair Enumeration (O(n²) time, O(1) space)
Enumerate every pair of indices (i, j) where i < j. Each pair represents a valid subsequence whose first element is nums[i] and last element is nums[j]. Compute the product for every pair and track the maximum value. This approach is straightforward and confirms the core observation that the subsequence interior does not matter. However, it performs n(n-1)/2 comparisons, which becomes too slow for large inputs.
This brute force strategy is useful when first reasoning about the problem, but interviewers expect you to recognize that only prefix values influence the result. Once you fix the last index, you only need the best candidate from the prefix before it.
Approach 2: Enumeration + Maintaining Prefix Extremes (O(n) time, O(1) space)
Iterate through the array while treating each index j as the last element of the subsequence. The first element must come from the prefix [0, j-1]. To maximize the product, the optimal candidate is either the largest value or the smallest value seen so far.
This works because multiplication with a negative number can flip the sign. If nums[j] is positive, pairing it with the maximum prefix value produces the best result. If it is negative, pairing it with the minimum prefix value may create a larger positive product. Maintain two variables while scanning the array: prefixMax and prefixMin. For each index, compute:
max(nums[j] * prefixMax, nums[j] * prefixMin)
Update the global answer, then update the prefix extremes using the current element. This converts the quadratic search into a single linear pass while keeping only constant memory.
This technique appears frequently in array optimization problems and resembles patterns used in maximum product subarray problems. It also aligns with reasoning used in many two pointers or prefix-scanning strategies where you accumulate best candidates from one side of the array.
Recommended for interviews: Start by explaining the brute force pair enumeration to demonstrate understanding of the subsequence definition. Then transition to the prefix-extremes optimization. Interviewers expect the O(n) scan with maintained minimum and maximum prefix values because it shows awareness of sign interactions and efficient array traversal patterns.
Solution
We can enumerate the last element of the subsequence, assuming it is nums[i]. Then the first element of the subsequence can be nums[j], where j leq i - m + 1. Therefore, we use two variables mi and mx to maintain the prefix minimum and maximum values respectively. When traversing to nums[i], we update mi and mx, then calculate the products of nums[i] with mi and mx, taking the maximum value.
The time complexity is O(n), where n is the length of array nums. And the space complexity is O(1).
class Solution:
def maximumProduct(self, nums: List[int], m: int) -> int:
ans = mx = -inf
mi = inf
for i in range(m - 1, len(nums)):
x = nums[i]
y = nums[i - m + 1]
mi = min(mi, y)
mx = max(mx, y)
ans = max(ans, x * mi, x * mx)
return ansclass Solution {
public long maximumProduct(int[] nums, int m) {
long ans = Long.MIN_VALUE;
int mx = Integer.MIN_VALUE;
int mi = Integer.MAX_VALUE;
for (int i = m - 1; i < nums.length; ++i) {
int x = nums[i];
int y = nums[i - m + 1];
mi = Math.min(mi, y);
mx = Math.max(mx, y);
ans = Math.max(ans, Math.max(1L * x * mi, 1L * x * mx));
}
return ans;
}
}class Solution {
public:
long long maximumProduct(vector<int>& nums, int m) {
long long ans = LLONG_MIN;
int mx = INT_MIN;
int mi = INT_MAX;
for (int i = m - 1; i < nums.size(); ++i) {
int x = nums[i];
int y = nums[i - m + 1];
mi = min(mi, y);
mx = max(mx, y);
ans = max(ans, max(1LL * x * mi, 1LL * x * mx));
}
return ans;
}
};function maximumProduct(nums: number[], m: number): number {
let ans = Number.MIN_SAFE_INTEGER;
let mx = Number.MIN_SAFE_INTEGER;
let mi = Number.MAX_SAFE_INTEGER;
for (let i = m - 1; i < nums.length; i++) {
const x = nums[i];
const y = nums[i - m + 1];
mi = Math.min(mi, y);
mx = Math.max(mx, y);
ans = Math.max(ans, x * mi, x * mx);
}
return ans;
}func maximumProduct(nums []int, m int) int64 {
ans := int64(math.MinInt64)
mx := math.MinInt32
mi := math.MaxInt32
for i := m - 1; i < len(nums); i++ {
x := nums[i]
y := nums[i-m+1]
mi = min(mi, y)
mx = max(mx, y)
ans = max(ans, max(int64(x)*int64(mi), int64(x)*int64(mx)))
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Enumeration | O(n²) | O(1) | Good for understanding the problem or when constraints are very small |
| Enumeration + Maintaining Prefix Extremes | O(n) | O(1) | Optimal solution for large arrays; tracks prefix max and min while scanning once |
Frequently asked questions
Is Maximum Product of First and Last Elements of a Subsequence easy or hard?
The problem is typically classified as Medium difficulty. The brute force idea is simple, but recognizing that only prefix extremes matter—and handling negative numbers correctly—requires stronger array optimization intuition.
Maximum Product of First and Last Elements of a Subsequence Python/Java solution
Python, Java, C++, Go, and TypeScript implementations follow the same logic: iterate through the array, maintain prefixMax and prefixMin, and update the maximum product using nums[j] multiplied by both extremes. The algorithm runs in O(n) time and O(1) space in all languages.
How to solve Maximum Product of First and Last Elements of a Subsequence in O(n)?
Treat each element as the potential last element of the subsequence. Maintain two variables while iterating: the maximum and minimum values seen in the prefix. For every position j, compute nums[j] * prefixMax and nums[j] * prefixMin, update the global maximum, then update the prefix extremes with nums[j].
What is the best approach for Maximum Product of First and Last Elements of a Subsequence?
The optimal approach scans the array once while maintaining the maximum and minimum values seen in the prefix. For each index treated as the last element, compute the product with both prefix extremes and update the answer. This enumeration plus prefix-extremes technique runs in O(n) time and O(1) space.
Is Maximum Product of First and Last Elements of a Subsequence asked at Google/Amazon/Meta?
Problems involving maximum product pairs and prefix extreme tracking appear frequently in interviews at companies like Amazon, Google, and Meta. The pattern of maintaining running minimum and maximum values is commonly tested in array optimization questions.
What data structure is used in Maximum Product of First and Last Elements of a Subsequence?
The solution primarily uses simple variables while iterating through an array. Two prefix trackers—maximum and minimum—store the best candidates for the first element of the subsequence. No additional data structures are required beyond constant space variables.
What is the time complexity of Maximum Product of First and Last Elements of a Subsequence?
The optimal solution runs in O(n) time because the array is scanned once while tracking prefix minimum and maximum values. A naive brute force solution checks every pair of indices and takes O(n²) time. Both approaches use O(1) extra space.