974. Subarray Sums Divisible by K - LeetCode Fastest Solution

Feb 66 min read

Hello Code Recipian! Ready to push your coding prowess to the next level? Today's question: Subarray Sums Divisible by K—a great challenge to put your coding skills to work!

This challenge is part of our LeetCode problem solutions series, so don't forget to check out more once you've cracked this one.

Let's jump in and solve this together!

Problem Statement: 974. Subarray Sums Divisible by K

Given an array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k.

A subarray is a contiguous part of an array.

Example 1

Input: nums = [4, 5, 0, -2, -3, 1], k = 5

Output: 7

Justification: There are 7 subarrays whose sum is divisible by k = 5: [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3].

Example 2

Input: nums = [7], k = 2

Output: 0

Constraints

1 <= nums.length <= 3 * 10^4
-10^4 <= nums[i] <= 10^4
2 <= k <= 10^4

Solution: 974. Subarray Sums Divisible by K

Before attempting this problem, make sure you have already solved the Subarray Sum Equals K problem. If you haven't, please do so first and then return to this one. This problem is a more advanced variation, and without the basics set, you will have a hard time understanding this.

Brute force approach: As discussed in Subarray Sum Equals K, a simple and straight forward way to solve this problem is by using the brute force approach. This involves employing two nested loops to generate all possible subarrays for the given nums array and counting those whose sum equals k. However, due to the use of nested loops, this solution has a time complexity of O(n²), making it inefficient.

Sliding window technique cannot be applied here, for the same reasons outlined in Subarray Sum Equals K.

Prefix Sum Approach: We will be using the prefix sum approach here as well, as it provides an efficient way to solve this problem. If you recall, the brute force method generates and counts subarrays that start at a particular index. However, the prefix sum approach takes the opposite perspective—it counts the subarrays that end at a particular index.

If you think about it, iterating from left to right and counting subarrays starting at a given index can be challenging since we don't know in advance how many subarrays will satisfy the condition. However, if we instead consider how many subarrays end at a particular index (i.e., the current index), the problem becomes much simpler because we have already processed the elements to the left.

If this seems unclear, don't worry—it will make sense once we walk through an example. Consider the given input: nums = [4, 5, 0, -2, -3, 1] and k = 5

Let's start with the first element, 4 (at index 0).

The only possible subarray is [4].
Check if its sum is divisible by k:
- 4 % 5 = 4 (not divisible).

💡 Note: A number x is divisible by y, only if x % y = 0.

Now, moving to the next element, 5 (at index 1), the possible subarrays ending here are:

[4, 5] → Sum = 9, and 9 % 5 = 4 (not divisible).
[5] → Sum = 5, and 5 % 5 = 0 (divisible ✅).

Since [5] is divisible by k, we add 1 to our result.

Continuing to index 2 (element 0), the possible subarrays ending here are:

[4, 5, 0] → Sum = 9, and 9 % 5 = 4 (not divisible).
5, 0] → Sum = 5, and 5 % 5 = 0 (divisible ✅).
[0] → Sum = 0, and 0 % 5 = 0 (divisible ✅).

Since two subarrays satisfy the condition, we add 2 more to our result.

Identifying a Pattern:

Now, let's analyze the pattern behind this approach. At index 2, the prefix sum is 9, and 9 % 5 = 4. For a subarray ending at this index to be divisible by k, there must be a previous subarray whose remainder is also 4.

The diagram below illustrates how we determine if the subarray [5, 0] (ending at index 2) is divisible by k=5:

Now let's analyze the above calculation and build a pattern out of it. If you notice, at a particular index, as an example let's consider index 2, the prefix sum at index 2 is equal to 9, and 9%5 = 4, so in order for a subarray ending at this index to be divisible by k, i.e. to get a remainder 0, there must be a subarray before this index whose remainder is equal to 4.

Diagram showing how the remainders are calculated for subarray 1 — Diagram showing the prefix sum and remainder calculations for subarray [5, 0]

From the above analysis we can conclude that a subarray ending at a particular index is divisible by k if:

currentSum % k - previouslySeenSum % k = subarraySum % k = 0

currentSum % k = previouslySeenSum % k

Storing Previously Seen Remainders:

This algorithm keeps track of remainders encountered in previous iterations, along with their frequencies. To enable quick lookups and avoid quadratic time complexity, these remainders are stored in a hashmap, seenRemainders.

Additionally, the hashmap is initialized with {0:1} to handle cases where the prefix sum exactly divisible by k upon first occurrence. Without this initialization, such cases would be missed, leading to incorrect results.

Normalizing Negative Remainders:

The algorithm relies on tracking prefix sum remainders to count subarrays whose sum is divisible by k. However, if the remainders are negative and not normalized, the approach breaks down. Here's why:

Consider nums = [-3, -7] and k = 5.

At index 1, currentSum % k → -10 % 5 = 0.
And previouslySeenSum % k → -3.

Since currentSum % k does not match previouslySeenSum % k the algorithm incorrectly concludes that there is no valid subarray, when in reality, the subarray [-3, -7] is divisible by k.

We can normalize negative remainders using the formula:

remainder := ((prefixSum % k) + k) % k

This formula ensures all remainders fall within the valid range [0, k-1] ensuring consistency in hashmap lookups.

Now let's revisit the previous example using this formula:

At index 1, currentSum % k → ((-10 % 5) + 5) % 5 = 0.
And previouslySeenSum % k → ((-3 % 5) + 5) % 5 = 2.

Since the seenRemainders hashmap is initialized with {0:1}, the algorithm correctly identifies a valid subarray and returns a count of 1.

Let's now discuss how to implement this approach.

Algorithm

Below is a step-by-step breakdown of how the algorithm works:

Initialization:
1. Create a hashmap seenRemainders, to track prefix sum remainders encountered in previous iterations.
2. Initialize seenRemainders with {0:1} to handle edge cases where the current remainder is exactly k.
3. Define two variables:
  1. prefixSum → Stores the cumulative sum.
  2. subarrayCount → Stores the final count of valid subarrays.
Count subarrays divisible by k: Iterate through the nums array and perform the following steps for each element:
1. Update the prefixSum by adding the current number.
2. Normalize the remainder to handle negative values using the formula: remainder := ((prefixSum % k) + k) % k
3. Check if the remainder exists in seenRemainders hashmap:
  1. If it exists, add its frequency to subarrayCount.
  2. If not, continue to next step.
4. Increment the frequency of the current remainder in seenRemainders.
Repeat steps a to d for every number in nums.
Return the final result: Return subarrayCount as the final count of subarrays divisible by k.

Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses:

Simulation

Here’s a visual representation of how the algorithm works:

Code

Go Solution

Python Solution

Java Solution

JavaScript Solution

TypeScript Solution

C++ Solution

C# Solution

C Solution

PHP Solution

Kotlin Solution

Swift Solution

Ruby Solution

Scala Solution

Rust Solution

Dart Solution

Racket Solution

Complexity Analysis

Time Complexity

The algorithm processes the nums array in a single pass, resulting in a time complexity of O(n).

Space Complexity

The algorithm uses a hashmap seenRemainders to store prefix sum remainders. In the worst case, where all remainders are unique, that hashmap will store upto n elements. Therefore, the space complexity is also O(n).

Want to master the Prefix Sum pattern? Take your skills to the next level with these must-read articles:

Dive in now and take your coding game to the next level!

⚡ FREE Premium Access—Only for a Short Time! ⚡ Love coding? Get expert tutorials, pro tips, and exclusive resources—100% FREE! For a limited time, enjoy full access to Code Recipe Membership at no cost. Don’t wait—grab this deal before time runs out! ⏳ Sign up now!