Skip to main content
Talentd

Total Waviness of Numbers in Range II - Solution & Explanation

HardMathDynamic Programming4 min readAsked at: Amazon, Microsoft, Google +1
Practice this 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 <= 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

Code

C

C

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO((R-L+1) * d)O(1)Small ranges where direct iteration is feasible
Digit DP with Direction StateO(d * 10 * states)O(d * states)Large numeric ranges requiring efficient counting
Digit DP with MemoizationO(d * 10 * states)O(d * states)General case for competitive programming and interviews

Video Solution

Total Waviness of Numbers in Range II | Super Detailed | For Beginners | Leetcode 3753 | MIK • codestorywithMIK • 14,789 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Total Waviness of Numbers in Range II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer