LeetCode 3883 - Count Non Decreasing Arrays With Given Digit Sums

The problem asks us to compute the number of non-decreasing arrays of integers where each integer satisfies a specific digit sum constraint.

leetcodehardarraydynamic-programmingprefix-sum

LeetCode Problem 3883

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Prefix Sum

Solution

Problem Understanding

The problem asks us to compute the number of non-decreasing arrays of integers where each integer satisfies a specific digit sum constraint. Specifically, we are given an array digitSum of length n, where digitSum[i] represents the required sum of digits for the i-th element in the array. We must construct arrays arr of length n such that each element is between 0 and 5000, the array is non-decreasing, and sum_of_digits(arr[i]) == digitSum[i]. The result should be returned modulo 10^9 + 7.

In other words, we need to:

  1. Enumerate all integers from 0 to 5000 that have a given digit sum.
  2. Form non-decreasing sequences using those integers in order.
  3. Count all possible valid sequences efficiently.

Constraints are important: n can be up to 1000, and digitSum[i] can be at most 50. This implies we cannot brute-force all arrays directly because the number of combinations could be extremely large. We must rely on dynamic programming to compute counts efficiently using precomputed sets of numbers for each digit sum.

Edge cases include:

  • digitSum[i] = 0, which corresponds only to 0.
  • digitSum[i] larger than any digit sum achievable for numbers ≤ 5000 (e.g., 49 is impossible).
  • Sequences of length 1 where multiple numbers satisfy the digit sum.

Approaches

The brute-force approach would generate all numbers from 0 to 5000, filter them by digit sum, and then attempt to construct all non-decreasing sequences of length n. While correct, this approach is infeasible because the number of sequences grows exponentially with n (up to O(5000^n)).

The key insight for an optimal solution is dynamic programming combined with counting numbers with a given digit sum. Instead of generating each array, we can:

  1. Precompute for each possible digit sum s all numbers x (0 ≤ x ≤ 5000) that satisfy sum_of_digits(x) = s.
  2. Use a dynamic programming table dp[i][j] where i is the index in digitSum and j iterates over valid numbers for that digit sum. The value represents the number of valid sequences ending with that number.
  3. Exploit the non-decreasing property by using prefix sums to efficiently compute cumulative counts for numbers less than or equal to the current number.

This reduces the time complexity from exponential to a polynomial time in terms of the number of valid numbers and n.

Approach Time Complexity Space Complexity Notes
Brute Force O(5000^n) O(1) Generate all arrays explicitly, infeasible for large n
Optimal O(n * 5001^2) O(n * 5001) Precompute numbers by digit sum and use DP with prefix sums to count non-decreasing sequences

Algorithm Walkthrough

  1. Precompute digit sums: Iterate over all numbers from 0 to 5000, computing sum_of_digits(num) and storing numbers in a dictionary keyed by their digit sum.
  2. Initialize DP table: For the first index, count all numbers that satisfy digitSum[0]. Set dp[0][num] = 1 for each valid number.
  3. Iterate through digitSum array: For each index i from 1 to n-1:

a. Retrieve all numbers that satisfy digitSum[i].

b. For each valid number x at position i, sum all DP values from dp[i-1][y] where y <= x (non-decreasing constraint). This gives the number of sequences ending with x.

c. Use a prefix sum array over the previous DP row to compute these sums efficiently. 4. Compute final answer: Sum all DP values for the last index. This represents all valid arrays of length n.

Why it works: The DP maintains the invariant that dp[i][x] stores the number of valid sequences ending with number x at position i. By summing only sequences that respect the non-decreasing condition, the algorithm correctly counts all valid arrays without enumerating them.

Python Solution

class Solution:
    MOD = 10**9 + 7

    def countArrays(self, digitSum: list[int]) -> int:
        from collections import defaultdict

        # Step 1: Precompute numbers by digit sum
        sum_to_numbers = defaultdict(list)
        for num in range(5001):
            s = sum(int(d) for d in str(num))
            sum_to_numbers[s].append(num)

        n = len(digitSum)
        if n == 0:
            return 0

        # Step 2: Initialize DP
        prev_dp = {}
        for num in sum_to_numbers.get(digitSum[0], []):
            prev_dp[num] = 1

        if not prev_dp:
            return 0

        # Step 3: DP iteration
        for i in range(1, n):
            curr_dp = {}
            numbers = sum_to_numbers.get(digitSum[i], [])
            if not numbers:
                return 0
            sorted_prev = sorted(prev_dp.keys())
            prefix = []
            total = 0
            for num in sorted_prev:
                total = (total + prev_dp[num]) % self.MOD
                prefix.append((num, total))

            for x in numbers:
                # Binary search to find sum of all prev_dp[num] where num <= x
                l, r = 0, len(prefix)-1
                idx = -1
                while l <= r:
                    m = (l + r)//2
                    if prefix[m][0] <= x:
                        idx = m
                        l = m+1
                    else:
                        r = m-1
                if idx != -1:
                    curr_dp[x] = prefix[idx][1]
            prev_dp = curr_dp

        return sum(prev_dp.values()) % self.MOD

This Python implementation first precomputes all numbers by their digit sums, then iteratively builds valid sequences using dynamic programming. Binary search with prefix sums ensures that the non-decreasing property is maintained efficiently.

Go Solution

package main

func countArrays(digitSum []int) int {
    const MOD = 1_000_000_007
    n := len(digitSum)

    // Precompute numbers by digit sum
    sumToNumbers := make([][]int, 51)
    for num := 0; num <= 5000; num++ {
        s := 0
        temp := num
        for temp > 0 {
            s += temp % 10
            temp /= 10
        }
        sumToNumbers[s] = append(sumToNumbers[s], num)
    }

    prevDP := map[int]int{}
    for _, num := range sumToNumbers[digitSum[0]] {
        prevDP[num] = 1
    }
    if len(prevDP) == 0 {
        return 0
    }

    for i := 1; i < n; i++ {
        currDP := map[int]int{}
        numbers := sumToNumbers[digitSum[i]]
        if len(numbers) == 0 {
            return 0
        }
        sortedPrev := []int{}
        for num := range prevDP {
            sortedPrev = append(sortedPrev, num)
        }
        sort.Ints(sortedPrev)
        prefix := []int{}
        total := 0
        for _, num := range sortedPrev {
            total = (total + prevDP[num]) % MOD
            prefix = append(prefix, total)
        }

        for _, x := range numbers {
            l, r, idx := 0, len(sortedPrev)-1, -1
            for l <= r {
                m := (l + r) / 2
                if sortedPrev[m] <= x {
                    idx = m
                    l = m + 1
                } else {
                    r = m - 1
                }
            }
            if idx != -1 {
                currDP[x] = prefix[idx]
            }
        }
        prevDP = currDP
    }

    ans := 0
    for _, v := range prevDP {
        ans = (ans + v) % MOD
    }
    return ans
}

Go handles maps and integer slices slightly differently. We explicitly sort keys and maintain prefix sums as a slice for efficient accumulation. The modulo operation ensures values remain bounded.

Worked Examples

Example 1: digitSum = [25,1]

Precompute valid numbers:

  • 25 → [799, 889, 898, 979, 988, 997]
  • 1 → [1, 10, 100, 1000]

DP:

i Number Count
0 799 1
0 889 1
0 898 1
0 979 1
0 988 1
0 997 1
1 1 0
1 10 0