/*
https://leetcode.com/problems/permutations/
Runtime: 40 ms, faster than 5.01% of Java online submissions for Permutations.
Memory Usage: 36.8 MB, less than 97.16% of Java online submissions for Permutations.
*/
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        ArrayList<List<Integer>> output = new ArrayList<>();
        for (int step = 0, il = factorial(nums.length); step < il; step++) {
            output.add(Arrays.stream(nums).boxed().collect(Collectors.toList()));

            int i = nums.length - 2;
            while (i > -1 && nums[i] >= nums[i + 1]) {
                --i;
            }
            if (i > -1) {
                int j = i + 1;
                while (j < nums.length && nums[i] < nums[j]) {
                    ++j;
                }
                swap(nums, i, j - 1);
            }
            for (int s = i + 1, e = nums.length - 1; s < e; ++s, --e) {
                swap(nums, s, e);
            }
        }
        return output;
    }

    static int factorial(int n) {
        int result = 1;
        for (int i = 1; i <= n; i++) {
            result *= i;
        }
        return result;
    }

    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}