Rust | “i dont like trees” faster-then-editorial approach
Intuition\nThe answer will be the product for all nodes of $\binom{k+m}{m}$ where $k$ and $m$ are sizes of left and right subtree of the node, respectively.\n\n
# Intuition\nThe answer will be the product for all nodes of $\\binom{k+m}{m}$ where $k$ and $m$ are sizes of left and right subtree of the node, respectively.\n\nWe want to compute the sizes of subtrees somehow. The easiest way would be to either build the tree directly or somehow iterate through it via function recursion.\n\nBut we are not going to do this for two reasons. First, we don\'t like trees. Second, this will take worst-case quadratic time (we are talking `[1, 2, 3, ..., 1000]` case here).\n\n(As evident from the editorial, a quadratic time solution will work. But we can to better than this.)\n\n# Approach\nInstead we can just reverse the permutation and notice the answer immediately. For any value $i$ in the reversed permutation, if we locate values $j$ and $k$ that are less than $i$ and are closest to $i$ from right and left respectively, i.e.\n$[\u2026, j, \\underbrace{\u2026}_{\\text{values}\u2265i}, i, \\underbrace{\u2026}_{\\text{values}\u2265i}, k, \u2026]$\nthen the values between $j$ and $i$ are the indices (in the original array) of values in the left subtree of $i$, and the values between $i$ and $k$ are the indices of values in the right subtree.\n\nTherefore we only need to reverse the permutation (which is essentially sorting the original array) and then have a pass though it noting for each value $i$ the distances to the closest values that are less than $i$ (this will need a stack of previous smaller values).\n\nAfter that only the problem of computing the binomial coefficients remains. Unlike editorial, which uses a quadratic solution by precomputing Pascal\'s triangle, we will use $\\binom{k+m}{m} = \\frac{(k+m)!}{k! \\cdot m!}$ formula, and only precompute the factorials. In fact, since factorials are constants, we can precompute them compile-time (up to $999!$) using Rust\'s const expressions.\n\n# Complexity\n- Time complexity: $O(n \\log(n))$, where $n = nums.\\mathrm{length}$.\n\n- Space complexity: $O(n)$.\n\nLeetCode shows `4 ms` and `2.3 MB`.\n\n# Code\n```\n/// Standard \u201Cgive the answer modulo 10\u2079\xA0+\xA07\u201D thing\nmod modulo {\n\nuse std::{ops::{Add, Sub, Mul, Div, AddAssign, MulAssign}, iter::Sum};\n\n#[derive(Clone, Copy, PartialEq, Eq, Debug)]\npub struct I32Mod(i32);\n\nfn ext_gcd(a: i32, b: i32) -> (i32, i32, i32) {\n    let (mut a, mut b) = (a, b);\n    let (mut ma, mut na, mut mb, mut nb) = (1_i32, 0_i32, 0_i32, 1_i32);\n    assert!(a > 0 && b > 0);\n    while b > 0 {\n        let (k, r) = (a / b, a % b);\n        let (mr, nr) = (\n            ma - k * mb,\n            na - k * nb,\n        );\n        a = b;\n        ma = mb; na = nb;\n        b = r;\n        mb = mr; nb = nr;\n    }\n    return (a, ma, na);\n}\n\nimpl I32Mod {\n    pub const MOD: i32 = 10_i32.pow(9) + 7;\n\n    #[inline]\n    pub fn inverse(self) -> Self {\n        assert!(self.0 != 0, "only nonzero elements are inversible");\n        let (d, _, n) = ext_gcd(Self::MOD, self.0);\n        assert!(d == 1, "element should be inversible");\n        return n.into()\n    }\n\n    pub const fn const_from(value: i32) -> Self {\n        Self((value % Self::MOD + Self::MOD) % Self::MOD)\n    }\n\n    pub const fn const_mul(self, other: I32Mod) -> I32Mod {\n        Self((\n            (self.0 as i64 * other.0 as i64) % (Self::MOD as i64)\n        ) as i32)\n    }\n\n}\n\nimpl From<i32> for I32Mod {\n    #[inline]\n    fn from(value: i32) -> Self {\n        Self((value % Self::MOD + Self::MOD) % Self::MOD)\n    }\n}\n\nimpl From<I32Mod> for i32 {\n    #[inline]\n    fn from(value: I32Mod) -> i32 {\n        value.0\n    }\n}\n\nimpl Add<I32Mod> for I32Mod {\n    type Output = I32Mod;\n    #[inline]\n    fn add(self, other: I32Mod) -> I32Mod {\n        Self((self.0 + other.0) % Self::MOD)\n    }\n}\n\nimpl Sub<I32Mod> for I32Mod {\n    type Output = I32Mod;\n    #[inline]\n    fn sub(self, other: I32Mod) -> I32Mod {\n        Self((self.0 - other.0 + Self::MOD) % Self::MOD)\n    }\n}\n\nimpl Mul<I32Mod> for I32Mod {\n    type Output = I32Mod;\n    #[inline]\n    fn mul(self, other: I32Mod) -> I32Mod {\n        Self((\n            (self.0 as i64 * other.0 as i64) % (Self::MOD as i64)\n        ) as i32)\n    }\n}\n\nimpl Div<I32Mod> for I32Mod {\n    type Output = I32Mod;\n    // #[inline]\n    fn div(self, rhs: I32Mod) -> Self::Output {\n        self * rhs.inverse()\n    }\n}\n\nimpl AddAssign<I32Mod> for I32Mod {\n    #[inline]\n    fn add_assign(&mut self, other: I32Mod) {\n        *self = *self + other;\n    }\n}\n\nimpl MulAssign<I32Mod> for I32Mod {\n    #[inline]\n    fn mul_assign(&mut self, other: I32Mod) {\n        *self = *self * other;\n    }\n}\n\n} // mod modulo\n\nuse modulo::I32Mod;\n\nconst MAX_N: usize = 1000;\n\nconst factorials: [I32Mod; MAX_N] = { // compile-time precompute\n    let mut result: [I32Mod; MAX_N] = [I32Mod::const_from(0); MAX_N];\n    result[0] = I32Mod::const_from(1);\n    let mut i = 1;\n    while i < MAX_N {\n        result[i] = result[i-1].const_mul(I32Mod::const_from(i as i32));\n        i += 1;\n    }\n    result\n};\n\nimpl Solution {\n    pub fn num_of_ways(nums: Vec<i32>) -> i32 {\n        let n = nums.len();\n        assert!(n <= MAX_N);\n        let inv_nums = { // permutation inverse\n            let mut inv_nums = (0..(n as i32)).collect::<Vec<_>>();\n            inv_nums.sort_unstable_by_key(|&i| nums[i as usize]);\n            inv_nums.push(-1); // add guard\n            inv_nums\n        };\n        let margins = {\n            let mut margins = Vec::<(i32,i32)>::with_capacity(n + 1);\n            let mut stack = Vec::with_capacity(20);\n            for (j, i) in inv_nums.into_iter().enumerate() {\n                let j = j as i32;\n                // clear the stack from values that are larger than us\n                // (guard will wipe the stack on last iteration)\n                loop { match stack.last() {\n                    Some(&(j1, i1)) if i1 > i => {\n                        margins[j1 as usize].1 = j - j1 - 1;\n                        stack.pop();\n                    },\n                    _ => break,\n                } }\n                margins.push((\n                    match stack.last() {\n                        Some(&(j1, _)) => j - j1 - 1,\n                        None => j,\n                    },\n                    -1, // must get overwritten later\n                ));\n                stack.push((j, i));\n            }\n            margins.pop(); // remove guard\n            margins\n        };\n        let mut result_frac = (I32Mod::from(1), I32Mod::from(1));\n        for (left, right) in margins {\n            result_frac.0 *= factorials[(left + right) as usize];\n            result_frac.1 *= factorials[left as usize];\n            result_frac.1 *= factorials[right as usize];\n        }\n        return (result_frac.0 / result_frac.1 - 1.into()).into();\n    }\n}\n```\n\nP.S. It\'s a joke. I like trees. Just not in this problem.
['Rust']