# 523. Continuous Subarray Sum

Hello, reader 👋🏽 ! Welcome to day 26 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: <a href="https://leetcode.com/problems/continuous-subarray-sum/" target="_blank">523. Continuous Subarray Sum</a>.

<hr />

## 🤔 Problem Statement
- Given an array of integers and an integer k, check if there exists a subarray of at least size 2 whose sum is a multiple of k.
- Return true if such a subarray exists, else false.
- **0 is always a multiple of any k**.

- E.g.:
  - `nums = [23,2,4,6,7], k = 6` => `true`
    - `[2,4]` is a subarray whose sum is divisible by k.
  - `nums = [23,2,6,4,7], k = 6` => `true`
    - `[23,2,4,6,7]` is a subarray whose sum is divisible by k.
  - `nums = [5,0,0,0], k = 3` => `true`
    - `[0, 0]` is a multiple of 3

<hr />

## 💬 Thought Process - Brute Force
- The brute force approach is to generate all the the continuous subarrays and check if any of their sum is a multiple of k.
- This works, but it's highly inefficient as it takes `O(n^2)` to generate all continuous subarrays.

## 💬 Thought Process - HashMap and Running Sum
- This idea is based on a little bit of math that can be easier to understand visually.
- But before we move on to the visual, let's vaguely look at the motivation behind this approach. 
- Suppose a subarray, let us call it `sum`, from i to j, `0 <= i < j < n` is divisible by k => `sum % k == 0`.
  - let `sum1 = nums[0] + nums[1] + ... + nums[i-1] + nums[i]`
  - let `sum2 = nums[0] + nums[1] + .... + nums[j-1] + nums[j]`
    - then, `sum1 % k == sum2 % k`
- `sum1` and `sum2` can lead to the same remainder on dividing by k only and only if there was a subarray sum in between that was a multiple of k.
- We can keep calculating the contiguous running sum and use a hash table that stores `<remainder, index>` pairs.
- Before adding the current `runningSum % k`, we check if the same remainder was already seen before and was at least 2 indices behind from current index. 
- If yes, then that means there was some subarray between the index i (previous seen remainder) and j (current index), whose sum was a multiple of k.

- Let's now look at it visually to understand a little deeper.
  ![image.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1666803909711/BOo95L-gw.png align="left")

- Two edge cases are if:
  1. The first element is itself a of k  => In this case, we should not return true, since subarray size is only 1
  2. To handle cases when the entire subarray sum with size > 2 is a multiple of k, i.e. `sum % k == 0`
- Hence we add to the hashmap pair `0, -1` which is sort of a dummy to handle the above two cases.

- This edge case can be seen below:
  ![image.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1666804129295/bhNJez0J6.png align="left")

- If you think about this carefully, this is valid because there will only be `0 to k-1` remainders between 2 multiples of k.
  
- Now that this is clear, let's head over to the code.

### 👩🏽‍💻 Solution - HashMap and Running Sum
- Below is the code for the above approach using hash map and storing previously seen remainders.
```
class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        if(nums == null || nums.length == 0) {
            return false;
        }
        
        int n = nums.length;
        
        HashMap<Integer, Integer> map = new HashMap();
        map.put(0, -1);
        int sum = 0;
        for(int i = 0; i<n; i++) {
            sum += nums[i];
            int remainder = sum % k;
            
            if(!map.containsKey(remainder) ) {
                map.put(remainder, i);
            }
            else {
                int j = map.get(remainder);
                if(i - j > 1) {
                    return true;
                }
            }
        }

        return false;
    }
}
```
```
Time Complexity: O(n)
    - n = length of array
        - Since we are only traversing the array once.
Space Complexity: O(n) or O(k)
    - n = length of array
        - If n > k, then O(n) else O(k)
```

<hr />

- You can find the code for this question in the GitHub repo here: <a href="https://github.com/bharati-21/daily-problem-solving/tree/main/523-continuous-subarray-sum" target="_blank">523. Continuous Subarray Sum</a>.

<hr />

## Conclusion
That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!