This blog post will cover how to make the conceptual leap from a naive O(n^2) solution to a O(n) solution. Rather than just giving an answer, the goal of this post is explain in detail how to think about approaching these problems to make that leap.
The problem found on LeetCode:
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)
The negative numbers make it more complicated, because you will have to know the sum of all the other numbers in the array. Often the first approach for a naive solution is to use a loop within a loop. For each item in the array, add up all the remaining numbers in the array. Keep track of the length of the longest subarrays that add up to the target value and replace it if a larger value is found.
Solution #1: O(n^2)
This could be solved in JavaScript with the following. This gives us O(n^2) time complexity.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
const maxSubArrayLen = (nums, k) => { let currentSum = 0; let longest = 0; // Go through each number for (let i = 0; i < nums.length; i++) { // Get the total sum of the current item through the end // of the array for (let j = i; j < nums.length; j++) { currentSum += nums[j]; if (currentSum === k) { // If a value is found that matches the target value k, // use the length of the current subarray as the best value longest = Math.max(longest, j - i + 1); } } // Reset for the next summation through the array currentSum = 0; } return longest; }; |
Solution #2: Greedy Algorithm
How do we make the jump to a better time complexity? We are doing a lot of the same calculations over again. Every time we go through the inner loop, we are adding up numbers we have already added up. It seems we could probably get this down to O(n) by using a greedy approach. We can store values of the summations we have calculated already, or memoize them in a hash map / object. That way we don’t have to go through the inner loop at all.
The tricky part is deciding how to store the values. In this case, we will store the current running sum as the key, and the index of that summation as the value.
Visualize The Concept
Before diving into that code, let’s look at this conceptually. What we really want is to cut off the beginning of the array (from the beginning up to Location A) where we know that we already have a summation. That initial summation is equal to the total current summation (at Location B) minus our target value.
Take the illustration, which shows an example array with the solution. Our target value will be 24.
We see the values 9 + 8 + 7 add up to 24, our target value. The total sum of all values up to that point in the array (Location B) is 29. We subtract our target value (24) from our running total (29), which gives us 5. We check our memo object by looking up the key for the 5. We find that it exists because we already calculated that value at stored an index for it. The index we are storing is the location where we have calculated that sub amount (Location A). In other words, when we were at index 2 of the array, we already calculated a sum of 5.
We can “chop off” that part of the array (from the beginning to Location A). We just want the difference in indices from Location A to Location B. That gives us the longest sub array for the target value.
Solution #2: The Code
As we loop through the array, we take the current running total and store it as a key in our memo object. We will store the current index as the value for that key. The reason we take this approach is because we ultimately want to return the length of the longest subarray, so we care most about retrieving indexes. This part may feel a little backwards. However, it makes sense to look up the already calculated values in O(1) time. By storing the indexes as the values, it makes it easier to do calculations for the length of the subarray.
Conceptual pitfall: You initial instincts may tempt you to do the opposite and store the indexes as the key, and the sum for that location as a value. But this puts us right back into our original problem of having to loop through a data structure for each location in the array. To calculate the difference from the current total and the target, we would then have to loop through all the keys of the object to find out if we had already calculated the difference just to to find the index..
The code below is one possible solution.
|
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 32 |
const maxSubArrayLen = (nums, k) => { // Initialize the memo with value 0 with an index of -1 // Required for length calculations to include beginning // of the array // (e.g. off by one errors) const memo = {'0': -1}; let currentSum = 0; let longest = 0; for (var i = 0; i < nums.length; i++) { // Get the current running total currentSum += nums[i]; if (!(currentSum in memo)) { // If we don't have a value for the sum, store it // in the memo. We always want to store the first one, // since it will give us the longest subarray memo[currentSum] = i; } // Difference between our total sum and our target value let diff = currentSum - k; if (diff in memo) { // If a key for a sum exists in the memo, then we know // we have found a valid sub array // Example: Total Sum (29) - Location A (5) = Target (24) // Indexes: Loc B idx (5) - Loc A Idx (2) = Longest (3) longest = Math.max(longest, i - memo[diff]); } } return longest; }; |