Count good integers on a grid path

Dynamic Programming

48.7% acceptance

May 13, 2026

You are given two integers l and r, and a string directions consisting of exactly three 'D' characters and three 'R' characters. For each integer x in the range [l, r] (inclusive), perform the following steps: If x has fewer than 16 digits, pad it on the left with leading zeros to obtain a 16-digit string. Place the 16 digits into a 4 × 4 grid in row-major order (the first 4 digits form the first row from left to right, the next 4 digits form the second row, and so on). Starting at the top-left cell (row = 0, column = 0), apply the 6 characters of directions in order: 'D' increments the row by 1. 'R' increments the column by 1. Record the sequence of digits visited along the path (including the starting cell), producing a sequence of length 7. The integer x is considered good if the recorded sequence is non-decreasing. Return an integer representing the number of good integers in the range [l, r].

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_good_integers_on_path(l: i64, r: i64, directions: String) -> i64 {
    let mut row = 0i32;
    let mut col = 0i32;
    let mut path_set = [false; 16];
    path_set[0] = true;
    for c in directions.chars() {
      if c == 'D' { row += 1; } else { col += 1; }
      path_set[(row * 4 + col) as usize] = true;
    }
    Self::count_up_to(r, &path_set) - Self::count_up_to(l - 1, &path_set)
  }
  fn count_up_to(n: i64, path_set: &[bool; 16]) -> i64 {
    if n < 0 { return 0; }
    let s_str = format!("{:016}", n);
    let s: Vec<u8> = s_str.bytes().map(|b| b - b'0').collect();
    let mut memo = vec![[[-1i64; 11]; 2]; 16];
    Self::dp(0, 1, 10, &s, path_set, &mut memo)
  }
  fn dp(pos: usize, tight: usize, last: usize, s: &[u8], path_set: &[bool; 16], memo: &mut Vec<[[i64; 11]; 2]>) -> i64 {
    if pos == 16 { return 1; }
    if memo[pos][tight][last] != -1 { return memo[pos][tight][last]; }
    let max_d = if tight == 1 { s[pos] } else { 9 };
    let mut total = 0i64;
    for d in 0..=max_d {
      let new_last;
      if path_set[pos] {
        if last < 10 && (d as usize) < last { continue; }
        new_last = d as usize;
      } else {
        new_last = last;
      }
      let new_tight = if tight == 1 && d == s[pos] { 1 } else { 0 };
      total += Self::dp(pos + 1, new_tight, new_last, s, path_set, memo);
    }
    memo[pos][tight][last] = total;
    total
  }
}