<p>Given an integer array nums and an integer k, return <code>true</code> <em>if </em><code>nums</code><em> has a <strong>good subarray</strong> or </em><code>false</code><em> otherwise</em>.</p>

<p>A <strong>good subarray</strong> is a subarray where:</p>

<ul>
	<li>its length is <strong>at least two</strong>, and</li>
	<li>the sum of the elements of the subarray is a multiple of <code>k</code>.</li>
</ul>

<p><strong>Note</strong> that:</p>

<ul>
	<li>A <strong>subarray</strong> is a contiguous part of the array.</li>
	<li>An integer <code>x</code> is a multiple of <code>k</code> if there exists an integer <code>n</code> such that <code>x = n * k</code>. <code>0</code> is <strong>always</strong> a multiple of <code>k</code>.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [<u>23,2,6,4,7</u>], k = 6
<strong>Output:</strong> true
<strong>Explanation:</strong> [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.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [23,2,6,4,7], k = 13
<strong>Output:</strong> false
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>0 &lt;= sum(nums[i]) &lt;= 2<sup>31</sup> - 1</code></li>
	<li><code>1 &lt;= k &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

// Author: Kemal Tahir Bıcılıoğlu
// Question Link: https://leetcode.com/problems/continuous-subarray-sum/

/*
    We need to continuously sum the elements and add the mod k of the summations to our map.
    This enables us to check if the current sum % k was previously found. For example:
    for the array [23, 2, 4, 6, 7] and k = 6 -> prefix sum (mod k) = [0, 5, 1, 5, 5, 0]
    the sum of the elements from the indices 0 to 1 [23] (mod 6) = 5, also the sum of the 
    elements from the indices 0 to 3 [23, 2, 4] (mod 6) = 5. This means the summation of the
    array created by the elements between these subarrays in mod 6 = 0 so that both of them are
    the same. Considering this, we need to keep the remainders in a map to remember for the next
    remainders. There is one more constraint for the subarrays which is being at least in 2 
    length. We can check it by adding also the indices in the map, and when we call map.find()
    if the current remainder is found we need also to check if the current index - founded index
    > 1 because this makes the array created by the elements in between are at least in 2 length.
*/
// Also observe that we do not need to keep an array for the continuos sums. We can just
// keep an integer variable for the continuos sum. This makes space complexity O(1) for keeping
// sums, however we are keeping the remainders in the map so it makes space complexity O(n)

// Time complexity: O(n logn)
// Space complexity: O(n)

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        vector<int> prefix_sum(nums.size()+1, 0);
        unordered_map<int, int> rems; // remainders
        rems.insert({0,0});

        for(int i = 0; i < nums.size(); i++){
            prefix_sum[i+1] = prefix_sum[i] + nums[i];
            prefix_sum[i+1] %= k;
            auto it1 = rems.find(prefix_sum[i+1]); // check if we found the same rem. before in the map
            if(it1 != rems.end() && abs((it1->second) - (i+1)) > 1){
                return true;
            } // if yes and they are good subarray return true, if not add to the map 
            rems.insert({prefix_sum[i+1], i+1});
        }
        return false;
    }
};
153627