[Algorithm] Maximum Size Subarray Sum Equals k

Maximum Size Subarray Sum Equals k

Problem Statement:

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead.

Example 1:

Given nums = [1, -1, 5, -2, 3], k = 3,
return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)

Example 2:

Given nums = [-2, -1, 2, 1], k = 1,
return 2. (because the subarray [-1, 2] sums to 1 and is the longest)

Follow Up:
Can you do it in O(n) time?

Solution: Prefix Sum + Hash Table

This problem can be solved using prefix sums. The original question really boils down to this equation: prefix_sum[i] - prefix_sum[j] = k (where i > j), and we need to find the maximum gap of i and j. We can use a hash table keyed by prefix sums and the value should be the index. There might be multiple prefix_sum[i] that is of equal value and we just need to keep the lowest. And we put a key-value pair of (0, -1) to cover cases where the entire prefix_sum[i] is a possible subarray which meets requirements.

Once the hash table is built we can do a O(n) search on each prefix_sum[i] to find the prefix_sum[j] = prefix_sum[i] - k and keep the max length.

Code implementation (version 1):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

class Solution { public: int maxSubArrayLen(vector<int>& nums, int k) { int n = nums.size(); unordered_map<int, int> prefix; prefix[0] = -1; int sum = 0; for (int i=0; i<n; i++) { sum += nums[i]; if (prefix.find(sum) == prefix.end()) { prefix[sum] = i; } nums[i] = sum; } int len = 0; for (int i=n-1; i>=0; i--) { int current = nums[i]; if (prefix[sum] == i) prefix.erase(sum); int target = current - k; auto it = prefix.find(target); if (it != prefix.end()) { len = max(len, i - it->second); } } return len; } };

This implementation does some redundant work since the way it maintains the relationship of i > j is by scanning backwards and removing prefix_sum[i] if it's the lowest index for this prefix sum. The removing can be avoided if we search while we are inserting new prefix sums. We can do a search for prefix_sum[j] before we insert prefix_sum[i].

Code implementation (version 2):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

class Solution { public: int maxSubArrayLen(vector<int>& nums, int k) { int n = nums.size(); unordered_map<int, int> prefix; prefix[0] = -1; int len = 0; int sum = 0; for (int i=0; i<n; i++) { sum += nums[i]; int target = sum - k; auto it = prefix.find(target); if (it != prefix.end()) { len = max(len, i - it->second); } if (prefix.find(sum) == prefix.end()) { prefix[sum] = i; } } return len; } };