523. Continuous Subarray Sum

Continuous Subarray Sum

Problem Description

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 = 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

Approach) Brute Force

var checkSubarraySum = function(nums, k) {
    
    for (let i = 1; i < nums.length; i++) {
        let sum = nums[i]
        for (let j = i - 1; j >= 0; j--) {
            sum += nums[j]
            if (sum % k === 0 || sum === k) return true
        }
    }

    return false
    
};

Approach) Hashmap

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var checkSubarraySum = function(nums, k) {

    let sum = 0
    const hash = {}
    hash[0] = -1
    
    for (let i = 0; i<nums.length; i++) {
        sum += nums[i]
        
        if (k!=0) sum %= k
        
        if ( hash[sum] !== undefined   ) {
            if(i-hash[sum]>1) return true
        } else {
            hash[sum] = i
        }
    }
    
    return false
};

Approach) Set

var checkSubarraySum = function (nums, k) {
	let sum = 0
	let prefix = 0;
	const hash = new Set();
	
	for (let i = 0; i < nums.length; i++) {
		sum += nums[i]
		if (k != 0) sum %= k
		if(hash.has(sum)) return true
		hash.add(prefix);
		prefix = sum;
	}
	return false
};

Approach) Native 

var checkSubarraySum = function(nums, k) {
    if (k == 1 || k == -1) {
        if (nums.length > 1) {
            return true
        }
    }
    let sums = new Set()
    let sum = 0
    let answer = false
    for (let i = 0; i < nums.length; i++) {
        if (i > 0 && (nums[i] == 0 && nums[i-1] == 0)) {
            answer = true
            break
        }
        sum += nums[i]
        let mod = sum % k
        if (k != 0) {
            if (nums[i] % k != 0) {
                if ((sums.has(mod) || mod == 0) && i>0) {
                    answer = true
                    break
                } else if (mod >= 0) {
                    sums.add(mod)
                }
            } 
        } else {
            if (sum == 0 && i > 0) {
                answer = true
                break
            } else {
                if (nums[i] != 0) {
                    if (sums.has(sum)) {
                        answer = true
                        break
                    } else {
                        sums.add(sum)
                    }
                } 
            }
        }
        
        
    }
    return answer
};

Approach) Sum Count

var checkSubarraySum = function(nums, k) {
    const sumCount = new Map([[0, 1]]);
    let sum = 0;

    for (const num of nums) {
        sum = (sum + num) % k;

        if (sumCount.has(sum))
            if (sumCount.get(sum) > 1 || num % k)
                return true;

        sumCount.set(sum, 1 + (sumCount.get(sum) || 0));        
    }
    
    return false;
}; 

Approach) Dynamic Programming

Idea is to first transform nums array into sum array, such that every element in array is equal to sum of all its previous elements.
Then iterate through the array and find currentElement % k of each element. Check if the modulo number is in Map already.
If not then put the modulo into map as key and current index as value.
We are keeping index as value to make sure the numbers are atleast 1 index apart.
If we find the modulo num in map, then check if the curresponding value is is atleast 1 index away from current index.
If yes then we found the ans and return true.

var checkSubarraySum = function(nums, k) {
    let map = new Map();
	map.set(0, -1);
    
    for(let i = 1; i < nums.length; i++){
        nums[i] += nums[i - 1];
    }
    
    for(let i = 0; i < nums.length; i++) {
        let res = nums[i];

        if(k !== 0) res = res % k;
        
        if(map.has(res) && i - map.get(res) > 1) return true;
        
        if(!map.has(res)) map.set(res, i);
    }
    
    return false;
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #523. Continuous Subarray Sum

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!