Kth smallest instructions

Array Math Dynamic Programming Combinatorics

44.7% acceptance

Feb 25, 2026

565

Bob is standing at cell (0, 0), and he wants to reach destination: destination = [row, column]. He can only travel right and down. You are going to help Bob by providing instructions for his journey. The instructions are represented as a string where each character is either: 'H', meaning move horizontally (go right), or 'V', meaning move vertically (go down). Multiple instructions will lead Bob to destination. For example, if destination is [2, 3], both "HHHVV" and "HVHVH" are valid instructions. However, Bob is very picky. Bob has a lucky number k, and he wants the kth lexicographically smallest instructions that will take him to destination (1-indexed). Given destination and k, return the kth lexicographically smallest instructions that will lead Bob to destination.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn kth_smallest_path(destination: Vec<i32>, mut k: i32) -> String {
    let (mut v, mut h) = (destination[0] as usize, destination[1] as usize);
    // Precompute Pascal's triangle: C[n][r]
    let n = v + h + 1;
    let mut c = vec![vec![0i64; n + 1]; n + 1];
    c[0][0] = 1;
    for i in 1..=n {
      c[i][0] = 1;
      for j in 1..=i {
        c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
      }
    }
    let mut result = String::new();
    while h > 0 || v > 0 {
      if h > 0 {
        // Number of sequences starting with 'H'
        let count = c[h + v - 1][h - 1];
        if k as i64 <= count {
          result.push('H');
          h -= 1;
        } else {
          k -= count as i32;
          result.push('V');
          v -= 1;
        }
      } else {
        result.push('V');
        v -= 1;
      }
    }
    result
  }
}