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:
[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.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.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 <= 105Problem Overview: Given a numeric range [L, R], compute the total waviness across all numbers in that interval. Waviness depends on how adjacent digits in a number change, so each number must be inspected digit by digit and its contribution added to the final sum.
Approach 1: Brute Force Enumeration (O((R-L+1) * d) time, O(1) space)
Iterate through every integer from L to R. Convert each number to its digit representation and evaluate the waviness by scanning adjacent digits. Maintain a running total as you process each number. This approach relies purely on enumeration and basic digit processing. It works well when the range size is small but becomes expensive when R - L grows large because every number is processed individually.
Approach 2: Simulation with Digit Processing (O((R-L+1) * d) time, O(1) space)
The practical solution used in most implementations still iterates through the range but computes waviness efficiently while extracting digits. Instead of repeatedly converting to strings, use arithmetic operations (% 10, / 10) to inspect adjacent digits. Track the previous digit and update the waviness contribution during traversal. This keeps the computation tight and avoids extra allocations. The method fits naturally with problems involving math and digit-based rules.
Approach 3: Digit Dynamic Programming (O(d * states) time, O(d * states) space)
If the range becomes very large, iterate by digit position instead of by number. A classic dynamic programming technique builds numbers digit by digit while tracking constraints such as the previous digit and whether the prefix is already smaller than the bound. Each state accumulates the waviness contribution produced by the transition between digits. This avoids enumerating every integer and reduces the problem to processing digit states.
Recommended for interviews: Start with the brute force enumeration to show you understand how waviness is computed from digits. Then optimize the implementation using direct digit simulation to reduce overhead. When the interviewer hints at very large ranges, transitioning to a digit DP solution demonstrates deeper algorithmic skill and familiarity with range digit problems.
We define a helper function f(x) to calculate the waviness value of integer x. In this function, we store each digit of integer x in an array nums. If the number has fewer than 3 digits, the waviness value is 0. Otherwise, we iterate through each non-leading and non-trailing digit in the array nums, determine whether it is a peak or valley, and count the waviness value.
Then, we iterate through each integer x in the range [num1, num2] and accumulate its waviness value f(x) to obtain the final result.
The time complexity is O((num2 - num1 + 1) cdot log num2) and the space complexity is O(log num2).
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O((R-L+1) * d) | O(1) | Small ranges where iterating every number is cheap |
| Simulation with Digit Processing | O((R-L+1) * d) | O(1) | General case when the range fits within typical constraints |
| Digit Dynamic Programming | O(d * states) | O(d * states) | Very large ranges where enumerating each number is too slow |
Leetcode 3751 🔥 Total Waviness of Numbers in Range 1 | Biweekly Contest 170 Q2 | Optimal Approach • Study Placement • 158 views views
Watch 5 more video solutions →Practice Total Waviness of Numbers in Range I with our built-in code editor and test cases.
Practice on FleetCode