mediumArraysPattern: Prefix Sum
Maximum Equal-Endpoint Subarray Sum Solution
Problem Statement
Given an array of integers `nums` and an integer `k`, find the maximum sum of a contiguous subarray of length at least `k` such that the first and last elements of the subarray are equal. It is guaranteed that there is at least one subarray of length at least `k` that satisfies this condition.
Examples
Example 1:
Input:nums = [4, -1, 2, 4, -1, 2, 4], k = 4
Output:14
Explanation: The subarray [4, -1, 2, 4, -1, 2, 4] starts at index 0 and ends at index 6 (length 7 >= 4) with equal endpoints. Its sum is 14, which is the maximum possible.
Example 2:
Input:nums = [1, -5, 3, 1, 3], k = 3
Output:7
Explanation: The subarray [3, 1, 3] starts at index 2 and ends at index 4 (length 3 >= 3) with equal endpoints. Its sum is 7, which is the maximum possible.
Constraints
- 2 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- 2 <= k <= nums.length
- There is at least one pair of indices (i, j) such that i < j, j - i + 1 >= k, and nums[i] == nums[j].
Time: O(N) Space: O(N)
We can optimize this to O(N) time and space using prefix sums and a hash map. As we iterate through the array with a pointer j (the end of our subarray), we can dynamically 'activate' candidate starting indices i = j - k + 1. We store the minimum prefix sum encountered for each unique value in our hash map. When we are at index j, we look up the minimum prefix sum of nums[j] in our hash map and compute the maximum possible sum ending at j.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
from typing import List
import math
def max_equal_endpoint_subarray_sum(nums: List[int], k: int) -> int:
n = len(nums)
P = [0] * (n + 1)
for i in range(n):
P[i + 1] = P[i] + nums[i]
min_pref = {}
max_sum = -math.inf
for j in range(n):
i_new = j - k + 1
if i_new >= 0:
v = nums[i_new]
if v not in min_pref:
min_pref[v] = P[i_new]
else:
min_pref[v] = min(min_pref[v], P[i_new])
v_j = nums[j]
if v_j in min_pref:
curr_sum = P[j + 1] - min_pref[v_j]
if curr_sum > max_sum:
max_sum = curr_sum
return max_sum