LC 523. Continuous Subarray Sum

Sarthak Sehgal · April 4, 2020

medium   arrays   math

Approach 1

This is a straightforward approach and the interviewer probably expects you to discuss this approach. Approach 2 has some observational maths involved which makes the time complexity better. The idea here is to preprocess the array and store the prefix sum for each index (preSum[i] = sum of arr[0] to arr[i]). Then, iterate through the prefix sum array and if we find preSum[j] - preSum[i] to be divisible by k, that means we have found a subarray.

public class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0)   return false;
        
        int[] preSum = new int[nums.length+1];
        
        for (int i = 1; i <= nums.length; i++) {
            preSum[i] = preSum[i-1] + nums[i-1];
        }
        
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+2; j <= nums.length; j++) {
                if (k == 0) {
                    if (preSum[j] - preSum[i] == 0) {
                        return true;
                    }
                } else if ((preSum[j] - preSum[i]) % k == 0) {
                    return true;
                }
            }
        }
        return false;
    }
}

Time complexity: O(n^2)
Space complexity: O(n) or O(1) if you store prefix sum in the input array itseld

Approach 2

Let’s say he have two number a and b where a%k == b%k. This means that (a-b)%k == 0. This is because:

Let a = p*k + r
    b = q*k + r

Note that a%k = b%d = r

a - b = (p-q)%k

So (a-b)%k = 0

We will use this idea to solve the question. Let’s store (prefix sum)%k for each index instead of the prefix sum itself. Now, if for some index i, preSum[i]%k = X and then for another index j, preSum[j]%k = X. By the above property, (preSum[j]-preSum[i])%k = 0. This means that the subarray i+1..j is divisible by k.

Code:

bool checkSubarraySum(vector<int>& nums, int k) {
        int preSum = 0;
        unordered_map<int, int> vis;
        vis[0] = -1;
        for (int i=0; i<nums.size(); i++) {
                preSum += nums[i];
                if (k!=0) preSum %= k;
                if (vis.find(preSum) != vis.end()) {
                        if (i-vis[preSum]>1)
                                return true;
                } else {
                        vis[preSum] = i;
                }
        }

        return false;
}

Time complexity: O(n)
Space complexity: O(1)

Twitter, Facebook