Valid Subarrays With Matching Sum Digits I - Solution & Explanation

Problem Overview: Given an array of integers, count the number of contiguous subarrays where the digit sum of the first element is equal to the digit sum of the last element. A digit sum is computed by repeatedly adding the digits of a number (for example, 123 → 1+2+3 = 6).

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

Compute the digit sum for each number when needed. For every starting index i, expand the subarray to the right using j. Compare the digit sum of nums[i] and nums[j]. If they match, the subarray [i, j] is valid and contributes to the count. This checks every possible subarray, resulting in O(n²) comparisons. Space usage stays constant since only counters and temporary digit-sum calculations are used. This approach is straightforward and useful for validating correctness before optimizing.

Approach 2: Digit Sum + Hash Map Frequency (O(n) time, O(n) space)

First compute the digit sum for each element. Now the problem becomes counting pairs of indices (i, j) with i ≤ j where the digit sum values are equal. Traverse the array once and maintain a frequency map keyed by digit sum. When you see a digit sum d, every previous occurrence of d forms a valid subarray ending at the current index. Add freq[d] to the answer, then increment the stored frequency. Each element is processed once with constant-time hash lookups, producing O(n) time complexity. This technique mirrors common counting patterns used in hash table problems and prefix-based frequency counting.

The optimization works because only the endpoints matter. Intermediate elements inside the subarray do not affect the validity condition. Once the array is transformed into digit sums, the task reduces to counting equal values across positions.

Recommended for interviews: Start by explaining the O(n²) brute force to show you understand the subarray definition and the digit-sum condition. Then reduce the problem by precomputing digit sums and counting equal endpoints with a frequency map. Interviewers typically expect the O(n) hash-map approach since it demonstrates pattern recognition related to arrays and hash maps while minimizing unnecessary comparisons.