# Maximum Product of First and Last Elements of a Subsequence **Difficulty:** MEDIUM [External](https://leetcode.com/problems/maximum-product-of-first-and-last-elements-of-a-subsequence) Canonical: https://scaleengineer.com/dsa/problems/maximum-product-of-first-and-last-elements-of-a-subsequence **Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers) **Data structures:** Array **Companies:** [KLA](https://scaleengineer.com/companies/kla) --- ## 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] <= 105` * `1 <= m <= nums.length` # Approaches ## Brute Force This approach involves a straightforward, nested-loop iteration to check all valid pairs of indices `(i, j)` that can form the start and end of a subsequence of size `m`. For each pair, we calculate the product of the corresponding elements and keep track of the maximum product seen so far. The condition to ensure a valid subsequence is that the distance between the indices `j` and `i` must be at least `m - 1`, allowing `m - 2` other elements to be chosen from between them. **Time:** O(N^2) - where N is the number of elements in `nums`. The nested loops lead to a quadratic number of product calculations. · **Space:** O(1) - We only use a few variables to store the indices and the maximum product, regardless of the input size. **Pros:** Very simple to understand and implement.; Requires no extra space, making it memory efficient. **Cons:** The time complexity of O(N^2) is too slow for the given constraints (N up to 10^5) and will likely result in a 'Time Limit Exceeded' error on most platforms. ### Explanation The core idea is to exhaustively search for the best pair of elements. We can select `nums[i]` as the first element and `nums[j]` as the last element of our subsequence. For this to be possible, we must be able to select `m-2` additional elements from the original array that lie between `nums[i]` and `nums[j]`. The number of elements available between index `i` and `j` is `j - i - 1`. Thus, we must satisfy the condition `j - i - 1 >= m - 2`, which simplifies to `j - i >= m - 1`. This leads to a simple algorithm where we iterate through all possible `i` and for each `i`, we iterate through all valid `j`'s, compute the product, and update our answer. ```java class Solution { public long maximumProduct(int[] nums, int m) { int n = nums.length; if (m == 1) { long maxProd = Long.MIN_VALUE; for (int num : nums) { maxProd = Math.max(maxProd, (long) num * num); } return maxProd; } long maxProduct = Long.MIN_VALUE; for (int i = 0; i <= n - m; i++) { for (int j = i + m - 1; j < n; j++) { long product = (long) nums[i] * nums[j]; if (product > maxProduct) { maxProduct = product; } } } return maxProduct; } } ``` Note: The special handling for `m=1` can be merged into the main logic, as `j >= i + 1 - 1` becomes `j >= i`. However, separating it can make the logic for the main case `m > 1` clearer. ### Algorithm The brute-force approach systematically checks every possible pair of elements that could serve as the first and last elements of a valid subsequence. 1. Initialize a variable `maxProduct` to a very small number (e.g., `Long.MIN_VALUE`) to store the maximum product found. 2. Iterate through the array with an index `i` from `0` to `nums.length - 1`. This index `i` represents the position of the first element of the subsequence. 3. For each `i`, start a nested loop with an index `j` from `i + m - 1` to `nums.length - 1`. This index `j` represents the position of the last element. 4. The condition `j >= i + m - 1` ensures that there are at least `m - 2` elements available between indices `i` and `j` to form a subsequence of size `m`. 5. Inside the inner loop, calculate the product of `nums[i]` and `nums[j]`. Use a `long` to prevent overflow. 6. Compare this product with `maxProduct` and update `maxProduct` if the current product is larger. 7. After the loops complete, `maxProduct` will hold the maximum possible product. ## Precomputation with Auxiliary Arrays We can significantly improve upon the brute-force approach by avoiding the nested loop. The key observation is that for a fixed first element `nums[i]`, the best choice for the last element `nums[j]` (where `j >= i + m - 1`) is either the largest or smallest number in the valid range for `j`. Similarly, if we fix `nums[j]`, the best `nums[i]` is the largest or smallest in its valid range. This suggests precomputing prefix (or suffix) minimums and maximums. By spending O(N) time and space on precomputation, we can reduce the main loop to a single pass, making the overall solution linear. **Time:** O(N) - The solution involves two separate passes over the array: one for precomputation and one for finding the maximum product. Both are linear, so the total time is O(N). · **Space:** O(N) - We use two auxiliary arrays, `prefixMax` and `prefixMin`, each of size N, to store the precomputed values. **Pros:** Achieves a highly efficient linear time complexity O(N).; The logic is a standard dynamic programming/precomputation pattern. **Cons:** Requires O(N) extra space, which might be a concern for very large inputs in memory-constrained environments. ### Explanation The problem is to maximize `nums[i] * nums[j]` subject to `j - i >= m - 1`. Let's iterate through all possible indices `j` for the last element. For each `j`, the index `i` for the first element must satisfy `i <= j - m + 1`. To maximize the product `nums[i] * nums[j]`, we need to find the optimal `nums[i]` from the prefix `nums[0...j-m+1]`. If `nums[j]` is positive, we should pick the largest possible `nums[i]`. If `nums[j]` is negative, we should pick the smallest possible `nums[i]` (most negative) to make the product positive and large. This can be solved efficiently by pre-calculating the minimum and maximum values for all prefixes of the array. ```java class Solution { public long maximumProduct(int[] nums, int m) { int n = nums.length; if (n < m) return 0; // Or handle as per problem spec for invalid input // The case m=1 is equivalent to finding max(num*num), which the general // logic below correctly handles as it becomes max(nums[i]*nums[j]) for i<=j. long[] prefixMax = new long[n]; long[] prefixMin = new long[n]; prefixMax[0] = nums[0]; prefixMin[0] = nums[0]; for (int i = 1; i < n; i++) { prefixMax[i] = Math.max(prefixMax[i - 1], nums[i]); prefixMin[i] = Math.min(prefixMin[i - 1], nums[i]); } long maxProduct = Long.MIN_VALUE; // Iterate through all possible last elements `nums[j]` for (int j = m - 1; j < n; j++) { // The first element `nums[i]` must be in the range nums[0...j-m+1] int i_limit = j - m + 1; long pMax = prefixMax[i_limit]; long pMin = prefixMin[i_limit]; long currentVal = nums[j]; long candidate1 = currentVal * pMax; long candidate2 = currentVal * pMin; maxProduct = Math.max(maxProduct, Math.max(candidate1, candidate2)); } return maxProduct; } } ``` An alternative symmetric solution involves precomputing suffix min/max arrays and iterating `i` from `0` to `n-m`. ### Algorithm This approach optimizes the search for the second element. Instead of a nested loop, we precompute information about the array to find the best partner for each element in linear time. 1. We can iterate through the array, fixing one element of the product pair, and then efficiently find the best possible second element. 2. Let's fix the last element `nums[j]` and iterate `j` from `m-1` to `n-1`. 3. For a given `nums[j]`, the first element `nums[i]` must be chosen from the subarray `nums[0...k]` where `k = j - m + 1`. 4. To maximize `nums[i] * nums[j]`, we need either the maximum or minimum value from `nums[0...k]`, depending on the sign of `nums[j]`. * If `nums[j]` is positive, we need the maximum value in `nums[0...k]`. * If `nums[j]` is negative, we need the minimum value in `nums[0...k]`. 5. We can precompute two arrays, `prefixMax` and `prefixMin`, in O(N) time. `prefixMax[k]` stores the maximum value in `nums[0...k]`, and `prefixMin[k]` stores the minimum. 6. With these precomputed arrays, we can iterate `j` from `m-1` to `n-1`, find the best `nums[i]` in O(1) time, calculate the product, and update the overall maximum product. ## Optimal Single-Pass Approach The most optimal solution achieves linear time complexity without using any extra space (O(1) space). We can combine the precomputation and the main calculation into a single pass. We use a two-pointer-like approach. One pointer `j` iterates from `m-1` to the end of the array, representing the last element of the subsequence. Another pointer `i_ptr` tracks the end of the prefix from which the first element can be chosen. As `j` moves forward, `i_ptr` also moves forward, and we maintain the running minimum and maximum of the prefix ending at `i_ptr`. This way, we always have the necessary information to calculate the best product for each `j` without storing entire prefix arrays. **Time:** O(N) - Both pointers `j` and `i_ptr` traverse the array at most once from left to right. The total number of operations is proportional to N. · **Space:** O(1) - Only a few variables are used to store the running prefix min/max and pointers, independent of the input size. **Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1).; Efficiently solves the problem in a single pass. **Cons:** The logic is slightly more complex to implement correctly compared to the O(N) space solution due to the coupled movement of the two pointers. ### Explanation This approach refines the prefix array method to use constant extra space. Instead of pre-calculating and storing all prefix minimums and maximums in an array, we can calculate them as needed during a single pass. We iterate through the possible last element indices `j` from `m-1` to `n-1`. For each `j`, the first element `nums[i]` can be chosen from the prefix `nums[0...j-m+1]`. We can maintain the minimum and maximum of this prefix in two variables. As `j` increments, the prefix `nums[0...j-m+1]` grows by one element. We can update our running prefix min/max in O(1) amortized time. This is a form of a sliding window or two-pointer technique where one pointer `j` scans the array, and another pointer `i_ptr` defines the boundary of the prefix being considered. This single-pass algorithm is optimal in both time and space. ```java class Solution { public long maximumProduct(int[] nums, int m) { int n = nums.length; // This logic correctly handles m=1, as j-i >= 0 means i<=j, and // max_{i<=j}(nums[i]*nums[j]) is equivalent to max_k(nums[k]*nums[k]). if (n < m) { return 0; // Or throw an exception for invalid input } long maxProduct = Long.MIN_VALUE; long prefixMax = nums[0]; long prefixMin = nums[0]; int i_ptr = 0; // Iterate j as the index of the last element for (int j = m - 1; j < n; j++) { // The first element's index `i` can be at most `j - m + 1` int i_limit = j - m + 1; // Update prefix min/max to cover the range up to i_limit // This inner loop runs disjointly over the course of the outer loop while (i_ptr < i_limit) { i_ptr++; prefixMax = Math.max(prefixMax, nums[i_ptr]); prefixMin = Math.min(prefixMin, nums[i_ptr]); } // Now prefixMax/prefixMin are the min/max of nums[0...i_limit] long currentVal = nums[j]; long candidate1 = currentVal * prefixMax; long candidate2 = currentVal * prefixMin; maxProduct = Math.max(maxProduct, Math.max(candidate1, candidate2)); } return maxProduct; } } ``` ### Algorithm This approach builds upon the logic of the prefix array method but eliminates the need for extra space by computing the prefix information on-the-fly. 1. Initialize `maxProduct` to a very small value. 2. Initialize `prefixMax` and `prefixMin` to `nums[0]`. These will track the running min/max of the prefix relevant to the first element `nums[i]`. 3. Initialize a pointer, `i_ptr`, to `0`. This pointer marks the end of the prefix for which `prefixMax` and `prefixMin` have been calculated. 4. Iterate with a pointer `j` from `m-1` to `n-1`. This `j` represents the index of the last element. 5. For each `j`, the maximum possible index for the first element `i` is `i_limit = j - m + 1`. 6. We need the min/max of the prefix `nums[0...i_limit]`. Since our `i_ptr` might be behind `i_limit`, we advance `i_ptr` up to `i_limit`, updating `prefixMax` and `prefixMin` with each new element encountered. 7. Once `i_ptr` equals `i_limit`, `prefixMax` and `prefixMin` hold the required values. 8. Calculate the candidate product using `nums[j]` with both `prefixMax` and `prefixMin`. 9. Update the global `maxProduct` with the larger of these candidates. 10. After the loop over `j` finishes, `maxProduct` holds the result.