Continuous Subarray Sum - Leetcode Solution

Problem Statement

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.

A continuous subarray is a subarray that appears in consecutive positions in the array.

Example:

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.

Input: nums = [23,2,6,4,7], k = 6 Output: true Explanation: [23, 2, 6, 4] is a continuous subarray of size 4 whose elements sum up to 6 * 5 = 30.

Input: nums = [23,2,6,4,7], k = 13 Output: false

Solution

First of all, we need to understand the problem statement. We need to find a continuous subarray of size at least two whose elements sum up to a multiple of k.

To solve this problem, we can use a prefix sum approach. We can create an array of prefix sums for nums, where prefix[i] = nums[0] + nums[1] + ... + nums[i-1]. Then, we can iterate through prefix and check if there are any two indices i and j (i < j) such that (prefix[j] - prefix[i]) % K == 0. If we find such indices, we return true. Otherwise, we return false.

Here are the steps to implement the solution:

• Create an array prefix of size n+1, where n is the length of nums.
• Initialize prefix[0] to 0.
• Iterate through nums, and at each iteration i, set prefix[i+1] = prefix[i] + nums[i].
• Initialize a set seen to store the modulus of prefix[i] with k.
• Iterate through prefix, and at each iteration i, check if (prefix[i] % k) is in seen. If it is, return true. Otherwise, add (prefix[i] % k) to seen.
• Return false if you have not found a proper subarray.

Let's look at the code to implement this solution:

Python Code

def checkSubarraySum(nums, k): n = len(nums) prefix = [0] * (n + 1) for i in range(n): prefix[i+1] = prefix[i] + nums[i] seen = set() for i in range(1, n+1): mod = prefix[i] % k if mod in seen: return True seen.add(prefix[i-1] % k) return False

Time Complexity

The time complexity of this solution is O(n), where n is the length of nums. We are iterating through nums twice, which takes O(n) time. We are also using a set to store seen values, which takes O(1) time on average for each check or add operation.

Space Complexity

The space complexity of the solution is O(n) as we are using prefix and seen arrays of size n+1 and a set of size at most K (where K is the input parameter).

1