Skip to content

Continuous Subarray Sum

Leetcode 523. Continuous Subarray Sum

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 * k0 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 <= 105
  • 0 <= nums[i] <= 109
  • 0 <= sum(nums[i]) <= 231 - 1
  • 1 <= k <= 231 - 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 % kA % k = 0

in other words, (BA) % 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.

Leetcode 523. Continuous Subarray Sum
Leetcode 523. Continuous Subarray Sum
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 🙂 )

Leetcode 523. Continuous Subarray Sum
Leetcode 523. Continuous Subarray Sum

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.

Leetcode 523. Continuous Subarray Sum
Leetcode 523. Continuous Subarray Sum

We continue doing the same for index 1….

Leetcode 523. Continuous Subarray Sum
Leetcode 523. Continuous Subarray Sum

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!

Leetcode 523. Continuous Subarray Sum
Leetcode 523. Continuous Subarray Sum

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! 🙂

81 thoughts on “Continuous Subarray Sum”

  1. Your article gave me a lot of inspiration, I hope you can explain your point of view in more detail, because I have some doubts, thank you.

  2. Thanks for sharing superb informations. Your website is so cool. I’m impressed by the details that you have on this site. It reveals how nicely you perceive this subject. Bookmarked this website page, will come back for more articles. You, my friend, ROCK! I found just the info I already searched all over the place and just could not come across. What a perfect website.

  3. Heya i’m for the first time here. I came across this board and I find It truly useful & it helped me out much. I’m hoping to provide one thing again and aid others like you helped me.

  4. This is really interesting, You’re a very skilled blogger. I’ve joined your feed and look forward to seeking more of your magnificent post. Also, I’ve shared your site in my social networks!

  5. The standard chunk of Lorem Ipsum used since the 1500s is reproduced below for those interested.

  6. Наша группа профессиональных специалистов приготовлена предложить вам актуальные подходы, которые не только предоставят надежную протекцию от холодильности, но и подарят вашему зданию элегантный вид.
    Мы практикуем с новейшими материалами, утверждая постоянный время использования и превосходные эффекты. Изоляция фронтонов – это не только сокращение расходов на отапливании, но и заботливость о экосистеме. Спасательные подходы, какие мы претворяем в жизнь, способствуют не только дому, но и сохранению природных ресурсов.
    Самое ключевое: [url=https://ppu-prof.ru/]Наружное утепление фасада цена[/url] у нас составляет всего от 1250 рублей за метр квадратный! Это доступное решение, которое сделает ваш хаус в истинный тепличный корнер с минимальными затратами.
    Наши пособия – это не исключительно теплоизоляция, это создание области, в где каждый член отражает ваш уникальный образ. Мы примем в расчет все ваши требования, чтобы преобразить ваш дом еще больше приятным и привлекательным.
    Подробнее на [url=https://ppu-prof.ru/]http://ppu-prof.ru[/url]
    Не откладывайте труды о своем корпусе на потом! Обращайтесь к специалистам, и мы сделаем ваш дом не только теплее, но и моднее. Заинтересовались? Подробнее о наших сервисах вы можете узнать на веб-ресурсе. Добро пожаловать в мир спокойствия и уровня.

  7. It was impossible for me to leave your website without expressing my gratitude for the excellent knowledge you give your visitors. Without a doubt, I’ll be checking back frequently to see what updates you’ve made.

  8. Уважаемые Клиенты!
    Предлагаем вам новейшее концепцию в мире дизайна внутреннего пространства – шторы плиссе. Если вы движетесь к совершенству в всей нюансе вашего жилища, то эти гардины окажутся великолепным паттерном для вас.
    Что делает шторы плиссе таковыми особенными? Они сочетают в себе в себе шик, использование и применимость. Благодаря эксклюзивной постройке, технологичным материалам, шторы плиссе идеально гармонизируются с для какова угодно интерьера, будь то гостинка, спальня, плитка или рабочее место.
    Закажите [url=https://tulpan-pmr.ru]шторы плиссе[/url] – создайте уют и великолепие в вашем доме!
    Чем манят шторы плиссе для вас? Во-первых, их самобытный образ, который присоединяет к привлекательность и шик вашему внутреннему пространству. Вы можете выискать из различных текстур, оттенков и подходов, чтобы выделить отличительность вашего дома.
    Кроме того, шторы плиссе предлагают массивный круг функциональных возможностей. Они могут управлять уровень света в помещении, остерегать от солнечного света, поддерживать интимность и формировать уютную среду в вашем доме.
    Мы сайт: [url=https://tulpan-pmr.ru]www.tulpan-pmr.ru[/url]
    Мы сами поддержим вам выбрать шторы плиссе, какие идеально подойдут для вашего внутреннего пространства!

Leave a Reply

Your email address will not be published. Required fields are marked *