Total Waviness of Numbers in Range II - Video Solutions
Total Waviness of Numbers in Range II | Super Detailed | For Beginners | Leetcode 3753 | MIK
Total Waviness of Numbers in Range II - Video Solution
Watch 10 video solutions for Total Waviness of Numbers in Range II, a hard level problem involving Math, Dynamic Programming. This walkthrough by codestorywithMIK has 14,789 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
[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.
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 |