LeetCode #3753 — HARD

Total Waviness of Numbers in Range II

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

Solve on LeetCode

The Problem

Problem Statement

You are given two integers num1 and num2 representing an inclusive range [num1, num2].

The waviness of a number is defined as the total count of its peaks and valleys:

A digit is a peak if it is strictly greater than both of its immediate neighbors.
A digit is a valley if it is strictly less than both of its immediate neighbors.
The first and last digits of a number cannot be peaks or valleys.
Any number with fewer than 3 digits has a waviness of 0.

Return the total sum of waviness for all numbers in the range [num1, num2].

Example 1:

Input: num1 = 120, num2 = 130

Output: 3

Explanation:

In the range [120, 130]:

120: middle digit 2 is a peak, waviness = 1.
121: middle digit 2 is a peak, waviness = 1.
130: middle digit 3 is a peak, waviness = 1.
All other numbers in the range have a waviness of 0.

Thus, total waviness is 1 + 1 + 1 = 3.

Example 2:

Input: num1 = 198, num2 = 202

Output: 3

Explanation:

In the range [198, 202]:

198: middle digit 9 is a peak, waviness = 1.
201: middle digit 0 is a valley, waviness = 1.
202: middle digit 0 is a valley, waviness = 1.
All other numbers in the range have a waviness of 0.

Thus, total waviness is 1 + 1 + 1 = 3.

Example 3:

Input: num1 = 4848, num2 = 4848

Output: 2

Explanation:

Number 4848: the second digit 8 is a peak, and the third digit 4 is a valley, giving a waviness of 2.

Constraints:

1 <= num1 <= num2 <= 10¹⁵

Step 01

Brute Force Baseline

Problem summary: You are given two integers num1 and num2 representing an inclusive range [num1, num2]. The waviness of a number is defined as the total count of its peaks and valleys: A digit is a peak if it is strictly greater than both of its immediate neighbors. A digit is a valley if it is strictly less than both of its immediate neighbors. The first and last digits of a number cannot be peaks or valleys. Any number with fewer than 3 digits has a waviness of 0. Return the total sum of waviness for all numbers in the range [num1, num2].

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Math · Dynamic Programming

Example 1

120
130

Example 2

198
202

Example 3

4848
4848

Step 02

Core Insight

What unlocks the optimal approach

Use digit dynamic programming
Build a digit-DP state <code>(position, tight, lastDigit, secondLastDigit)</code>

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Largest constraint values

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #3753: Total Waviness of Numbers in Range II
// Auto-generated Java example from go.
class Solution {
    public void exampleSolution() {
    }
}
// Reference (go):
// // Accepted solution for LeetCode #3753: Total Waviness of Numbers in Range II
// package main
// 
// import (
// 	"cmp"
// 	"strconv"
// )
// 
// // https://space.bilibili.com/206214
// func totalWaviness1(num1, num2 int64) int64 {
// 	lowS := strconv.FormatInt(num1, 10)
// 	highS := strconv.FormatInt(num2, 10)
// 	n := len(highS)
// 	diffLH := n - len(lowS)
// 	memo := make([][][3][10]int, n)
// 	for i := range memo {
// 		memo[i] = make([][3][10]int, n-1) // 一个数至多包含 n-2 个峰或谷
// 	}
// 
// 	var dfs func(int, int, int, int, bool, bool) int
// 	dfs = func(i, waviness, lastCmp, lastDigit int, limitLow, limitHigh bool) (res int) {
// 		if i == n {
// 			return waviness
// 		}
// 		if !limitLow && !limitHigh {
// 			p := &memo[i][waviness][lastCmp+1][lastDigit]
// 			if *p > 0 {
// 				return *p - 1
// 			}
// 			defer func() { *p = res + 1 }()
// 		}
// 
// 		lo := 0
// 		if limitLow && i >= diffLH {
// 			lo = int(lowS[i-diffLH] - '0')
// 		}
// 		hi := 9
// 		if limitHigh {
// 			hi = int(highS[i] - '0')
// 		}
// 
// 		isNum := !limitLow || i > diffLH // 前面是否填过数字
// 		for d := lo; d <= hi; d++ {
// 			w := waviness
// 			c := 0
// 			if isNum { // 当前填的数不是最高位
// 				c = cmp.Compare(d, lastDigit)
// 			}
// 			if c*lastCmp < 0 { // 形成了一个峰或谷
// 				w++
// 			}
// 			res += dfs(i+1, w, c, d, limitLow && d == lo, limitHigh && d == hi)
// 		}
// 		return
// 	}
// 	return int64(dfs(0, 0, 0, 0, true, true))
// }
// 
// func totalWaviness(num1, num2 int64) int64 {
// 	lowS := strconv.FormatInt(num1, 10)
// 	highS := strconv.FormatInt(num2, 10)
// 	n := len(highS)
// 	diffLH := n - len(lowS)
// 	type pair struct{ wavinessSum, numCnt int }
// 	memo := make([][3][10]pair, n)
// 
// 	var dfs func(int, int, int, bool, bool) pair
// 	dfs = func(i, lastCmp, lastDigit int, limitLow, limitHigh bool) (res pair) {
// 		if i == n {
// 			return pair{0, 1} // 本题无特殊约束，能递归到终点的都是合法数字
// 		}
// 		if !limitLow && !limitHigh {
// 			p := &memo[i][lastCmp+1][lastDigit]
// 			if p.numCnt > 0 {
// 				return *p
// 			}
// 			defer func() { *p = res }()
// 		}
// 
// 		lo := 0
// 		if limitLow && i >= diffLH {
// 			lo = int(lowS[i-diffLH] - '0')
// 		}
// 		hi := 9
// 		if limitHigh {
// 			hi = int(highS[i] - '0')
// 		}
// 
// 		isNum := !limitLow || i > diffLH // 前面是否填过数字
// 		for d := lo; d <= hi; d++ {
// 			c := 0
// 			if isNum { // 当前填的数不是最高位
// 				c = cmp.Compare(d, lastDigit)
// 			}
// 			sub := dfs(i+1, c, d, limitLow && d == lo, limitHigh && d == hi)
// 			res.wavinessSum += sub.wavinessSum // 累加子树的波动值
// 			res.numCnt += sub.numCnt // 累加子树的合法数字个数
// 			if c*lastCmp < 0 { // 形成了一个峰或谷
// 				res.wavinessSum += sub.numCnt // 这个峰谷会出现在 sub.numCnt 个数字中
// 			}
// 		}
// 		return
// 	}
// 	return int64(dfs(0, 0, 0, true, true).wavinessSum)
// }

// Accepted solution for LeetCode #3753: Total Waviness of Numbers in Range II
package main

import (
	"cmp"
	"strconv"
)

// https://space.bilibili.com/206214
func totalWaviness1(num1, num2 int64) int64 {
	lowS := strconv.FormatInt(num1, 10)
	highS := strconv.FormatInt(num2, 10)
	n := len(highS)
	diffLH := n - len(lowS)
	memo := make([][][3][10]int, n)
	for i := range memo {
		memo[i] = make([][3][10]int, n-1) // 一个数至多包含 n-2 个峰或谷
	}

	var dfs func(int, int, int, int, bool, bool) int
	dfs = func(i, waviness, lastCmp, lastDigit int, limitLow, limitHigh bool) (res int) {
		if i == n {
			return waviness
		}
		if !limitLow && !limitHigh {
			p := &memo[i][waviness][lastCmp+1][lastDigit]
			if *p > 0 {
				return *p - 1
			}
			defer func() { *p = res + 1 }()
		}

		lo := 0
		if limitLow && i >= diffLH {
			lo = int(lowS[i-diffLH] - '0')
		}
		hi := 9
		if limitHigh {
			hi = int(highS[i] - '0')
		}

		isNum := !limitLow || i > diffLH // 前面是否填过数字
		for d := lo; d <= hi; d++ {
			w := waviness
			c := 0
			if isNum { // 当前填的数不是最高位
				c = cmp.Compare(d, lastDigit)
			}
			if c*lastCmp < 0 { // 形成了一个峰或谷
				w++
			}
			res += dfs(i+1, w, c, d, limitLow && d == lo, limitHigh && d == hi)
		}
		return
	}
	return int64(dfs(0, 0, 0, 0, true, true))
}

func totalWaviness(num1, num2 int64) int64 {
	lowS := strconv.FormatInt(num1, 10)
	highS := strconv.FormatInt(num2, 10)
	n := len(highS)
	diffLH := n - len(lowS)
	type pair struct{ wavinessSum, numCnt int }
	memo := make([][3][10]pair, n)

	var dfs func(int, int, int, bool, bool) pair
	dfs = func(i, lastCmp, lastDigit int, limitLow, limitHigh bool) (res pair) {
		if i == n {
			return pair{0, 1} // 本题无特殊约束，能递归到终点的都是合法数字
		}
		if !limitLow && !limitHigh {
			p := &memo[i][lastCmp+1][lastDigit]
			if p.numCnt > 0 {
				return *p
			}
			defer func() { *p = res }()
		}

		lo := 0
		if limitLow && i >= diffLH {
			lo = int(lowS[i-diffLH] - '0')
		}
		hi := 9
		if limitHigh {
			hi = int(highS[i] - '0')
		}

		isNum := !limitLow || i > diffLH // 前面是否填过数字
		for d := lo; d <= hi; d++ {
			c := 0
			if isNum { // 当前填的数不是最高位
				c = cmp.Compare(d, lastDigit)
			}
			sub := dfs(i+1, c, d, limitLow && d == lo, limitHigh && d == hi)
			res.wavinessSum += sub.wavinessSum // 累加子树的波动值
			res.numCnt += sub.numCnt // 累加子树的合法数字个数
			if c*lastCmp < 0 { // 形成了一个峰或谷
				res.wavinessSum += sub.numCnt // 这个峰谷会出现在 sub.numCnt 个数字中
			}
		}
		return
	}
	return int64(dfs(0, 0, 0, true, true).wavinessSum)
}

# Accepted solution for LeetCode #3753: Total Waviness of Numbers in Range II
#
# @lc app=leetcode id=3753 lang=python3
#
# [3753] Total Waviness of Numbers in Range II
#

# @lc code=start
class Solution:
    def totalWaviness(self, num1: int, num2: int) -> int:
        def solve(s):
            digits = list(map(int, str(s)))
            n = len(digits)
            # memo key: (index, second_last_digit, last_digit, is_less, is_started)
            # value: (count_of_numbers, sum_of_waviness)
            memo = {}

            def dp(idx, second_last, last, is_less, is_started):
                if idx == n:
                    return 1, 0
                
                state = (idx, second_last, last, is_less, is_started)
                if state in memo:
                    return memo[state]
                
                limit = digits[idx] if not is_less else 9
                total_count = 0
                total_waviness = 0
                
                for d in range(limit + 1):
                    new_less = is_less or (d < limit)
                    new_started = is_started or (d > 0)
                    
                    if not new_started:
                        # Still in leading zeros
                        c, w = dp(idx + 1, 10, 10, new_less, False)
                        total_count += c
                        total_waviness += w
                    else:
                        # Check if the previous digit (last) becomes a peak or valley
                        # This requires a valid 3-digit window: second_last, last, d
                        current_contribution = 0
                        if second_last != 10 and last != 10:
                            if (last > second_last and last > d) or (last < second_last and last < d):
                                current_contribution = 1
                        
                        # Determine args for next call
                        # If this is the very first digit (is_started was False), 
                        # then effectively second_last remains "empty" (10) for the next state,
                        # and last becomes d.
                        # If we had already started, we shift the window.
                        next_second_last = 10 if not is_started else last
                        next_last = d
                        
                        c, w = dp(idx + 1, next_second_last, next_last, new_less, True)
                        
                        total_count += c
                        total_waviness += w + (c * current_contribution)
                
                memo[state] = (total_count, total_waviness)
                return total_count, total_waviness

            return dp(0, 10, 10, False, False)[1]

        return solve(num2) - solve(num1 - 1)
# @lc code=end

// Accepted solution for LeetCode #3753: Total Waviness of Numbers in Range II
// Rust example auto-generated from go reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
    pub fn rust_example() {
        // Port the logic from the reference block below.
    }
}

// Reference (go):
// // Accepted solution for LeetCode #3753: Total Waviness of Numbers in Range II
// package main
// 
// import (
// 	"cmp"
// 	"strconv"
// )
// 
// // https://space.bilibili.com/206214
// func totalWaviness1(num1, num2 int64) int64 {
// 	lowS := strconv.FormatInt(num1, 10)
// 	highS := strconv.FormatInt(num2, 10)
// 	n := len(highS)
// 	diffLH := n - len(lowS)
// 	memo := make([][][3][10]int, n)
// 	for i := range memo {
// 		memo[i] = make([][3][10]int, n-1) // 一个数至多包含 n-2 个峰或谷
// 	}
// 
// 	var dfs func(int, int, int, int, bool, bool) int
// 	dfs = func(i, waviness, lastCmp, lastDigit int, limitLow, limitHigh bool) (res int) {
// 		if i == n {
// 			return waviness
// 		}
// 		if !limitLow && !limitHigh {
// 			p := &memo[i][waviness][lastCmp+1][lastDigit]
// 			if *p > 0 {
// 				return *p - 1
// 			}
// 			defer func() { *p = res + 1 }()
// 		}
// 
// 		lo := 0
// 		if limitLow && i >= diffLH {
// 			lo = int(lowS[i-diffLH] - '0')
// 		}
// 		hi := 9
// 		if limitHigh {
// 			hi = int(highS[i] - '0')
// 		}
// 
// 		isNum := !limitLow || i > diffLH // 前面是否填过数字
// 		for d := lo; d <= hi; d++ {
// 			w := waviness
// 			c := 0
// 			if isNum { // 当前填的数不是最高位
// 				c = cmp.Compare(d, lastDigit)
// 			}
// 			if c*lastCmp < 0 { // 形成了一个峰或谷
// 				w++
// 			}
// 			res += dfs(i+1, w, c, d, limitLow && d == lo, limitHigh && d == hi)
// 		}
// 		return
// 	}
// 	return int64(dfs(0, 0, 0, 0, true, true))
// }
// 
// func totalWaviness(num1, num2 int64) int64 {
// 	lowS := strconv.FormatInt(num1, 10)
// 	highS := strconv.FormatInt(num2, 10)
// 	n := len(highS)
// 	diffLH := n - len(lowS)
// 	type pair struct{ wavinessSum, numCnt int }
// 	memo := make([][3][10]pair, n)
// 
// 	var dfs func(int, int, int, bool, bool) pair
// 	dfs = func(i, lastCmp, lastDigit int, limitLow, limitHigh bool) (res pair) {
// 		if i == n {
// 			return pair{0, 1} // 本题无特殊约束，能递归到终点的都是合法数字
// 		}
// 		if !limitLow && !limitHigh {
// 			p := &memo[i][lastCmp+1][lastDigit]
// 			if p.numCnt > 0 {
// 				return *p
// 			}
// 			defer func() { *p = res }()
// 		}
// 
// 		lo := 0
// 		if limitLow && i >= diffLH {
// 			lo = int(lowS[i-diffLH] - '0')
// 		}
// 		hi := 9
// 		if limitHigh {
// 			hi = int(highS[i] - '0')
// 		}
// 
// 		isNum := !limitLow || i > diffLH // 前面是否填过数字
// 		for d := lo; d <= hi; d++ {
// 			c := 0
// 			if isNum { // 当前填的数不是最高位
// 				c = cmp.Compare(d, lastDigit)
// 			}
// 			sub := dfs(i+1, c, d, limitLow && d == lo, limitHigh && d == hi)
// 			res.wavinessSum += sub.wavinessSum // 累加子树的波动值
// 			res.numCnt += sub.numCnt // 累加子树的合法数字个数
// 			if c*lastCmp < 0 { // 形成了一个峰或谷
// 				res.wavinessSum += sub.numCnt // 这个峰谷会出现在 sub.numCnt 个数字中
// 			}
// 		}
// 		return
// 	}
// 	return int64(dfs(0, 0, 0, true, true).wavinessSum)
// }

// Accepted solution for LeetCode #3753: Total Waviness of Numbers in Range II
// Auto-generated TypeScript example from go.
function exampleSolution(): void {
}
// Reference (go):
// // Accepted solution for LeetCode #3753: Total Waviness of Numbers in Range II
// package main
// 
// import (
// 	"cmp"
// 	"strconv"
// )
// 
// // https://space.bilibili.com/206214
// func totalWaviness1(num1, num2 int64) int64 {
// 	lowS := strconv.FormatInt(num1, 10)
// 	highS := strconv.FormatInt(num2, 10)
// 	n := len(highS)
// 	diffLH := n - len(lowS)
// 	memo := make([][][3][10]int, n)
// 	for i := range memo {
// 		memo[i] = make([][3][10]int, n-1) // 一个数至多包含 n-2 个峰或谷
// 	}
// 
// 	var dfs func(int, int, int, int, bool, bool) int
// 	dfs = func(i, waviness, lastCmp, lastDigit int, limitLow, limitHigh bool) (res int) {
// 		if i == n {
// 			return waviness
// 		}
// 		if !limitLow && !limitHigh {
// 			p := &memo[i][waviness][lastCmp+1][lastDigit]
// 			if *p > 0 {
// 				return *p - 1
// 			}
// 			defer func() { *p = res + 1 }()
// 		}
// 
// 		lo := 0
// 		if limitLow && i >= diffLH {
// 			lo = int(lowS[i-diffLH] - '0')
// 		}
// 		hi := 9
// 		if limitHigh {
// 			hi = int(highS[i] - '0')
// 		}
// 
// 		isNum := !limitLow || i > diffLH // 前面是否填过数字
// 		for d := lo; d <= hi; d++ {
// 			w := waviness
// 			c := 0
// 			if isNum { // 当前填的数不是最高位
// 				c = cmp.Compare(d, lastDigit)
// 			}
// 			if c*lastCmp < 0 { // 形成了一个峰或谷
// 				w++
// 			}
// 			res += dfs(i+1, w, c, d, limitLow && d == lo, limitHigh && d == hi)
// 		}
// 		return
// 	}
// 	return int64(dfs(0, 0, 0, 0, true, true))
// }
// 
// func totalWaviness(num1, num2 int64) int64 {
// 	lowS := strconv.FormatInt(num1, 10)
// 	highS := strconv.FormatInt(num2, 10)
// 	n := len(highS)
// 	diffLH := n - len(lowS)
// 	type pair struct{ wavinessSum, numCnt int }
// 	memo := make([][3][10]pair, n)
// 
// 	var dfs func(int, int, int, bool, bool) pair
// 	dfs = func(i, lastCmp, lastDigit int, limitLow, limitHigh bool) (res pair) {
// 		if i == n {
// 			return pair{0, 1} // 本题无特殊约束，能递归到终点的都是合法数字
// 		}
// 		if !limitLow && !limitHigh {
// 			p := &memo[i][lastCmp+1][lastDigit]
// 			if p.numCnt > 0 {
// 				return *p
// 			}
// 			defer func() { *p = res }()
// 		}
// 
// 		lo := 0
// 		if limitLow && i >= diffLH {
// 			lo = int(lowS[i-diffLH] - '0')
// 		}
// 		hi := 9
// 		if limitHigh {
// 			hi = int(highS[i] - '0')
// 		}
// 
// 		isNum := !limitLow || i > diffLH // 前面是否填过数字
// 		for d := lo; d <= hi; d++ {
// 			c := 0
// 			if isNum { // 当前填的数不是最高位
// 				c = cmp.Compare(d, lastDigit)
// 			}
// 			sub := dfs(i+1, c, d, limitLow && d == lo, limitHigh && d == hi)
// 			res.wavinessSum += sub.wavinessSum // 累加子树的波动值
// 			res.numCnt += sub.numCnt // 累加子树的合法数字个数
// 			if c*lastCmp < 0 { // 形成了一个峰或谷
// 				res.wavinessSum += sub.numCnt // 这个峰谷会出现在 sub.numCnt 个数字中
// 			}
// 		}
// 		return
// 	}
// 	return int64(dfs(0, 0, 0, true, true).wavinessSum)
// }

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(n × m)

Space

O(n × m)

Approach Breakdown

RECURSIVE

O(2ⁿ) time

O(n) space

Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.

DYNAMIC PROGRAMMING

O(n × m) time

O(n × m) space

Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.

Shortcut: Count your DP state dimensions → that’s your time. Can you drop one? That’s your space optimization.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Overflow in intermediate arithmetic

Wrong move: Temporary multiplications exceed integer bounds.

Usually fails on: Large inputs wrap around unexpectedly.

Fix: Use wider types, modular arithmetic, or rearranged operations.

State misses one required dimension

Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.

Usually fails on: Correctness breaks on cases that differ only in hidden state.

Fix: Define state so each unique subproblem maps to one DP cell.