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 = 6Output:trueExplanation:[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 = 6Output:trueExplanation:[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 = 13Output:false

**Constraints:**

`1 <= nums.length <= 10`

^{5}`0 <= nums[i] <= 10`

^{9}`0 <= sum(nums[i]) <= 2`

^{31}- 1`1 <= k <= 2`

^{31}- 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! 🙂

Picture this – 3 am in the morning, I had a line of fiends stretched around the corner of my block. It was in the freezing middle of January but they had camped out all night, jumping-ready to buy like there was a sale on Jordans. If you were 16 years old, in my shoes, you’d do anything to survive, right? I got good news though; I MADE IT OUT OF THE HOOD, with nothing but a laptop and an internet connection. I’m not special or lucky in any way. If I, as a convicted felon that used to scream “Free Harlem” around my block until my throat was sore, could find a way to generate a stable, consistent, reliable income online, ANYONE can! If you’re interested in legitimate, stress-free side hustles that can bring in $3,500/week, I set up a site you can use: https://incomecommunity.com

Hello foolishhungry.com owner, Your posts are always well-written and easy to understand.

To the foolishhungry.com webmaster, Thanks for the detailed post!

Hello foolishhungry.com webmaster, You always provide clear explanations and step-by-step instructions.

Dear foolishhungry.com webmaster, Thanks for the detailed post!

Dear foolishhungry.com webmaster, Your posts are always a great read.

To the foolishhungry.com owner, Your posts are always informative and up-to-date.