Continuous Subarray Sum

Leetcode Problem 523: Continuous Subarray Sum

Problem Summary

Given an integer array nums and an integer k, return true if there exists a contiguous subarray of length at least 2 whose elements sum to a multiple of k (including zero), and false otherwise.

Constraints:

• The array has between 1 and 100,000 elements.
• Each element is a non-negative integer up to 1,000,000,000.
• The total array sum fits in a 32-bit unsigned integer.
• k is a positive integer up to 2^31 − 1.

Techniques

• Array
• Hash Table
• Math
• Prefix Sum

Solution

function checkSubarraySum(nums: number[], k: number): boolean {
    let prefixSum = 0;
    let subarrays = 0
    let previousPrefixSumPositions = new Map<number, number>()

    previousPrefixSumPositions.set(0, -1)

    for (let i = 0; i < nums.length; i++) {
        prefixSum = prefixSum + nums[i] 
        let remainder = prefixSum % k;

        if (remainder < 0) { 
            remainder += k;
        }

        const firstPositionOfRemainder = previousPrefixSumPositions.get(remainder)
        
        if (firstPositionOfRemainder !== undefined && (i - firstPositionOfRemainder) >= 2) {
            return true
        } 
        
        if(firstPositionOfRemainder === undefined) {
            previousPrefixSumPositions.set(remainder, i)
        }          
    }

    return false
};


console.log(checkSubarraySum([23,2,4,6,7], 6))
console.log(checkSubarraySum([23,2,6,4,7], 6))