LeetCode 3584 - Maximum Product of First and Last Elements of a Subsequence

The problem asks for the maximum possible product of the first and last elements of any subsequence of length m chosen from an integer array nums.

leetcodemediumarraytwo-pointers

LeetCode Problem 3584

Difficulty: 🟡 Medium
Topics: Array, Two Pointers

Solution

Problem Understanding

The problem asks for the maximum possible product of the first and last elements of any subsequence of length m chosen from an integer array nums. A subsequence means we can pick elements in order from the array, not necessarily contiguous, as long as their indices are strictly increasing. However, only the first and last elements of the chosen subsequence matter for the final product; all middle elements exist only to satisfy the subsequence length requirement.

In other words, we are selecting indices i1 < i2 < ... < im, and the value we care about is nums[i1] * nums[im]. The middle elements do not affect the product but constrain feasibility because we must be able to pick m - 2 elements between the first and last indices.

The constraints show that nums.length can be up to 10^5, which immediately rules out any quadratic or combinatorial enumeration of subsequences. Values can range between -10^5 and 10^5, meaning negative numbers are significant and we must consider both maximum and minimum values when computing products.

Edge cases include when m = 1, where the subsequence consists of a single element and the product becomes nums[i] * nums[i], effectively the maximum square of any element. Another important case is when m = nums.length, where the subsequence must include the entire array, so the answer is simply nums[0] * nums[n-1].

Approaches

The brute-force approach considers every subsequence of size m, computes its first and last elements, and tracks the maximum product. While correct, this is infeasible because the number of subsequences grows combinatorially as O(n choose m), which is far too large for n = 10^5.

The key insight is that only the first and last chosen indices matter, and any valid subsequence of length m imposes a constraint on the distance between those indices. If we pick indices i < j, then we must ensure there are at least m - 2 indices between them, meaning j - i + 1 >= m. Once this constraint is satisfied, all intermediate elements can always be chosen arbitrarily from within the range.

This reduces the problem to choosing a pair (i, j) with sufficient distance, maximizing nums[i] * nums[j]. For each valid j, we need the best possible nums[i] among all valid i positions. Because numbers can be negative, we must track both the maximum and minimum values seen so far in the valid prefix.

Approach Time Complexity Space Complexity Notes
Brute Force O(C(n, m) · m) O(m) Enumerates all subsequences and computes endpoints
Optimal O(n) O(1) Maintains prefix min and max for valid starting indices

Algorithm Walkthrough

The optimal solution reframes the problem as a constrained two-index optimization problem over valid subsequence endpoints.

  1. We first observe that for any fixed ending index j, the starting index i must satisfy i <= j - (m - 1) to ensure there are enough elements between them to form a subsequence of length m. This defines a sliding boundary for valid i values.
  2. We iterate through the array using j as the potential last element of the subsequence. The valid starting region for i expands as j increases, but only includes indices up to j - (m - 1).
  3. While moving j, we maintain two running values over all valid i indices: the maximum value seen so far and the minimum value seen so far. We need both because multiplying by a negative number can turn a small value into a large product.
  4. At each position j, once we have at least one valid i, we compute two candidate products: nums[j] * max_prefix and nums[j] * min_prefix. The maximum of these two is the best subsequence ending at j.
  5. We update the global answer with the best product found for each j.
  6. We update the prefix extrema as the valid range expands.

The algorithm carefully ensures that only valid subsequence endpoints are considered while maintaining sufficient information to evaluate all possibilities efficiently.

Why it works

The correctness relies on the invariant that at every step, we maintain the best and worst possible starting values among all indices that can legally serve as the first element of a length-m subsequence ending at or beyond the current position. Since any valid subsequence is fully determined by its endpoints, and all middle elements are always constructible as long as spacing is satisfied, evaluating all valid endpoint pairs guarantees the optimal solution.

Python Solution

from typing import List

class Solution:
    def maximumProduct(self, nums: List[int], m: int) -> int:
        n = len(nums)
        
        if m == 1:
            best = float("-inf")
            for x in nums:
                best = max(best, x * x)
            return best
        
        best = float("-inf")
        
        prefix_max = float("-inf")
        prefix_min = float("inf")
        
        # i can be valid start only up to j-(m-1)
        for j in range(m - 1, n):
            i = j - (m - 1)
            
            # expand prefix window to include new valid start index
            if i - 1 >= 0:
                val = nums[i - 1]
                prefix_max = max(prefix_max, val)
                prefix_min = min(prefix_min, val)
            
            # initialize at first valid window
            if prefix_max == float("-inf"):
                prefix_max = nums[0]
                prefix_min = nums[0]
            
            best = max(
                best,
                nums[j] * prefix_max,
                nums[j] * prefix_min
            )
        
        return best

