Total Waviness of Numbers in Range II - Solution & Explanation

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.