Longest Subarray with Sum Divisible by K

🎯

Longest Subarray with Sum Divisible by K

mediumHASH_MAPAmazonGoogle

Imagine you are analyzing a sequence of daily sales and want to find the longest stretch where the total sales are divisible by a fixed number K, helping you identify periodic trends.

💡 This problem involves finding subarrays with a sum divisible by K, which can be tricky because beginners often struggle to connect prefix sums with modular arithmetic and how to efficiently track remainders using hash maps.

📋

Problem Statement

Given an integer array nums and an integer k, find the length of the longest subarray whose sum is divisible by k. Return the length of such subarray. If no such subarray exists, return 0.

1 ≤ nums.length ≤ 10^5-10^9 ≤ nums[i] ≤ 10^92 ≤ k ≤ 10^9

💡

Example

Input"nums = [2, 7, 6, 1, 4, 5], k = 3"

Output4

The subarray [7, 6, 1, 4] sums to 18, which is divisible by 3, and its length is 4, the longest possible.

Input"nums = [-2, 2, -5, 12, -11, -1, 7], k = 3"

Output5

The subarray [2, -5, 12, -11, -1] sums to -3, divisible by 3, length 5.

• All elements are zero → entire array length
• No subarray sum divisible by k → output 0
• Negative numbers in array → must handle modulo correctly
• k equals 1 → entire array length always valid

⚠️

Common Mistakes

Not handling negative prefix sums modulo correctly

Incorrect remainder values cause wrong subarray detection

✅ Add k to remainder if remainder is negative to keep it in [0, k-1]

Not initializing remainder 0 at index -1

Misses subarrays starting at index 0 that are divisible by k

✅ Initialize remainder_index[0] = -1 before iteration

Using nested loops for large input sizes

Solution times out (TLE) on large inputs

✅ Use prefix sums with hash map to achieve O(n) time

Not updating max_length correctly when remainder repeats

Returns shorter subarray length than possible

✅ Update max_length with current index minus earliest index of remainder

Using hash map without considering space complexity

Excessive memory usage if k is very large

✅ Consider array optimization if k is small or use appropriate data structures

🧠

Brute Force (Nested Loops)

💡 Starting with brute force helps understand the problem deeply by checking every possible subarray, which clarifies what we are looking for before optimizing.

Intuition

Check every subarray by summing elements and test if the sum is divisible by k, tracking the longest length found.

Algorithm

1. Initialize max_length to 0.
2. Use two nested loops to consider every subarray start and end indices.
3. Calculate the sum of elements in the current subarray.
4. If sum % k == 0, update max_length if current subarray is longer.

💡 The nested loops and sum calculation are straightforward but inefficient, which helps beginners see the problem's brute force nature.

</>

Code

def longest_subarray_div_by_k(nums, k):
    max_length = 0
    n = len(nums)
    for start in range(n):
        current_sum = 0
        for end in range(start, n):
            current_sum += nums[end]
            if current_sum % k == 0:
                max_length = max(max_length, end - start + 1)
    return max_length

# Driver code
if __name__ == '__main__':
    print(longest_subarray_div_by_k([2,7,6,1,4,5], 3))  # Output: 4

Line Notes

max_length = 0Initialize to track the longest valid subarray length found so far

for start in range(n)Outer loop picks the start index of subarray

current_sum += nums[end]Accumulate sum for current subarray ending at 'end'

if current_sum % k == 0Check if current subarray sum is divisible by k

public class Solution {
    public static int longestSubarrayDivByK(int[] nums, int k) {
        int maxLength = 0;
        int n = nums.length;
        for (int start = 0; start < n; start++) {
            int currentSum = 0;
            for (int end = start; end < n; end++) {
                currentSum += nums[end];
                if (currentSum % k == 0) {
                    maxLength = Math.max(maxLength, end - start + 1);
                }
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        System.out.println(longestSubarrayDivByK(new int[]{2,7,6,1,4,5}, 3)); // 4
    }
}

Line Notes

int maxLength = 0;Track longest subarray length found

for (int start = 0; start < n; start++)Outer loop selects subarray start

currentSum += nums[end];Add current element to running sum

if (currentSum % k == 0)Check divisibility condition

#include <iostream>
#include <vector>
using namespace std;

int longestSubarrayDivByK(vector<int>& nums, int k) {
    int maxLength = 0;
    int n = nums.size();
    for (int start = 0; start < n; start++) {
        int currentSum = 0;
        for (int end = start; end < n; end++) {
            currentSum += nums[end];
            if (currentSum % k == 0) {
                maxLength = max(maxLength, end - start + 1);
            }
        }
    }
    return maxLength;
}

int main() {
    vector<int> nums = {2,7,6,1,4,5};
    cout << longestSubarrayDivByK(nums, 3) << endl; // 4
    return 0;
}

Line Notes

int maxLength = 0;Initialize max length tracker

for (int start = 0; start < n; start++)Outer loop for subarray start

currentSum += nums[end];Accumulate sum for current subarray

if (currentSum % k == 0)Check if sum divisible by k

function longestSubarrayDivByK(nums, k) {
    let maxLength = 0;
    const n = nums.length;
    for (let start = 0; start < n; start++) {
        let currentSum = 0;
        for (let end = start; end < n; end++) {
            currentSum += nums[end];
            if (currentSum % k === 0) {
                maxLength = Math.max(maxLength, end - start + 1);
            }
        }
    }
    return maxLength;
}

// Test
console.log(longestSubarrayDivByK([2,7,6,1,4,5], 3)); // 4

Line Notes

let maxLength = 0;Initialize variable to track longest subarray length

for (let start = 0; start < n; start++)Outer loop selects subarray start index

currentSum += nums[end];Add current element to running sum

if (currentSum % k === 0)Check if current sum divisible by k

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Two nested loops each up to n, summing subarrays in O(1) per addition, total O(n^2).

💡 For n=20, this means about 400 operations, which is okay, but for n=100000 it becomes 10 billion operations, too slow.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem and motivate better solutions.

🧠

Prefix Sum + Hash Map (First Seen Remainder)

💡 This approach uses prefix sums and modular arithmetic to reduce time complexity by remembering the earliest index where a particular remainder was seen, enabling quick subarray length calculation.

Intuition

If two prefix sums have the same remainder when divided by k, the subarray between them sums to a multiple of k.

Algorithm

1. Initialize a hash map to store remainder to earliest index mapping, starting with remainder 0 at index -1.
2. Iterate through the array, computing prefix sum and its remainder modulo k.
3. If remainder seen before, update max_length with distance between current index and earliest index of this remainder.
4. If remainder not seen, store current index as earliest occurrence.

💡 The key insight is that same remainder prefix sums indicate divisible subarrays, and storing earliest indices helps find longest subarray.

</>

Code

def longest_subarray_div_by_k(nums, k):
    remainder_index = {0: -1}
    max_length = 0
    prefix_sum = 0
    for i, num in enumerate(nums):
        prefix_sum += num
        remainder = prefix_sum % k
        if remainder < 0:
            remainder += k
        if remainder in remainder_index:
            max_length = max(max_length, i - remainder_index[remainder])
        else:
            remainder_index[remainder] = i
    return max_length

# Driver code
if __name__ == '__main__':
    print(longest_subarray_div_by_k([2,7,6,1,4,5], 3))  # Output: 4

Line Notes

remainder_index = {0: -1}Store remainder 0 at index -1 to handle subarrays starting at index 0

prefix_sum += numAccumulate prefix sum as we iterate

remainder = prefix_sum % kCalculate remainder to detect divisible subarrays

if remainder in remainder_indexIf remainder seen before, subarray between indices is divisible

import java.util.*;

public class Solution {
    public static int longestSubarrayDivByK(int[] nums, int k) {
        Map<Integer, Integer> remainderIndex = new HashMap<>();
        remainderIndex.put(0, -1);
        int maxLength = 0, prefixSum = 0;
        for (int i = 0; i < nums.length; i++) {
            prefixSum += nums[i];
            int remainder = prefixSum % k;
            if (remainder < 0) remainder += k;
            if (remainderIndex.containsKey(remainder)) {
                maxLength = Math.max(maxLength, i - remainderIndex.get(remainder));
            } else {
                remainderIndex.put(remainder, i);
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        System.out.println(longestSubarrayDivByK(new int[]{2,7,6,1,4,5}, 3)); // 4
    }
}

Line Notes

remainderIndex.put(0, -1);Initialize remainder 0 at index -1 for subarrays starting at 0

prefixSum += nums[i];Accumulate prefix sum as we iterate

int remainder = prefixSum % k;Calculate remainder for divisibility check

if (remainderIndex.containsKey(remainder))Check if remainder seen before to find divisible subarray

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int longestSubarrayDivByK(vector<int>& nums, int k) {
    unordered_map<int, int> remainderIndex;
    remainderIndex[0] = -1;
    int maxLength = 0, prefixSum = 0;
    for (int i = 0; i < nums.size(); i++) {
        prefixSum += nums[i];
        int remainder = prefixSum % k;
        if (remainder < 0) remainder += k;
        if (remainderIndex.find(remainder) != remainderIndex.end()) {
            maxLength = max(maxLength, i - remainderIndex[remainder]);
        } else {
            remainderIndex[remainder] = i;
        }
    }
    return maxLength;
}

int main() {
    vector<int> nums = {2,7,6,1,4,5};
    cout << longestSubarrayDivByK(nums, 3) << endl; // 4
    return 0;
}

Line Notes

remainderIndex[0] = -1;Store remainder 0 at index -1 to handle subarrays from start

prefixSum += nums[i];Update prefix sum with current element

int remainder = prefixSum % k;Compute remainder for divisibility

if (remainderIndex.find(remainder) != remainderIndex.end())Check if remainder seen before to update max length

function longestSubarrayDivByK(nums, k) {
    const remainderIndex = new Map();
    remainderIndex.set(0, -1);
    let maxLength = 0, prefixSum = 0;
    for (let i = 0; i < nums.length; i++) {
        prefixSum += nums[i];
        let remainder = prefixSum % k;
        if (remainder < 0) remainder += k;
        if (remainderIndex.has(remainder)) {
            maxLength = Math.max(maxLength, i - remainderIndex.get(remainder));
        } else {
            remainderIndex.set(remainder, i);
        }
    }
    return maxLength;
}

// Test
console.log(longestSubarrayDivByK([2,7,6,1,4,5], 3)); // 4

Line Notes

remainderIndex.set(0, -1);Initialize remainder 0 at index -1 for subarrays starting at 0

prefixSum += nums[i];Accumulate prefix sum as we iterate

let remainder = prefixSum % k;Calculate remainder for divisibility check

if (remainderIndex.has(remainder))If remainder seen before, update max length

⏱

Complexity

TimeO(n)

SpaceO(k) or O(n) in worst case

Single pass through array with constant time hash map operations, total O(n).

💡 For n=100000, this means about 100000 operations, which is efficient and scalable.

Interview Verdict: Accepted

This approach is optimal and accepted in interviews, demonstrating mastery of prefix sums and hash maps.

🧠

Prefix Sum + Hash Map with Space Optimization (Using Array for Small k)

💡 When k is small, we can replace the hash map with a fixed-size array to store earliest indices, reducing overhead and improving speed.

Intuition

Since remainder values range from 0 to k-1, an array indexed by remainder can store earliest occurrence, avoiding hash map overhead.

Algorithm

1. Initialize an array of size k with -2 (indicating unseen), set index for remainder 0 to -1.
2. Iterate through nums, compute prefix sum and remainder modulo k.
3. If remainder seen before (array value != -2), update max_length with distance.
4. Else store current index as earliest occurrence for this remainder.

💡 This approach is similar to the previous but uses an array for O(1) remainder lookups when k is small.

</>

Code

def longest_subarray_div_by_k(nums, k):
    earliest = [-2] * k
    earliest[0] = -1
    max_length = 0
    prefix_sum = 0
    for i, num in enumerate(nums):
        prefix_sum += num
        remainder = prefix_sum % k
        if remainder < 0:
            remainder += k
        if earliest[remainder] != -2:
            max_length = max(max_length, i - earliest[remainder])
        else:
            earliest[remainder] = i
    return max_length

# Driver code
if __name__ == '__main__':
    print(longest_subarray_div_by_k([2,7,6,1,4,5], 3))  # Output: 4

Line Notes

earliest = [-2] * kInitialize array with sentinel -2 to mark unseen remainders

earliest[0] = -1Set remainder 0 earliest index to -1 for subarrays starting at 0

if earliest[remainder] != -2Check if remainder seen before using array

earliest[remainder] = iStore earliest index for this remainder

public class Solution {
    public static int longestSubarrayDivByK(int[] nums, int k) {
        int[] earliest = new int[k];
        Arrays.fill(earliest, -2);
        earliest[0] = -1;
        int maxLength = 0, prefixSum = 0;
        for (int i = 0; i < nums.length; i++) {
            prefixSum += nums[i];
            int remainder = prefixSum % k;
            if (remainder < 0) remainder += k;
            if (earliest[remainder] != -2) {
                maxLength = Math.max(maxLength, i - earliest[remainder]);
            } else {
                earliest[remainder] = i;
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        System.out.println(longestSubarrayDivByK(new int[]{2,7,6,1,4,5}, 3)); // 4
    }
}

Line Notes

Arrays.fill(earliest, -2);Fill array with sentinel to mark unseen remainders

earliest[0] = -1;Initialize remainder 0 earliest index for subarrays from start

if (earliest[remainder] != -2)Check if remainder seen before using array

earliest[remainder] = i;Store earliest index for remainder

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int longestSubarrayDivByK(vector<int>& nums, int k) {
    vector<int> earliest(k, -2);
    earliest[0] = -1;
    int maxLength = 0, prefixSum = 0;
    for (int i = 0; i < nums.size(); i++) {
        prefixSum += nums[i];
        int remainder = prefixSum % k;
        if (remainder < 0) remainder += k;
        if (earliest[remainder] != -2) {
            maxLength = max(maxLength, i - earliest[remainder]);
        } else {
            earliest[remainder] = i;
        }
    }
    return maxLength;
}

int main() {
    vector<int> nums = {2,7,6,1,4,5};
    cout << longestSubarrayDivByK(nums, 3) << endl; // 4
    return 0;
}

Line Notes

vector<int> earliest(k, -2);Initialize vector with sentinel -2 for unseen remainders

earliest[0] = -1;Set remainder 0 earliest index for subarrays starting at 0

if (earliest[remainder] != -2)Check if remainder previously seen

earliest[remainder] = i;Record earliest index for this remainder

function longestSubarrayDivByK(nums, k) {
    const earliest = new Array(k).fill(-2);
    earliest[0] = -1;
    let maxLength = 0, prefixSum = 0;
    for (let i = 0; i < nums.length; i++) {
        prefixSum += nums[i];
        let remainder = prefixSum % k;
        if (remainder < 0) remainder += k;
        if (earliest[remainder] !== -2) {
            maxLength = Math.max(maxLength, i - earliest[remainder]);
        } else {
            earliest[remainder] = i;
        }
    }
    return maxLength;
}

// Test
console.log(longestSubarrayDivByK([2,7,6,1,4,5], 3)); // 4

Line Notes

const earliest = new Array(k).fill(-2);Initialize array with sentinel to mark unseen remainders

earliest[0] = -1;Set remainder 0 earliest index for subarrays from start

if (earliest[remainder] !== -2)Check if remainder seen before using array

earliest[remainder] = i;Store earliest index for this remainder

⏱

Complexity

TimeO(n)

SpaceO(k)

Single pass with O(1) remainder lookups using fixed array, efficient for small k.

💡 For k=1000 and n=100000, this is very fast and uses predictable memory.

Interview Verdict: Accepted

This is a practical optimization when k is small, showing attention to detail and performance.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, the prefix sum + hash map approach is the best to implement due to its optimal time and space balance.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	Yes	Mention only - never code due to inefficiency
2. Prefix Sum + Hash Map	O(n)	O(n) in worst case	No	Yes	Code this as optimal solution
3. Prefix Sum + Array Optimization	O(n)	O(k)	No	Yes	Mention if k is small, code if asked for optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and learn how to communicate your thought process clearly during interviews.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force approach to show understanding.Discuss inefficiencies and motivate prefix sum + hash map solution.Implement the optimal solution carefully handling negative numbers.Test with edge cases and discuss possible follow-ups.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of prefix sums, modular arithmetic, hash map usage, and your ability to optimize from brute force to efficient solutions.

Common Follow-ups

• What if k is negative or zero? → Handle modulo carefully or clarify constraints.
• Can you find the actual subarray, not just length? → Store start/end indices during iteration.

💡 Follow-ups test your ability to adapt the solution to variations and extract more information from your algorithm.

🔍

Pattern Recognition

When to Use

1) Asked for subarray with sum divisible by k, 2) Need longest length, 3) Large input size, 4) Hint or tag about prefix sums or hash maps.

Signature Phrases

'sum divisible by k''longest subarray with sum % k == 0'

NOT This Pattern When

Problems asking for maximum sum subarray (Kadane's algorithm) or fixed window size problems are different patterns.

Similar Problems

Subarray Sum Equals K - similar prefix sum and hash map technique for exact sumMaximum Size Subarray Sum Equals k - same pattern with sum equals k instead of divisibleLongest Substring Without Repeating Characters - uses hash map to track indices for length maximization

Practice

1. You are given an integer array and a target sum k. You need to find the number of continuous subarrays whose sum equals k. Which approach guarantees an optimal solution with linear time complexity?

easy

A. Use a sliding window technique to expand and shrink the window until the sum matches k.

B. Use nested loops to check all subarrays and sum their elements to count matches.

C. Use dynamic programming to store sums of all subarrays and count those equal to k.

D. Use prefix sums combined with a hash map to track frequencies of prefix sums and count valid subarrays in one pass.

Solution

1. Step 1: Understand the problem constraints

   The problem requires counting continuous subarrays summing to k efficiently.

2. Step 2: Evaluate approaches

   Sliding window (A) fails with negative numbers. Nested loops (D) are correct but O(n²). DP (C) is inefficient here. Prefix sum + hash map (B) tracks prefix sums and counts in O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Prefix sums + hash map is the classic O(n) solution [OK]

Hint: Prefix sums + hash map handles negatives and counts efficiently [OK]

Common Mistakes:

• Assuming sliding window works with negative numbers
• Confusing DP with prefix sums
• Using nested loops for optimality

2. What is the time complexity of the optimal prefix sum + hash map solution for counting subarrays summing to k in an array of length n?

medium

A. O(n log n) due to hash map lookups

B. O(n) because each element is processed once with O(1) average hash map operations

C. O(n²) because prefix sums require nested loops to check subarrays

D. O(n) for prefix sums plus O(n) for nested loops, total O(n²)

Solution

1. Step 1: Identify loops and operations

   The algorithm iterates over the array once (O(n)) and performs constant-time hash map operations on average.

2. Step 2: Analyze hash map operations

   Hash map lookups and inserts are O(1) average, so total time is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with O(1) map ops -> O(n) time [OK]

Hint: Hash map average O(1) lookups keep complexity linear [OK]

Common Mistakes:

• Assuming hash map lookups are O(log n)
• Confusing prefix sums with nested loops
• Counting nested loops inside prefix sums

3. Suppose the problem changes: now you want to detect if any number appears at least twice, but the array is extremely large and cannot fit into memory. Which approach is best suited to handle this scenario?

hard

A. Sort the array externally (external sort) and then scan for duplicates in a streaming fashion.

B. Use a hash set in memory as before, but process the array in chunks and merge results.

C. Use a bloom filter to probabilistically detect duplicates with limited memory.

D. Use nested loops on the entire array since it requires no extra space.

Solution

1. Step 1: Understand memory constraints

   The array is too large to fit in memory, so hash sets or sorting in memory are infeasible.

2. Step 2: Evaluate options

   External sorting is possible and practical for large data sets that cannot fit into memory. Bloom filters provide probabilistic detection but can yield false positives, which may not be acceptable depending on requirements. Nested loops are impractical due to O(n²) time complexity.

3. Step 3: Choose external sorting

   External sorting allows sorting data on disk and then scanning sequentially for duplicates, which is efficient and exact.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   External sorting handles large data sets with limited memory and provides exact duplicate detection [OK]

Hint: External sorting enables exact duplicate detection on large data sets [OK]

Common Mistakes:

• Assuming hash sets can handle huge data
• Ignoring external sorting costs
• Choosing nested loops despite inefficiency
• Overlooking bloom filter false positives

4. Suppose the problem is modified so that the array can contain negative numbers and k can be zero. Which modification to the prefix sum + hash map approach correctly handles this variant?

hard

A. Use prefix sums without modulo and store sums in a hash map to detect repeated sums for k=0

B. Normalize k to positive and use modulo as usual, ignoring zero k case

C. Skip modulo operations entirely and check if any subarray sum equals zero when k=0

D. Replace hash map with a balanced tree to handle negative sums and zero k

Solution

1. Step 1: Understand that modulo by zero is undefined

   When k=0, modulo operations cannot be used; must check sums equal zero directly.

2. Step 2: Use prefix sums and hash map of sums (not modulo) to detect repeated sums indicating zero-sum subarray

   This approach correctly handles negative numbers and zero k.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Detect repeated prefix sums for zero k to find zero-sum subarrays [OK]

Hint: For k=0, detect repeated prefix sums without modulo [OK]

Common Mistakes:

• Applying modulo when k=0 causing errors
• Ignoring negative numbers in modulo computations
• Using data structures that don't support negative sums efficiently

5. Suppose the input array can contain duplicate numbers and you want to find the longest consecutive sequence length allowing repeated elements to be counted only once. Which modification to the optimal hash set approach correctly handles duplicates without inflating the sequence length?

hard

A. Sort the array and count consecutive numbers, skipping duplicates during the scan.

B. Use the hash set approach but iterate over the original array instead of the set.

C. Use a hash map to count frequencies and multiply sequence length by frequency.

D. Use the hash set approach as is, since duplicates are automatically ignored by the set.

Solution

1. Step 1: Understand duplicate impact

   Duplicates can inflate counts if not handled properly.

2. Step 2: Evaluate modifications

   Iterating over original array or multiplying by frequency inflates length. Using set alone ignores duplicates but does not handle sorted consecutive counting with duplicates properly.

3. Step 3: Correct approach

   Sorting and skipping duplicates during linear scan correctly counts longest consecutive sequence without inflating length.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Sorting + skipping duplicates ensures correct consecutive count [OK]

Hint: Sorting + skip duplicates handles repeated elements correctly [OK]

Common Mistakes:

• Iterating over original array causing duplicates counted multiple times
• Multiplying length by frequency inflates result
• Assuming set alone handles duplicates correctly