Valid Subarrays With Matching Sum Digits II - Solution & Explanation

Problem Overview: You are given an array and must count subarrays where the digit sum of the subarray’s total matches a specific digit-based condition derived from the subarray boundaries. The challenge is that recomputing subarray sums and their digit sums repeatedly becomes expensive for large inputs.

Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)

Generate every possible subarray using two nested loops. For each starting index i, extend the subarray to j while maintaining a running sum. After each extension, compute the digit sum of the current subarray total and check if it satisfies the matching condition. This approach is straightforward and useful for validating logic during development. However, computing up to n(n+1)/2 subarrays makes it impractical for large inputs.

Approach 2: Prefix Sum with On‑Demand Digit Sum (O(n²) time, O(n) space)

Precompute a prefix sum array so any subarray sum can be calculated in constant time using sum(i..j) = prefix[j+1] - prefix[i]. This removes the need to accumulate sums repeatedly. You still iterate over all pairs (i, j), but each subarray sum lookup becomes O(1). The digit sum check remains the main cost. While still quadratic overall, the code is cleaner and easier to reason about than incremental accumulation.

Approach 3: Prefix Transformation + Hash Map (O(n) time, O(n) space)

The key observation is that digit sums follow a predictable modular behavior (digital root). Instead of recomputing digit sums for every subarray, transform prefix sums into their digit-root representation. When two prefixes produce compatible digit signatures, the subarray between them satisfies the matching rule. Maintain a frequency map using a hash map keyed by this transformed value. As you iterate through the array once, compute the current prefix sum, convert it to its digit-root form, and count how many previous prefixes produce a valid match. Each lookup and update is O(1).

This converts a quadratic search into a linear scan because the digit constraint can be expressed using prefix relationships rather than recomputing properties for every subarray. The approach mirrors techniques used in problems involving remainder classes, digit invariants, or prefix transformations.

Recommended for interviews: Interviewers expect the prefix-based optimization. Starting with brute force demonstrates you understand the subarray definition, but the real signal comes from recognizing that digit-sum behavior can be normalized using modular arithmetic and tracked with a hash structure. The final solution combines prefix sums and hash maps to achieve O(n) time, which scales to large inputs.