Lintcode 1844 subarray sum equals to k II

LintCode – ChatGPT！A more effective learning experience!

Description

Given an array of integers and an integer k, you need to find the minimum size of continuous no-empty subarrays whose sum equals to k, and return its length.

if there are no such subarray, return -1.

the integer nums[i] may be negative

Example

Example1

Input: 
nums = [1,1,1,2] and k = 3
Output: 
2

Example2

Input: 
nums = [2,1,-1,4,2,-3] and k = 3
Output: 
2

Thoughts

Before we approach this problem, let’s first talk about a concept called prefixSum.

prefixSum[i] is the sum of the first i elements in the array (index from 0 to i - 1)

To get the sum up to the element that has a index of i from the prefixSum array, we simply get it by prefixSum[i + 1]

For the sum between index i to j we can use prefixSum[j+1] - prefixSum[i] to calculate

So the first element in prefixSum array prefixSum[0] should be 0 , which means the sum of the first 0 elements of the array is 0

We can generate the prefixSum array by looping through the array in O(n) time

Now let’s take a look at this problem.

The naive way to solve this would be the brute force where we find the all the subarrays and see if they are equal to k , at the same time we see if the length of the subarray is the minimum. This would give us O(n^2) time complexity.

What if we want O(n) time complexity instead? Then we cannot have nested loops. Think about the condition the subarray has to meet:

you need to find the minimum size of continuous no-empty subarrays whose sum equals to k, and return its length

With the prefixSum we talked about earlier, we can check if:

prefixSum[end + 1] - prefixSum[start] === k

Where start and end denote the boundary of the subarray

If we want to solve it in O(n) , we can probably only iterate over one of the boundaries, either start or end . Then if we transform the check a little bit:

prefixSum[end + 1] - k === prefixSum[start]

Now the check becomes: given an index end , is there a value that equals to prefixSum[end + 1] - k in the prefixSum array?

Then we need to figure out how to look up this information quickly, preferably with O(1) complexity. The first thing that comes to mind is: Map . Basically we keep a reversed map between the prefixSum array index and value.

Solution

export class Solution {
  /**
   * @param nums: a list of integer
   * @param k: an integer
   * @return: return an integer, denote the minimum length of continuous subarrays whose sum equals to k
   */
  subarraySumEqualsKII(nums, k) {
    let prefixSum = [0];
    let sumToIndex = {0: 0};
    let result = Infinity;

    for(let i = 0; i < nums.length; i++) {
        prefixSum[i + 1] = prefixSum[i] + nums[i]
    }

    for(let end = 0; end < nums.length; end++) {
        const sum = prefixSum[end + 1] - k
        if(sumToIndex[sum] !== undefined) {
            const length = end + 1 - sumToIndex[sum];
            result = Math.min(length, result)
        }
        sumToIndex[prefixSum[end + 1]] = end + 1
    }

    return result === Infinity ? -1 : result
  }
}

There are a couple of tricky parts:

How to calculate the length the subarray, you might need to try a few examples to figure it out
How do we decide when to update the sumToIndex map? For this particular problem, we can just update it at each iteration, because we are looking for the min length, it’s desired that we override the previous value with the same key so the index is larger. e.g


nums: [10, 0, ...]

previous sumToIndex: {10: 1}

now we are at index 1 and its prefixSum is also 10, we would want to override
the current value for key 10 with 2

new sumToIndex: {10: 2}

What if we actually want the Max length instead of the Min length? Can we still use the same logic for updating the sumToIndex map?

The answer is No, we don’t want to update/override the existing key in sumToIndex if we see it again because we want a smaller index for the prefixSum value. So we would make a small change here:

FROM:

for(let end = 0; end < nums.length; end++) {
    const sum = prefixSum[end + 1] - k
    if(sumToIndex[sum] !== undefined) {
	      const length = end + 1 - sumToIndex[sum];
	      result = Math.min(length, result)
    }
    sumToIndex[prefixSum[end + 1]] = end + 1
}

TO:

for(let end = 0; end < nums.length; end++) {
    const sum = prefixSum[end + 1] - k
    if(sumToIndex[sum] !== undefined) {
	      const length = end + 1 - sumToIndex[sum];
	      result = Math.max(length, result)
    } else {
		    /// we only update sumToIndex 
		    /// only if the prefixSum value is not present in it
		    sumToIndex[prefixSum[end + 1]] = end + 1
    }
}

Lintcode 1844 subarray sum equals to k II