Skip to main content

14. Permutations

mediumAsked at Freshworks

Generate every ordering of a small set — Freshworks asks it to probe whether you can enumerate automation-rule firing orders cleanly.

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

Problem

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

Constraints

  • 1 <= nums.length <= 6
  • All numbers are distinct

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 = [1]
Output
[[1]]

Approaches

1. Brute force (insert into all positions)

Build permutations iteratively: for each new number, insert into every position of every existing permutation.

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

Tradeoff:

2. Backtracking with used flags

Recurse with a path and a used[] mask. At each level, try every unused number, recurse, then undo. Push when path.length === n.

Time
O(n! * n)
Space
O(n)
function permute(nums) {
  const out = [], used = new Array(nums.length).fill(false), path = [];
  function dfs() {
    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.pop(); used[i] = false;
    }
  }
  dfs();
  return out;
}

Tradeoff:

Freshworks-specific tips

Freshworks expects clean backtracking — they care that you mutate one shared array and undo on return rather than spraying new arrays at every recursive call.

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 Freshworks interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →