Problem statement

Given an integer array nums and an integer k, return true if nums has a good subarray.

A good subarray has length at least two and a sum that is a multiple of k. Note that 0 is always a multiple of k.

Example 1

Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2,4] sums to 6.

Example 2

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

Example 3

Input: nums = [1,0], k = 2
Output: false
Explanation: The only length-2 subarray sums to 1.

Constraints

• 1 <= nums.length <= 40
• 0 <= nums[i] <= 1000
• 1 <= k <= 100

Hints for Continuous Subarray Sum

1. Hint 1

   A subarray sum is a multiple of k exactly when its two bounding prefix sums share the same remainder mod k.

2. Hint 2

   Store the earliest index at which each remainder appears.

3. Hint 3

   Enforce the length rule by requiring the two indices to be at least two apart.

How to solve Continuous Subarray Sum

A subarray sum is divisible by k exactly when its two bounding prefix sums have the same remainder mod k. Store the earliest index of each remainder and require the two indices to be at least two apart.

Approach

1. Start with first = {0: -1} and a running total.
2. At each i, compute r = total % k.
3. If r was seen at j and i - j >= 2, return true; if r is new, record first[r] = i.
4. Return false.

Why it works

prefix[i] - prefix[j] ≡ 0 (mod k) iff the remainders match, and i - j is the length of the subarray (j, i]. Keeping only the first index of each remainder maximises the length available for the check.

Complexity

• Time — O(n)
• Space — O(min(n, k))

Pitfalls

• Do not overwrite an existing remainder's index — a later, closer one can hide a valid longer subarray.
• The {0: -1} seed handles a prefix that is itself a multiple of k.

Reference solution

Python

def checkSubarraySum(nums, k: int) -> bool:
    first = {0: -1}
    total = 0
    for i, x in enumerate(nums):
        total += x
        r = total % k
        if r in first:
            if i - first[r] >= 2:
                return True
        else:
            first[r] = i
    return False

Java

public static boolean checkSubarraySum(int[] nums, int k) {
    Map<Integer, Integer> firstAt = new HashMap<>();
    firstAt.put(0, -1);
    int sum = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        int r = ((sum % k) + k) % k;
        Integer seen = firstAt.get(r);
        if (seen != null) {
            if (i - seen >= 2) return true;
        } else {
            firstAt.put(r, i);
        }
    }
    return false;
}

C++

bool checkSubarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> firstAt;
    firstAt[0] = -1;
    int sum = 0;
    for (int i = 0; i < (int) nums.size(); i++) {
        sum += nums[i];
        int r = ((sum % k) + k) % k;
        if (firstAt.count(r)) {
            if (i - firstAt[r] >= 2) return true;
        } else {
            firstAt[r] = i;
        }
    }
    return false;
}

JavaScript

var checkSubarraySum = function(nums, k) {
    const firstAt = new Map();
    firstAt.set(0, -1);
    let sum = 0;
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i];
        const r = ((sum % k) + k) % k;
        if (firstAt.has(r)) {
            if (i - firstAt.get(r) >= 2) return true;
        } else {
            firstAt.set(r, i);
        }
    }
    return false;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium