3753. Total Waviness of Numbers in Range II

Digit DP
Dynamic Programming
Math

TIME

O(D 10 11 11 10)

SPACE

O(D 11 11)

Intuition

The range can go up to 10^15, so scanning every number is impossible.

Instead, count the total waviness for all numbers from 0 to limit with digit DP. Then:

answer = count(num2) - count(num1 - 1)

When building a number from left to right, a digit can only be classified as a peak or valley after its right neighbor is known. So the DP keeps the last two significant digits. When a new digit is appended, the previous digit becomes an internal digit with both neighbors known.

State

dp(position, tight, started, previousPreviousDigit, previousDigit) returns:

how many numbers can be formed from this state
the total waviness contributed by all those numbers

previousPreviousDigit = -1 means only one significant digit has been placed so far.

Transition

For each possible next digit:

If the number has not started and the digit is 0, keep skipping leading zeros.
If this is the first significant digit, store it as previousDigit.
If there is only one previous significant digit, store the pair.
Otherwise, check whether previousDigit is a peak or valley using:
```
previousPreviousDigit, previousDigit, currentDigit
```
Add that contribution for every number formed by the suffix.

At the end of the digits, return one formed number with no additional contribution. The last digit is never counted because it never becomes internal.

Complexity

Let D be the number of digits in limit.

Time: O(D * 10 * 11 * 11 * 10)
Space: O(D * 11 * 11) for memoization

Since num2 <= 10^15, D is at most 16.

Edge Cases

Numbers with fewer than 3 digits -> no digit ever has both neighbors, so contribution is 0
Equal neighboring digits -> strict peak and valley comparisons fail
Leading zeros -> ignored until the first non-zero digit
Single-number range -> handled by prefix subtraction

Code

from functools import lru_cache
from typing import Tuple


class Solution:
    def totalWaviness(self, num1: int, num2: int) -> int:
        """
        3753. Total Waviness of Numbers in Range II
        Time: O(D * 10 * 11 * 11 * 10)
        Space: O(D * 11 * 11)
        """
        return self._count_up_to(num2) - self._count_up_to(num1 - 1)

    def _count_up_to(self, limit: int) -> int:
        if limit <= 0:
            return 0

        digits = list(map(int, str(limit)))

        @lru_cache(None)
        def dp(
            position: int,
            tight: bool,
            started: bool,
            previous_previous_digit: int,
            previous_digit: int,
        ) -> Tuple[int, int]:
            if position == len(digits):
                return 1, 0

            upper_bound = digits[position] if tight else 9
            total_numbers = 0
            total_waviness = 0

            for digit in range(upper_bound + 1):
                next_tight = tight and digit == upper_bound

                if not started and digit == 0:
                    count, waviness = dp(position + 1, next_tight, False, -1, -1)
                    total_numbers += count
                    total_waviness += waviness
                    continue

                if not started:
                    count, waviness = dp(position + 1, next_tight, True, -1, digit)
                    total_numbers += count
                    total_waviness += waviness
                    continue

                if previous_previous_digit == -1:
                    count, waviness = dp(
                        position + 1,
                        next_tight,
                        True,
                        previous_digit,
                        digit,
                    )
                    total_numbers += count
                    total_waviness += waviness
                    continue

                contribution = int(
                    previous_previous_digit < previous_digit > digit
                    or previous_previous_digit > previous_digit < digit
                )
                count, waviness = dp(position + 1, next_tight, True, previous_digit, digit)
                total_numbers += count
                total_waviness += waviness + contribution * count

            return total_numbers, total_waviness

        return dp(0, True, False, -1, -1)[1]

/**
 * 3753. Total Waviness of Numbers in Range II
 * Time: O(D * 10 * 11 * 11 * 10)
 * Space: O(D * 11 * 11)
 */
class Solution {
    private char[] digits;
    private boolean[][][][] seen;
    private long[][][][] memoCount;
    private long[][][][] memoWaviness;

    public long totalWaviness(long num1, long num2) {
        return countUpTo(num2) - countUpTo(num1 - 1);
    }

    private long countUpTo(long limit) {
        if (limit <= 0) {
            return 0;
        }

        digits = Long.toString(limit).toCharArray();
        int n = digits.length;
        seen = new boolean[n][2][11][11];
        memoCount = new long[n][2][11][11];
        memoWaviness = new long[n][2][11][11];

        return dp(0, true, false, -1, -1).waviness;
    }

    private Result dp(
        int position,
        boolean tight,
        boolean started,
        int previousPreviousDigit,
        int previousDigit
    ) {
        if (position == digits.length) {
            return new Result(1, 0);
        }

        int startedIndex = started ? 1 : 0;
        int previousPreviousIndex = previousPreviousDigit + 1;
        int previousIndex = previousDigit + 1;

        if (!tight && seen[position][startedIndex][previousPreviousIndex][previousIndex]) {
            return new Result(
                memoCount[position][startedIndex][previousPreviousIndex][previousIndex],
                memoWaviness[position][startedIndex][previousPreviousIndex][previousIndex]
            );
        }

        int upperBound = tight ? digits[position] - '0' : 9;
        long totalCount = 0;
        long totalWaviness = 0;

        for (int digit = 0; digit <= upperBound; digit++) {
            boolean nextTight = tight && digit == upperBound;
            Result result;
            int contribution = 0;

            if (!started && digit == 0) {
                result = dp(position + 1, nextTight, false, -1, -1);
            } else if (!started) {
                result = dp(position + 1, nextTight, true, -1, digit);
            } else if (previousPreviousDigit == -1) {
                result = dp(position + 1, nextTight, true, previousDigit, digit);
            } else {
                if (
                    (previousPreviousDigit < previousDigit && previousDigit > digit)
                        || (previousPreviousDigit > previousDigit && previousDigit < digit)
                ) {
                    contribution = 1;
                }
                result = dp(position + 1, nextTight, true, previousDigit, digit);
            }

            totalCount += result.count;
            totalWaviness += result.waviness + (long) contribution * result.count;
        }

        if (!tight) {
            seen[position][startedIndex][previousPreviousIndex][previousIndex] = true;
            memoCount[position][startedIndex][previousPreviousIndex][previousIndex] = totalCount;
            memoWaviness[position][startedIndex][previousPreviousIndex][previousIndex] = totalWaviness;
        }

        return new Result(totalCount, totalWaviness);
    }

    private static class Result {
        long count;
        long waviness;

        Result(long count, long waviness) {
            this.count = count;
            this.waviness = waviness;
        }
    }
}