Skip to main content

22. Permutations

mediumAsked at Gojek

Return all possible permutations of an array of distinct integers.

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

Problem

Given an array nums of distinct integers, return all the 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. Insert-everywhere

Start from [[]] and for each new number insert it at every position in every existing permutation.

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

Tradeoff:

2. Backtracking with used set

Recurse picking each unused element and pushing on a current path; when path length equals n, emit a copy.

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

Gojek-specific tips

Gojek likes the disciplined push/pop pattern because dispatcher routing simulations explore permutations of driver-assignments in the same shape.

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

Practice these live with InterviewChamp.AI →