Total waviness of numbers in range ii

Math Dynamic Programming

25.1% acceptance

Feb 25, 2026

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].

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn total_waviness(num1: i64, num2: i64) -> i64 {
    Self::f(num2) - Self::f(num1 - 1)
  }

  fn f(n: i64) -> i64 {
    if n <= 0 { return 0; }
    let s: Vec<i32> = n.to_string().bytes().map(|b| (b - b'0') as i32).collect();
    let len = s.len();
    let mut result = 0i64;
    // Numbers with fewer digits (len < 3 contribute 0)
    for d in 1..len {
      if d >= 3 {
        let dummy = vec![9i32; d];
        result += Self::sum_wav_len(d, &dummy, false);
      }
    }
    if len >= 3 {
      result += Self::sum_wav_len(len, &s, true);
    }
    result
  }

  fn sum_wav_len(len: usize, limit: &[i32], tight_init: bool) -> i64 {
    use std::collections::HashMap;
    // State: (tight, pprev, prev) where pprev/prev: -1=unset, 0-9=digit
    let mut dp: HashMap<(bool, i32, i32), (i64, i64)> = HashMap::new();
    dp.insert((tight_init, -1, -1), (1, 0));
    for pos in 0..len {
      let mut new_dp: HashMap<(bool, i32, i32), (i64, i64)> = HashMap::new();
      let lo = if pos == 0 { 1 } else { 0 };
      for (&(t, pprev, prev), &(cnt, wav)) in &dp {
        let hi = if t { limit[pos] } else { 9 };
        for d in lo..=hi {
          let new_tight = t && d == limit[pos];
          let contrib = if pprev >= 0 {
            if (prev > pprev && prev > d) || (prev < pprev && prev < d) { cnt } else { 0 }
          } else { 0 };
          let e = new_dp.entry((new_tight, prev, d)).or_insert((0, 0));
          e.0 += cnt;
          e.1 += wav + contrib;
        }
      }
      dp = new_dp;
    }
    dp.values().map(|(_, w)| *w).sum()
  }
}