/// 386. Lexicographical Numbers (Medium)
///
/// Given an integer n, return all the numbers in the range [1, n] sorted in
/// lexicographical order.
///
/// You must write an algorithm that runs in O(n) time and uses O(1) extra
/// space.
///
/// *Example 1:*
///
///   *Input:* n = 13
///   *Output:* [1,10,11,12,13,2,3,4,5,6,7,8,9]
///
/// *Example 2:*
///
///   *Input:* n = 2
///   *Output:* [1,2]
///
/// *Constraints:*
///
///   * 1 <= n <= 5 * 104
///
use leetcode::arg;

struct Solution {}

impl Solution {
    fn radd(vec: &mut Vec<i32>, c: i32, n: i32) {
        vec.push(c);
        for d in 0..=9 {
            let p = c * 10 + d;
            if p > n {
                break;
            }
            Self::radd(vec, p, n);
        }
    }

    pub fn lexical_order(n: i32) -> Vec<i32> {
        let mut vec = Vec::new();
        for d in 1..=std::cmp::min(9, n) {
            Self::radd(&mut vec, d, n);
        }
        vec
    }
}

pub fn main() {
    println!("{:?}", Solution::lexical_order(arg(1).parse().unwrap()));
}

#[cfg(test)]
mod tests {
    use crate::Solution;
    use leetcode::vi;

    #[test]
    fn examples() {
        assert_eq!(
            Solution::lexical_order(13),
            vi("[1,10,11,12,13,2,3,4,5,6,7,8,9]")
        );
        assert_eq!(Solution::lexical_order(2), vi("[1,2]"));
    }
}