LeetCode 1569: Number of Ways to Reorder Array to Get Same BST Solution

class Solution {
    public int numOfWays(int[] nums) {
        return (int) (dfs(nums) - 1) % 1000000007;
    }
    
    private long dfs(int[] nums) {
        if (nums.length <= 1) {
            return 1;
        }
        
        List<Integer> left = new ArrayList<>();
        List<Integer> right = new ArrayList<>();
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[0]) {
                left.add(nums[i]);
            } else {
                right.add(nums[i]);
            }
        }
        
        long leftWays = dfs(left.stream().mapToInt(i -> i).toArray());
        long rightWays = dfs(right.stream().mapToInt(i -> i).toArray());
        
        return (factorial(left.size() + right.size()) / (factorial(left.size()) * factorial(right.size()))) * leftWays * rightWays;
    }
    
    private long factorial(int n) {
        long result = 1;
        for (int i = 1; i <= n; i++) {
            result = (result * i) % 1000000007;
        }
        return result;
    }
}