Maximum Equal-Endpoint Subarray Sum — Problem Statement & Solution Guide

ArraysMediumPrefix Sum

TimeO(n)

SpaceO(n)

Quick Answer & Algorithm Key Takeaway

Cumulative sum for range queries

TopicArrays

PatternPrefix Sum

TimeO(n)

SpaceO(n)

Problem Description

Given an integer array nums and an integer k, identify a contiguous subarray whose length is at least k and whose first and last elements are identical. Among all such subarrays, return the greatest possible sum of its elements. If no subarray satisfies the equal‑endpoint condition, output 0. The algorithm must run in O(n) or O(n log n) time and use O(n) additional memory.

DSA Pattern Breakdown

"Maximum Equal-Endpoint Subarray Sum"

medium

WHY DOES IT MATTER?

This pattern—combining prefix sums with earliest‑index hashing—is a staple for any problem that asks for optimal subarray metrics under positional constraints. It transforms a quadratic search into a linear scan, which is crucial for real‑time analytics and large‑scale data pipelines.

OPTIMIZATION CHALLENGE

The breakthrough is realizing that only the earliest occurrence of each value matters for maximizing the sum, because any later start would produce a smaller or equal subarray length and thus a smaller sum when using the same end index.

REAL-WORLD CONNECTION

Imagine a log‑aggregation service that needs to find the longest time window where the first and last event types are identical and the total number of processed requests is maximized. Storing the earliest timestamp for each event type and using cumulative request counts mirrors the prefix‑sum + hashmap technique.

During an interview, compute the prefix sum on the fly (no separate array needed) and update the hash map only when you see a value for the first time; this saves both time and memory and demonstrates you can think in‑place.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(n)

Core Theory — Why This Approach?

The key to solving this problem efficiently lies in the prefix‑sum technique combined with a hash map that records the earliest occurrence of each array value. A prefix sum array P where P[i] = sum of nums[0..i‑1] lets us compute the sum of any subarray [l, r] in O(1) as P[r+1]‑P[l]. For a subarray to be valid, nums[l] must equal nums[r] and (r‑l+1) ≥ k. By scanning the array once, we can store for each distinct value the smallest index where it appears. When we encounter the same value later at index r, we check whether the distance to the stored index l satisfies the length constraint; if it does, the subarray sum is P[r+1]‑P[l]. Keeping the maximum of these candidates yields the answer.

A naïve solution would enumerate every pair (l, r), verify the equal‑endpoint condition, and compute the sum, resulting in O(n²) time – infeasible for n up to 10⁵ or higher. The optimal paradigm replaces the double loop with a single pass, leveraging constant‑time look‑ups in the hash map and O(1) subarray sum retrieval via prefix sums. This reduces the overall complexity to linear time while using linear extra space for the map and prefix array.

Interview Questions on This Problem

Q1How would you modify the solution if the subarray length must be exactly k instead of at least k?

Maintain a sliding window of size k and a hash map that stores the most recent index of each value within the window. For each window ending at r, check if nums[r] equals the value at the window's start (index r‑k+1); if they match, compute the window sum using a running total and update the maximum. This runs in O(n) time with O(1) extra space for the sum and O(k) for the map.

Q2Can the algorithm handle negative numbers in the array, and why does it still work?

Yes. Prefix sums correctly represent cumulative totals regardless of sign, and the hash map only tracks positions, not values of sums. The length constraint ensures we only consider subarrays of sufficient size, and the maximum sum comparison naturally accounts for negative totals.

Q3What would change if we needed the maximum product of a valid subarray instead of the sum?

The product version is far more complex because multiplication does not have an easy inverse like subtraction for sums, especially with zeros and negatives. One would need to segment the array around zeros and use prefix products with careful handling of sign changes, leading to O(n) but with additional bookkeeping for the count of negative numbers in each segment.

Examples

Example 1

Input

nums = [4, 2, 1, 2, 4, 3], k = 3

Output

Explanation: All subarrays with length ≥ 3 and equal endpoints are: - indices 0‑4 → [4,2,1,2,4] (sum = 13) - indices 1‑3 → [2,1,2] (sum = 5) The first one yields the maximum sum, so the answer is 13.

Example 2

Input

nums = [5, 1, 5, 5, 2, 5], k = 2

Output

Explanation: Valid subarrays (length ≥ 2, same first and last value) include: - 0‑2 → [5,1,5] (sum = 11) - 0‑3 → [5,1,5,5] (sum = 16) - 0‑5 → [5,1,5,5,2,5] (sum = 23) - 2‑3 → [5,5] (sum = 10) - 2‑5 → [5,5,2,5] (sum = 17) - 3‑5 → [5,2,5] (sum = 12) The subarray 0‑5 gives the largest sum of 23, which is returned.

Example 3

Input

nums = [1, 2, 3, 4], k = 2

Output

Explanation: No contiguous subarray of length at least 2 has the same first and last element. According to the specification, the result is 0.

Constraints

1 <= nums.length <= 100000
-10^9 <= nums[i] <= 10^9
1 <= k <= nums.length

Optimal Approach & Strategy

Maintain a running prefix sum and a hash map of the earliest index for each value; for each element, use the map to evaluate a candidate subarray in O(1) and update the maximum, achieving O(n) time.

Brute Force Approach

Enumerate every possible subarray, verify the equal‑endpoint condition and length ≥ k, compute its sum, and keep the maximum; this costs O(n²) time.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

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_sum

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;
}

Asked in Top Tech Interviews

Amazon

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.