Continuous Subarray Sum

Table of Contents

Leetcode 523. Continuous Subarray Sum

Problem

Given an integer array nums and an integer k, return true if nums has a continuous subarray of size at least two whose elements sum up to a multiple of k, or false otherwise.

An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.

Example 1:

Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

Example 2:

Input: nums = [23,2,6,4,7], k = 6
Output: true
Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42.
42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.

Example 3:

Input: nums = [23,2,6,4,7], k = 13
Output: false

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁹
0 <= sum(nums[i]) <= 2³¹ - 1
1 <= k <= 2³¹ - 1

Source: Leetcode 523. Continuous Subarray Sum

Solution

A naive approach

The simplest way to think of this problem is taking cumulative sum from an index up to the end of the array and check if any of those sums % k = 0 or not. We will have to do this for each index and this will definitely give a solution.

But this approach will cost us O(N2) [O N square] runtime which is not efficient and we don't want that! So, let's not waste time on it. If you want, you can think of it and even try it to some coding practice. No harm in doing that if you have enough time, right?

A better approach

The naive approach is not so bad as we might think, at least it will be thought provoking for the better approach which we will show in a moment.

Unlike the naive approach, we will still take cumulative sum but only from the beginning of the array. But how it will help?

To answer this question, let’s think about what it means for a contiguous subarray sum divisible by k?

This means the sum of that portion of the array modulus k is 0! Let’s say we started to take cumulative sum from the beginning and at some point A, we found p = A % k [p is some arbitrary number].

We continue moving and doing the cumulative sum and after some time at some point B, we again found p = B % k [p is some arbitrary number].

So, for point A and B, A % k = B % k

which means, B % k – A % k = 0

in other words, (B – A) % k = 0

What does this mean? This means, the cumulative some difference from B to A is divisible by k, in other words, the subarray sum from A to B is divisible by k!

Let’s have a look at the below image if you find hard time to understand the concept.

Implementation

Now we have the basic, we can think about how to implement it.

All we need is to run a for loop from the beginning of the array and take cumulative sum in a variable. Also we take cumulative sum mod k (to know the p, an arbitrary number) and save p somewhere. If any point, we find that the same p was found before, we can tell that the point where it is found now and the point where it was found before -are the two points of our contiguous subarray whose sum is divisible by k.

To save p values and their location, we can simply use a hash map with key as p values and value as index (location). Also, we need to check the length of contiguous subarray should be at least 2.

Below images describe the implementation more clearly (hopefully!).

Implementation Details

Let’s say we have an array as below. We also have k = 10 and a map m initialized with m[0] = -1 (why? please think about it! You can try submitting your code without this initialization, when you will get wrong answer or something, play with the test cases and try to understand why this initialization is crucial! If you find out why, please do a favour to explain in comment 🙂 )

Now, we started our for loop and added up the cumulative sum and cumulative sum mod k (p value). Plus we started to save the p value and location (index) in the map as below.

We continue doing the same for index 1….

And for index 2 … but wait! For index 2 the p value is 5 which was seen at index 0…. and is 2 – 0 >= 2 ? very hard question!

So, this is how we find the answer.

Complexity

Since we are running the loop once, it’s an O(N) time complexity thing. For using map, we need extra space of O(N) as well.

Code

C++

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        
        if(nums.size() < 2)
            return false;
        
        map<int, int> m;
        m[0] = -1; //This is CRITICAL!!!!!!!!!!! Think why it is critical and answer in comment :)
        int cumulative_sum = 0;
        for(int i = 0; i < nums.size(); i++){
            cumulative_sum += nums[i];
            int res = 0;
            if(k > 0)
                res = cumulative_sum % k;
            
            if(m.find(res) != m.end()){
                if(i - m[res] > 1) return true;
            }
            
            if(m.find(res) == m.end())
                m[res] = i;
        }
        
        return false;
    }
};

Conclusion

Hope you enjoyed this post. If you do, please write your feedback in the comment. If you did not enjoy, please write about your anger, frustration as well! We are always open to any kind of feedback.

Happy coding! 🙂