Skip to main content

47. Permutations

mediumAsked at Ola

Return all possible permutations of a distinct integer array.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an array nums of distinct integers, return all possible permutations. You can return the answer in any order.

Constraints

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • All integers are unique

Examples

Example 1

Input
nums = [1,2,3]
Output
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2

Input
nums = [0,1]
Output
[[0,1],[1,0]]

Approaches

1. Iterative insertion

Build perms by inserting each number into every position of existing perms.

Time
O(n!)
Space
O(n!)
let out = [[]];
for (const x of nums) {
  const next = [];
  for (const p of out)
    for (let i=0;i<=p.length;i++) next.push([...p.slice(0,i), x, ...p.slice(i)]);
  out = next;
}
return out;

Tradeoff:

2. DFS with used flags

Recurse picking each unused index; backtrack the flag and path.

Time
O(n!)
Space
O(n)
function permute(nums) {
  const out = [], used = Array(nums.length).fill(false);
  const dfs = (path) => {
    if (path.length === nums.length) { out.push([...path]); return; }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true; path.push(nums[i]);
      dfs(path);
      used[i] = false; path.pop();
    }
  };
  dfs([]);
  return out;
}

Tradeoff:

Ola-specific tips

Ola uses this to test that backtracking is muscle memory; tie it to enumerating dispatcher try-orders for a small driver pool.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Permutations and other Ola interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →