Total Waviness of Numbers in Range II solution and explanation
Google
9 more videos on this problem
Total Waviness of Numbers in Range II | Super Detailed | For Beginners | Leetcode 3753 | MIKcodestorywithMIK · 1:11:03 · 14K views
Q4. Total Waviness of Numbers in Range II | Easy Digit DP | Leetcode Biweekly Contest 170 | Watch2X🚀Rajan Keshari ( CSE - IIT Dhanbad ) · 16:07 · 3K views
Total Waviness of Numbers in Range II | LeetCode 3753 - Pythonimpoldev · 17:53 · 1K views
leetcode 3753 | Total Waviness of Numbers in Range II | Digit Dp | Leetcode POTD | DSACode With Vick · 43:57 · 1K views
Total Waviness of Numbers in Range II | LeetCode 3753 | Digit DP | Java Code | Developer CoderDeveloper Coder · 49:09 · 1K views
Total Waviness of Numbers in Range II | Leetcode - 3753Shivam Gupta · 29:39 · 820 views
Leetcode 3753 | Total Waviness of Numbers in Range II | Digit DP | Beginner friendlyCodeWithMeGuys · 30:56 · 679 views
Daily Leetcode #2257: Jun 05, 2026 - 3753. Total Waviness of Numbers in Range IIProgramming Live with Larry · 35:51 · 646 views
3753. Total Waviness of Numbers in Range II (Leetcode Hard)Programming Live with Larry · 1:02:18 · 513 views
Total Waviness of Numbers in Range II | LeetCode 3753Code with Siddhant · 15:38 · 285 views
The problem
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.
[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 <= 1015
Approach overview
Problem Overview: You are given a numeric range [L, R]. For each number, define its waviness based on how adjacent digits alternate between increasing and decreasing. The task is to compute the total waviness contributed by every number in the range.
Approach 1: Brute Force Enumeration (O((R-L+1) * d) time, O(1) space)
The most direct idea is to iterate through every integer from L to R. Convert each number into digits and scan adjacent pairs to determine whether the sequence goes up or down. Each time the comparison direction flips (increase → decrease or decrease → increase), increment the waviness counter. Accumulate the waviness for every number. This works for small ranges but becomes infeasible when the interval is large because the runtime grows linearly with the range size.
Approach 2: Digit Dynamic Programming (Digit DP) (O(d * 10 * states) time, O(d * states) space)
The efficient solution treats the number as a digit sequence and counts valid contributions using dynamic programming with digit constraints. Instead of enumerating every number, compute the total waviness for all numbers ≤ X and evaluate solve(R) - solve(L-1). The DP state typically tracks the current digit position, the previous digit, the last comparison direction (up or down), and whether the prefix is still tight with the upper bound. Each transition chooses the next digit and updates the direction relative to the previous digit. When the direction flips, increase the waviness contribution in the DP accumulation.
This technique avoids iterating through the entire range. It builds numbers digit by digit while respecting the upper bound and aggregates waviness counts directly in the state transitions. The approach relies on concepts from math and dynamic programming, particularly the classic digit DP pattern used for range counting problems.
Recommended for interviews: Interviewers expect the digit DP approach. Starting with brute force shows you understand the waviness definition and how it’s computed per number. Moving to digit DP demonstrates the ability to transform a range enumeration problem into a digit-level dynamic program with state compression and prefix constraints.
Solution
static int len, digits[20];
static long long memoCnt[20][11][11][2];
static long long memoSum[20][11][11][2];
static char vis[20][11][11][2];
static long long cnt, sum;
static void dfs(int pos, int pp, int pr, int st, int ti) {
if (pos == len) {
cnt = 1;
sum = 0;
return;
}
if (!ti && vis[pos][pp][pr][st]) {
cnt = memoCnt[pos][pp][pr][st];
sum = memoSum[pos][pp][pr][st];
return;
}
int h = ti ? digits[pos] : 9;
long long c = 0, s = 0;
for (int d = 0; d <= h; d++) {
int ns = st || d;
long long a = 0;
int npp, np;
if (!ns) {
npp = 10;
np = 10;
} else if (!st) {
npp = 10;
np = d;
} else {
if (pp != 10 && pr != 10 && ((pr > pp && pr > d) || (pr < pp && pr < d)))
a = 1;
npp = pr;
np = d;
}
dfs(pos + 1, npp, np, ns, ti && d == h);
c += cnt;
s += sum + a * cnt;
}
if (!ti) {
vis[pos][pp][pr][st] = 1;
memoCnt[pos][pp][pr][st] = c;
memoSum[pos][pp][pr][st] = s;
}
cnt = c;
sum = s;
}
static long long calc(long long N) {
if (N < 0) return 0;
len = 0;
long long x = N;
if (!x) {
digits[len++] = 0;
} else {
char buf[20];
int l = 0;
while (x) {
buf[l++] = x % 10;
x /= 10;
}
for (int i = l - 1; i >= 0; i--)
digits[len++] = buf[i];
}
memset(vis, 0, sizeof(vis));
dfs(0, 10, 10, 0, 1);
return sum;
}
long long totalWaviness(long long a, long long b) {
return calc(b) - calc(a - 1);
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O((R-L+1) * d) | O(1) | Small ranges where direct iteration is feasible |
| Digit DP with Direction State | O(d * 10 * states) | O(d * states) | Large numeric ranges requiring efficient counting |
| Digit DP with Memoization | O(d * 10 * states) | O(d * states) | General case for competitive programming and interviews |
Frequently asked questions
Is Total Waviness of Numbers in Range II easy or hard?
Total Waviness of Numbers in Range II is considered a hard problem. It requires recognizing the digit DP pattern, defining the correct DP state (position, previous digit, direction, tight flag), and correctly accumulating the waviness metric during transitions.
Total Waviness of Numbers in Range II Python/Java solution
Most implementations follow the same digit DP template. A recursive or iterative DP function processes digits from most significant to least significant, stores intermediate states in a memo table, and accumulates waviness contributions. The logic is identical across Python, Java, C++, and Go with only syntax differences.
What is the best approach for Total Waviness of Numbers in Range II?
The most efficient approach is digit dynamic programming (digit DP). Instead of iterating through every number in the range, compute the total waviness for all numbers ≤ X and evaluate solve(R) − solve(L−1). The DP state tracks digit position, previous digit, comparison direction, and tight bounds. This reduces the complexity to roughly O(d * 10 * states), where d is the number of digits.
How to solve Total Waviness of Numbers in Range II in O(d * 10) time?
Use digit DP to build numbers digit by digit while tracking the previous digit and whether the sequence is currently increasing or decreasing. When the direction flips, add to the waviness total. Run the DP for the upper bound and subtract the result for L−1 to obtain the value for the range.
Is Total Waviness of Numbers in Range II asked at Google/Amazon/Meta?
Problems based on digit DP and numeric range counting appear frequently in interviews at companies like Google, Amazon, and Meta. While this exact problem may not appear verbatim, the pattern of computing properties of numbers in a range using digit DP is a common advanced interview topic.
What data structure is used in Total Waviness of Numbers in Range II?
The solution primarily uses dynamic programming with memoization. The DP table stores states defined by digit index, previous digit, direction of comparison, and tight constraint. Arrays or hash maps are typically used to cache these states.
What is the time complexity of Total Waviness of Numbers in Range II?
The optimal digit DP solution runs in O(d * 10 * states) time, where d is the number of digits in the upper bound. Each digit position tries up to 10 possibilities and transitions between direction states. Space complexity is O(d * states) due to memoization of DP states.