3969. Valid Subarrays With Matching Sum Digits I - Solution

Q: Is Valid Subarrays With Matching Sum Digits I easy or hard?

The problem is rated Medium because the brute force idea is simple but recognizing the frequency-counting optimization requires pattern recognition. Once you reduce the condition to matching digit sums at the endpoints, the optimal O(n) hash map solution becomes straightforward.

Q: Valid Subarrays With Matching Sum Digits I Python/Java solution

The implementation typically computes digit sums with a helper function, then iterates through the array while maintaining a hash map of frequencies. Python uses a dictionary or collections.Counter, Java uses HashMap , and C++ uses unordered_map for O(1) average lookup.

The problem

You are given an integer array nums and an integer digit x.

A subarray nums[l..r] is considered valid if the sum of its elements satisfies both of the following conditions:

The first digit of the sum is equal to x.
The last digit of the sum is equal to x.

Return the number of valid subarrays.

Example 1:

Input: nums = [1,100,1], x = 1

Output: 4

Explanation:

The valid subarrays are:

nums[0..0]: sum = 1
nums[0..1]: sum = 1 + 100 = 101
nums[1..2]: sum = 100 + 1 = 101
nums[2..2]: sum = 1

Thus, the answer is 4.

Example 2:

Input: nums = [1], x = 2

Output: 0

Explanation:

The only subarray is nums[0..0] with a sum of 1, which does not satisfy the conditions.

Thus, the answer is 0.

Constraints:

1 <= nums.length <= 1500
1 <= nums[i] <= 10⁹
1 <= x <= 9

Approach overview

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.

Solution

We can enumerate the left endpoint l of the subarray, and for each l, we enumerate the right endpoint r in the range [l, n), and calculate the sum of nums[l..r]. If it satisfies the conditions, the answer is increased by one.

The time complexity is O(n^2), and the space complexity is O(1). Here, n is the length of the array nums.

Python

class Solution:
    def countValidSubarrays(self, nums: list[int], x: int) -> int:
        n = len(nums)
        ans = 0
        for l in range(n):
            s = 0
            for r in range(l, n):
                s += nums[r]
                if s % 10 == x and int(str(s)[0]) == x:
                    ans += 1
        return ans

Java

class Solution {
    public int countValidSubarrays(int[] nums, int x) {
        int n = nums.length;
        int ans = 0;

        for (int l = 0; l < n; l++) {
            long s = 0;
            for (int r = l; r < n; r++) {
                s += nums[r];
                if (s % 10 == x && Long.toString(s).charAt(0) - '0' == x) {
                    ans++;
                }
            }
        }

        return ans;
    }
}

C++

class Solution {
public:
    int countValidSubarrays(vector<int>& nums, int x) {
        int n = nums.size();
        int ans = 0;

        for (int l = 0; l < n; ++l) {
            long long s = 0;
            for (int r = l; r < n; ++r) {
                s += nums[r];
                if (s % 10 == x && to_string(s)[0] - '0' == x) {
                    ++ans;
                }
            }
        }

        return ans;
    }
};

TypeScript

function countValidSubarrays(nums: number[], x: number): number {
    const n = nums.length;
    let ans = 0;

    for (let l = 0; l < n; l++) {
        let s = 0;

        for (let r = l; r < n; r++) {
            s += nums[r];

            if (s % 10 === x && Number(s.toString()[0]) === x) {
                ans++;
            }
        }
    }

    return ans;
}

func countValidSubarrays(nums []int, x int) (ans int) {
    n := len(nums)

	for l := 0; l < n; l++ {
		var s int64
		for r := l; r < n; r++ {
			s += int64(nums[r])
			if s%10 == int64(x) && int(strconv.FormatInt(s, 10)[0]-'0') == x {
				ans++
			}
		}
	}

	return
}

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Subarray Enumeration	O(n²)	O(1)	Small arrays or verifying correctness before optimization
Digit Sum + Hash Map Frequency	O(n)	O(n)	General case; optimal for large inputs with fast hash lookups

Frequently asked questions

Is Valid Subarrays With Matching Sum Digits I easy or hard?

The problem is rated Medium because the brute force idea is simple but recognizing the frequency-counting optimization requires pattern recognition. Once you reduce the condition to matching digit sums at the endpoints, the optimal O(n) hash map solution becomes straightforward.

Valid Subarrays With Matching Sum Digits I Python/Java solution

The implementation typically computes digit sums with a helper function, then iterates through the array while maintaining a hash map of frequencies. Python uses a dictionary or collections.Counter, Java uses HashMap<Integer, Integer>, and C++ uses unordered_map for O(1) average lookup.

How to solve Valid Subarrays With Matching Sum Digits I in O(n)?

Precompute the digit sum of each element. Traverse the array and maintain a hash map where the key is the digit sum and the value is the number of times it has appeared so far. For the current element with digit sum d, add freq[d] to the answer and then increment freq[d]. This counts all subarrays ending at the current index whose endpoints share the same digit sum.

What is the best approach for Valid Subarrays With Matching Sum Digits I?

The most efficient approach converts every number into its digit sum and counts how often each digit sum appears. Using a hash map, every time the same digit sum appears again it forms new valid subarrays with previous occurrences. This reduces the problem to a frequency counting pattern and runs in O(n) time with O(n) extra space.

Is Valid Subarrays With Matching Sum Digits I asked at Google/Amazon/Meta?

Problems using digit manipulation and hash-map frequency counting appear frequently in interviews at companies like Amazon, Google, and Meta. While the exact question may vary, the pattern of transforming values and counting equal pairs or endpoints is common in coding interviews.

What data structure is used in Valid Subarrays With Matching Sum Digits I?

A hash map (dictionary) is the primary data structure. It stores frequencies of digit sums encountered so far. This allows constant-time lookups to determine how many valid subarrays can end at the current index.

What is the time complexity of Valid Subarrays With Matching Sum Digits I?

The optimal solution runs in O(n) time. Each element is processed once to compute its digit sum and update a hash map storing frequencies of previously seen digit sums. The brute force approach checks every subarray and takes O(n^2) time.

Valid Subarrays With Matching Sum Digits I solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Valid Subarrays With Matching Sum Digits I solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems