LeetCode 3753 - Total Waviness of Numbers in Range II

The problem asks us to compute a cumulative score over all integers in an inclusive range [num1, num2], where each individual number has a score called waviness.

leetcodehardmathdynamic-programming

LeetCode Problem 3753

Difficulty: 🔴 Hard
Topics: Math, Dynamic Programming

Solution

Problem Understanding

The problem asks us to compute a cumulative score over all integers in an inclusive range [num1, num2], where each individual number has a score called waviness. The waviness of a number is defined as the number of positions in its digit sequence that qualify as either a peak or a valley.

A digit is considered a peak if it is strictly greater than both of its adjacent digits, and it is considered a valley if it is strictly smaller than both of its adjacent digits. Only digits with both a left and right neighbor can contribute, meaning the first and last digits are never counted. Additionally, any number with fewer than three digits has waviness zero.

The task is not to compute waviness for a single number, but to compute the sum of waviness across all numbers in the range. Since the upper bound can be as large as 10^15, the range is far too large for brute force iteration.

The constraints imply that a direct enumeration of all numbers is impossible in the worst case, so the solution must rely on digit dynamic programming. Edge cases include small numbers under 100 (always zero contribution), single-point ranges, and numbers with repeated digits where no peaks or valleys exist. Another subtle case is handling leading zeros in digit DP, since waviness only applies after the number actually starts.

Approaches

The brute-force approach is to iterate through every number in [num1, num2], convert each number into its digit array, and compute its waviness by checking every interior digit. While correct, this approach requires iterating over up to 10^15 numbers, which is computationally infeasible.

The key insight is that waviness is a local property over triples of digits. Each contribution depends only on three consecutive digits (a, b, c), where b is counted if it is a peak or valley relative to its neighbors. This locality allows us to use digit DP while maintaining a sliding window of the last two digits, enabling us to evaluate contributions incrementally as we construct numbers digit by digit.

We define a digit DP where the state keeps track of the current position, whether we are still bounded by the prefix of the input limit, whether the number has started (to ignore leading zeros), and the last two digits chosen. When we place a new digit, we can evaluate whether the previous digit becomes a peak or valley using the last three digits.

Approach Time Complexity Space Complexity Notes
Brute Force O(N × D) O(D) Check each number digit by digit for peaks and valleys
Optimal Digit DP O(16 × 10 × 10 × 16 × 2 × 2) O(16 × 10 × 10 × 2 × 2) DP over digits with last-two-digit state and tight constraint

Algorithm Walkthrough

The optimal solution uses digit DP with memoization over number construction.

  1. We define a function solve(x) that computes the total waviness for all numbers from 0 to x. The final answer is solve(num2) - solve(num1 - 1) because the problem is a range sum.
  2. We convert x into a digit array so we can process it from the most significant digit to the least significant digit while respecting the upper bound constraint.
  3. We define a recursive DP function with the following state: current index, tight constraint flag, started flag indicating whether a non-leading-zero digit has been placed, length of the constructed number so far, and the last two digits (prev2, prev1).
  4. At each step, we try all possible digits from 0 to 9, respecting the tight constraint if we are still matching the prefix of x.
  5. When we place a digit d, we shift the window of last digits. If we already have at least two valid previous digits in a started number, then adding d allows us to evaluate the middle digit prev1 using the triple (prev2, prev1, d).
  6. If the number has started and the length is at least 3, we check whether prev1 is a peak or valley:
  • Peak if prev1 > prev2 and prev1 > d
  • Valley if prev1 < prev2 and prev1 < d

If either condition holds, we add 1 to the contribution. 7. We update the DP state and continue recursively. 8. The result accumulates contributions from all valid number constructions.

The DP ensures we count contributions exactly once per valid triple across all numbers.

Why it works

The correctness comes from the fact that each digit in a number can only be evaluated as a peak or valley once its right neighbor is known. By maintaining a rolling window of three digits during construction, every valid middle digit is evaluated exactly when its right boundary is placed, ensuring no double counting or omission. The digit DP guarantees completeness over all valid numbers under the bound constraint.

Python Solution

class Solution:
    def totalWaviness(self, num1: int, num2: int) -> int:
        def solve(x: int) -> int:
            if x <= 0:
                return 0

            digits = list(map(int, str(x)))
            n = len(digits)

            from functools import lru_cache

            @lru_cache(None)
            def dp(i: int, tight: int, started: int, length: int, prev2: int, prev1: int) -> int:
                if i == n:
                    return 0

                limit = digits[i] if tight else 9
                res = 0

                for d in range(limit + 1):
                    ntight = tight and (d == limit)

                    nstarted = started
                    nlen = length
                    nprev2, nprev1 = prev2, prev1

                    if not nstarted:
                        if d != 0:
                            nstarted = 1
                            nlen = 1
                            nprev2, nprev1 = -1, d
                        else:
                            nprev2, nprev1 = -1, -1
                    else:
                        nlen += 1
                        nprev2, nprev1 = prev1, d

                        if nlen >= 3:
                            if prev2 != -1:
                                if (prev1 > prev2 and prev1 > d) or (prev1 < prev2 and prev1 < d):
                                    res += 1

                    res += dp(i + 1, ntight, nstarted, nlen, nprev2, nprev1)

                return res

            return dp(0, 1, 0, 0, -1, -1)

        return solve(num2) - solve(num1 - 1)

Code Explanation

The solution defines a helper function solve that computes the cumulative waviness from 0 to x. Inside it, we perform digit DP with memoization. The dp function builds numbers digit by digit while tracking whether we are still under the prefix constraint (tight), whether a valid number has started (started), and how many digits have been placed in the active number (length).

The variables prev2 and prev1 maintain the last two digits of the currently constructed number. When a new digit is placed, we update this window and check whether the middle digit forms a peak or valley. The contribution is added immediately when the triple becomes complete.

The recursion explores all valid digit combinations, ensuring all numbers up to x are covered exactly once, and subtracting two prefix results gives the final range answer.

Go Solution

package main

func totalWaviness(num1 int64, num2 int64) int64 {
	solve := func(x int64) int64 {
		if x <= 0 {
			return 0
		}

		digits := []int{}
		for t := x; t > 0; t /= 10 {
			digits = append([]int{int(t % 10)}, digits...)
		}
		n := len(digits)

		memo := map[[6]int]int64{}

		var dp func(i int, tight int, started int, length int, prev2 int, prev1 int) int64
		dp = func(i int, tight int, started int, length int, prev2 int, prev1 int) int64 {
			if i == n {
				return 0
			}

			key := [6]int{i, tight, started, length, prev2 + 1, prev1 + 1}
			if val, ok := memo[key]; ok {
				return val
			}

			var res int64 = 0
			limit := 9
			if tight == 1 {
				limit = digits[i]
			}

			for d := 0; d <= limit; d++ {
				ntight := 0
				if tight == 1 && d == limit {
					ntight = 1
				}

				nstarted := started
				nlen := length
				nprev2, nprev1 := prev2, prev1

				if nstarted == 0 {
					if d != 0 {
						nstarted = 1
						nlen = 1
						nprev2, nprev1 = -1, d
					} else {
						nprev2, nprev1 = -1, -1
					}
				} else {
					nlen++
					nprev2, nprev1 = prev1, d

					if nlen >= 3 && prev2 != -1 {
						if (prev1 > prev2 && prev1 > d) || (prev1 < prev2 && prev1 < d) {
							res++
						}
					}
				}

				res += dp(i+1, ntight, nstarted, nlen, nprev2, nprev1)
			}

			memo[key] = res
			return res
		}

		return dp(0, 1, 0, 0, -1, -1)
	}

	return solve(num2) - solve(num1-1)
}

Go-specific notes

The Go implementation replaces lru_cache with an explicit map memoization using a fixed-size array key. Since Go does not support negative map keys directly for arrays, we offset prev2 and prev1 when storing them. The recursion structure remains identical to Python, but careful attention is needed to handle integer types (int64) to avoid overflow.

Worked Examples

For the input num1 = 120, num2 = 130, the DP evaluates each number independently through prefix construction. For 120, the DP builds sequences starting with 1, then 2, then 0, and when the triple (1, 2, 0) is formed, it detects that 2 > 1 and 2 > 0, adding one contribution. The same process occurs for 121 and 130, each producing one valid peak. All other numbers fail to form valid triples, resulting in total waviness of 3.

For 198, 202, the DP identifies valid triples (1, 9, 8), (2, 0, 1), and (2, 0, 2) respectively. Each satisfies either peak or valley conditions exactly once, and the DP ensures these are counted when the right boundary digit is placed.

For 4848, the DP evaluates two triples: (4, 8, 4) and (8, 4, 8). Both satisfy peak and valley conditions respectively, resulting in a total waviness of 2.

Complexity Analysis

Measure Complexity Explanation
Time O(n × 10 × 10 × 2 × 2 × n_states) Each digit DP state explores up to 10 transitions with memoization over position, tight, start, and last-two-digit state
Space O(n × 10 × 10 × 2 × 2) Memoization table stores all DP states

The complexity is acceptable because n ≤ 16, making the state space manageable despite multiple dimensions.

Test Cases

assert Solution().totalWaviness(120, 130) == 3  # example case
assert Solution().totalWaviness(198, 202) == 3  # example case
assert Solution().totalWaviness(4848, 4848) == 2  # example case

assert Solution().totalWaviness(1, 9) == 0  # single digit numbers
assert Solution().totalWaviness(10, 99) == 0  # two-digit numbers
assert Solution().totalWaviness(100, 100) == 0  # leading zero edge

assert Solution().totalWaviness(100, 105) >= 0  # small range sanity
assert Solution().totalWaviness(999, 1005) >= 0  # boundary crossing
Test Why
single digits verifies minimum length constraint
two-digit range ensures no invalid peak/valley counting
provided examples correctness against problem statement
boundary crossing ensures digit DP handles transitions correctly

Edge Cases

One important edge case is when the range includes numbers with fewer than three digits. These must always contribute zero, and the DP ensures this by only counting contributions when the constructed length reaches at least three digits after the number has started.

Another edge case is numbers with leading zeros in digit DP construction. Without careful handling, leading zeros could incorrectly participate in peak or valley detection. This is avoided by tracking a started flag, ensuring contributions only occur after the number has begun.

A third edge case is when peaks or valleys occur at the boundaries of the number. Since the first and last digits are explicitly excluded, the DP only evaluates a digit as a peak or valley when it has both left and right neighbors available, enforced by the rolling window mechanism that only checks the middle digit once all three digits are present.