The implementation first handles the special case m = 1, where the answer is simply the maximum square value in the array. For m > 1, it iterates over all possible ending indices j. For each j, it expands the valid starting region and updates the running minimum and maximum values of eligible starting elements. It then computes the best possible product using the current ending value and updates the global result.

Go Solution

func maximumProduct(nums []int, m int) int64 {
    n := len(nums)
    
    if m == 1 {
        var best int64 = int64(nums[0]) * int64(nums[0])
        for _, v := range nums {
            prod := int64(v) * int64(v)
            if prod > best {
                best = prod
            }
        }
        return best
    }
    
    var best int64 = -1 << 63
    
    prefixMax := nums[0]
    prefixMin := nums[0]
    
    for j := m - 1; j < n; j++ {
        i := j - (m - 1)
        
        if i-1 >= 0 {
            val := nums[i-1]
            if val > prefixMax {
                prefixMax = val
            }
            if val < prefixMin {
                prefixMin = val
            }
        }
        
        prod1 := int64(nums[j]) * int64(prefixMax)
        prod2 := int64(nums[j]) * int64(prefixMin)
        
        if prod1 > best {
            best = prod1
        }
        if prod2 > best {
            best = prod2
        }
    }
    
    return best
}

In Go, the main difference is careful handling of integer overflow by converting intermediate products to int64. We also use explicit comparisons instead of Python’s built-in max and min. The logic remains identical: maintain a dynamic prefix of valid starting elements and compute the best product at each endpoint.

Worked Examples

Example 1

nums = [-1,-9,2,3,-2,-3,1], m = 1

Since m = 1, every element is a valid subsequence. We compute squares:

At each step, we track:

  • -1 → 1
  • -9 → 81 (best so far)
  • 2 → 4
  • 3 → 9
  • -2 → 4
  • -3 → 9
  • 1 → 1

Final answer is 81.

Example 2

nums = [1,3,-5,5,6,-4], m = 3

We evaluate valid (i, j) pairs with distance constraint j - i + 1 >= 3.

For each j:

  • j = 2 (-5): valid i = 0, product 1 * -5 = -5, 3 * -5 = -15
  • j = 3 (5): valid i ∈ {0,1}, best max = 3, min = 1, best product = 5 * 3 = 15
  • j = 4 (6): valid i ∈ {0,1,2}, max = 3, min = -5, best = 6 * 3 = 18
  • j = 5 (-4): valid i ∈ {0,1,2}, max = 3, min = -5, best = (-4) * (-5) = 20

Final answer is 20.

Example 3

nums = [2,-1,2,-6,5,2,-5,7], m = 2

Now we only need pairs with at least 2 elements between constraint simplifies to adjacent valid index spacing ≥ 1.

We track best pairs:

  • Best positive pair found is (5,7) giving 35
  • Other pairs are smaller due to negatives or smaller magnitudes

Final answer is 35.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is processed once as part of prefix maintenance and endpoint evaluation
Space O(1) Only a constant number of variables are maintained

The linear time complexity comes from the single pass over the array, where each index contributes at most constant work. No auxiliary data structures grow with input size.

Test Cases

assert Solution().maximumProduct([-1,-9,2,3,-2,-3,1], 1) == 81  # single-element subsequence squares
assert Solution().maximumProduct([1,3,-5,5,6,-4], 3) == 20      # mixed positives and negatives
assert Solution().maximumProduct([2,-1,2,-6,5,2,-5,7], 2) == 35 # best pair with constraint
assert Solution().maximumProduct([5], 1) == 25                  # single element edge case
assert Solution().maximumProduct([-2,-3,-4], 2) == 12          # two negatives produce positive
assert Solution().maximumProduct([1,2,3,4,5], 5) == 5          # full array constraint
assert Solution().maximumProduct([-1,1,-1,1], 2) == 1          # alternating signs
Test Why
single element array verifies m = 1 and minimal input handling
mixed positives and negatives validates optimal handling of sign combinations
general case m = 2 ensures basic pair logic correctness
single value edge case where only one subsequence exists
all negatives ensures max/min interaction correctness
m equals n ensures full array constraint handling
alternating signs tests stability under frequent sign flips

Edge Cases

One important edge case is when m = 1. In this case, the subsequence consists of a single element, so the first and last elements are the same. This changes the problem into finding the maximum square of any element. A naive implementation might incorrectly treat this as a pair-selection problem, but the correct handling requires explicitly squaring each element.

Another edge case occurs when all numbers are negative. In such cases, the optimal solution often comes from selecting the least negative numbers or leveraging multiplication of two negatives. The algorithm handles this correctly by maintaining both the minimum and maximum prefix values, ensuring that negative multiplication opportunities are not missed.

A third edge case is when m = n. Here, there is exactly one valid subsequence, the entire array. The result is simply nums[0] * nums[n-1]. The algorithm naturally handles this because only one endpoint pair is ever considered valid, and the prefix window expands to include all possible starting indices before reaching the last element.