Maximum Equal-Endpoint Subarray Sum — Problem Statement & Solution Guide
Problem Description
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.
Examples
Input
[4, -1, 2, 4, -1, 2, 4, -1, 2, 4]
Output
12
Explanation: Step-by-step: Given the input array [4, -1, 2, 4, -1, 2, 4, -1, 2, 4], we first find all subarrays of length at least 2 where the first and last elements are equal. Then, we calculate the sum of each subarray and return the maximum sum.
Input
[3, 1, 3, 1, 3]
Output
9
Explanation: Step-by-step: Given the input array [3, 1, 3, 1, 3], we first find all subarrays of length at least 2 where the first and last elements are equal. Then, we calculate the sum of each subarray and return the maximum sum.
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].
Optimal Approach & Strategy
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.
Brute Force Approach
The brute force approach is to check every pair of indices (i, j) such that j - i + 1 >= k and nums[i] == nums[j]. For each valid pair, we compute the sum of the subarray from i to j using a nested loop or prefix sums. This takes O(N^2) time, which will result in a Time Limit Exceeded (TLE) error given the constraints.
Verified Code Solutions
function maxEqualEndpointSubarraySum(nums, k) {
const n = nums.length;
const P = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) {
P[i + 1] = P[i] + nums[i];
}
const minPref = new Map();
let maxSum = -Infinity;
for (let j = 0; j < n; j++) {
const iNew = j - k + 1;
if (iNew >= 0) {
const v = nums[iNew];
if (!minPref.has(v)) {
minPref.set(v, P[iNew]);
} else {
minPref.set(v, Math.min(minPref.get(v), P[iNew]));
}
}
const vJ = nums[j];
if (minPref.has(vJ)) {
const currSum = P[j + 1] - minPref.get(vJ);
if (currSum > maxSum) {
maxSum = currSum;
}
}
}
return maxSum;
}#include <vector>
#include <unordered_map>
#include <algorithm>
#include <climits>
class Solution {
public:
int maxEqualEndpointSubarraySum(std::vector<int>& nums, int k) {
int n = nums.size();
std::vector<long long> P(n + 1, 0);
for (int i = 0; i < n; ++i) {
P[i + 1] = P[i] + nums[i];
}
std::unordered_map<int, long long> min_pref;
min_pref.reserve(n);
long long max_sum = LLONG_MIN;
for (int j = 0; j < n; ++j) {
int i_new = j - k + 1;
if (i_new >= 0) {
int v = nums[i_new];
auto it = min_pref.find(v);
if (it == min_pref.end()) {
min_pref[v] = P[i_new];
} else {
it->second = std::min(it->second, P[i_new]);
}
}
int v_j = nums[j];
auto it = min_pref.find(v_j);
if (it != min_pref.end()) {
long long curr_sum = P[j + 1] - it->second;
if (curr_sum > max_sum) {
max_sum = curr_sum;
}
}
}
return static_cast<int>(max_sum);
}
};class Solution {
public int maxEqualSum(int[] nums, int k) {
if (k > nums.length) {
return 0;
}
int max_sum = Integer.MIN_VALUE;
for (int i = 0; i <= nums.length - k; i++) {
int window_sum = 0;
for (int j = i; j < i + k; j++) {
window_sum += nums[j];
}
if (nums[i] == nums[i + k - 1] && window_sum > max_sum) {
max_sum = window_sum;
}
}
return max_sum;
}
}def maxEqualSum(nums, k):
if k > len(nums):
return 0
max_sum = float('-inf')
for i in range(len(nums) - k + 1):
window_sum = sum(nums[i:i+k])
if nums[i] == nums[i+k-1] and window_sum > max_sum:
max_sum = window_sum
return max_sumfunction maxEqualEndpointSubarraySum(nums, k) {
const n = nums.length;
const P = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) {
P[i + 1] = P[i] + nums[i];
}
const minPref = new Map();
let maxSum = -Infinity;
for (let j = 0; j < n; j++) {
const iNew = j - k + 1;
if (iNew >= 0) {
const v = nums[iNew];
if (!minPref.has(v)) {
minPref.set(v, P[iNew]);
} else {
minPref.set(v, Math.min(minPref.get(v), P[iNew]));
}
}
const vJ = nums[j];
if (minPref.has(vJ)) {
const currSum = P[j + 1] - minPref.get(vJ);
if (currSum > maxSum) {
maxSum = currSum;
}
}
}
return maxSum;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.