Continuous Subarray Sum LeetCode Solution

Table of Contents

Problem Statement

Continuous Subarray Sum LeetCode Solution – Given an integer array nums and an integer k, return true if nums has a continuous subarray of the size of 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^5m
0 <= nums[i] <= 10⁹
0 <= sum(nums[i]) <= 2³¹ - 1
1 <= k <= 2³¹ - 1

Approach

Idea:

this problem is the same as Subarray sum equals K with some modification
We need a subarray say from i to j such that sum of all elements is divisible by k.
We make a prefix sum array where prefixSum[i] is the (sum of first i elements)%k.
for some prefixSum(0,j) , we need to check if there exist some prefixSum(0,i) such that both are equal.
if they both are equal then it means the subarray i+1 to j has sum==0 so this subarray is divided by k

Code:

Continuous Subarray Sum C++ Leetcode Solution:

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        
        int n=nums.size();
        
        vector<int> arr(n,0);
        
        arr[0]=nums[0]%k;
        
      unordered_map<int,int> mp;
        
        mp.insert({arr[0],0});
        
        for(int i=1;i<n;i++)
        {
            arr[i]=nums[i]+arr[i-1];
            arr[i]=arr[i]%k;
            
           if(arr[i]==0)return true;

            
            if(mp.find(arr[i])!=mp.end()){
            
                int idx=mp[arr[i]];
                
                if(i-idx==1)continue;
                
                return true;
            }
          
          
            mp[arr[i]]=i;
        }
        
        return false;
    }
};

Continuous Subarray Sum Java Leetcode Solution:

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>(){{put(0,-1);}};;
    int runningSum = 0;
    for (int i=0;i<nums.length;i++) {
        runningSum += nums[i];
        if (k != 0) runningSum %= k; 
        Integer prev = map.get(runningSum);
        if (prev != null) {
            if (i - prev > 1) return true;
        }
        else map.put(runningSum, i);
    }
    return false;
}
}

Complexity Analysis :

Time Complexity:

The Time Complexity of the above solution is O(n) where n = the size of the input array since we traversed the entire array once.

Space Complexity:

The Space Complexity of the above solution is O(n) for prefix sum and O(k) for hashmap.