Skip to content

Seating Arrangements

Jump to bottom
Andrew Burke edited this page Aug 19, 2026 · 1 revision

TIP103 Unit 11 Session 2 (Click for link to problem statements)

Seating Arrangements

A photographer needs to try every left-to-right ordering of the distinct guests in nums for a group photo.

Return a list of all possible orderings; the order of the arrangements does not matter.

def permute(nums):
    pass

Example Usage:

print(permute([1, 2, 3]))

Example Output:

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-30 mins
  • 🛠️ Topics: Recursion, Backtracking, Permutations

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • Q: What exactly counts as an "ordering" of the guests?
    • A: A permutation — every guest appears exactly once, and two orderings are different if any guest sits in a different left-to-right position.
  • Q: Can the guest list contain duplicates?
    • A: No, the guests in nums are distinct, so we never have to worry about duplicate arrangements.
  • Q: Does the returned list need to be in a particular order?
    • A: No, the arrangements can be returned in any order; only the set of arrangements matters.
HAPPY CASE
Input: nums = [1, 2, 3]
Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Explanation: With 3 distinct guests there are 3! = 6 possible left-to-right orderings, and every one of them appears exactly once.

EDGE CASE
Input: nums = [7]
Output: [[7]]
Explanation: A single guest has exactly one possible arrangement — sitting alone.

Input: nums = [4, 9]
Output: [[4, 9], [9, 4]]
Explanation: Two guests can only swap seats, giving 2! = 2 arrangements.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Generating All Permutations, we want to consider the following approaches:

  • Backtracking: Build an arrangement one seat at a time, trying every remaining guest in the next open seat, then undoing the choice to explore other options. This is the classic pattern for "generate all possibilities" problems.
  • Recursion with a shrinking candidate pool: Each recursive call works with the guests not yet seated, so the base case is reached when no guests remain.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Fill the photo lineup one seat at a time from left to right. At each step, choose one of the guests who has not been seated yet, recurse to fill the remaining seats, then remove the guest (backtrack) so a different guest can be tried in that seat. When no guests remain, the current lineup is a complete arrangement and gets saved.

1) Initialize an empty `arrangements` list to collect completed orderings.
2) Define a helper `backtrack(current, remaining)`:
   a) Base case: if `remaining` is empty, append a copy of `current` to `arrangements` and return.
   b) For each guest in `remaining`:
      i)   Append the guest to `current` (seat them in the next open spot).
      ii)  Recurse with that guest removed from `remaining`.
      iii) Pop the guest from `current` to undo the choice before trying the next guest.
3) Call `backtrack([], nums)` to start with an empty lineup and all guests available.
4) Return `arrangements`.

⚠️ Common Mistakes

  • Appending current itself instead of a copy (current[:]), so every saved arrangement mutates into the same emptied list after backtracking.
  • Forgetting to pop the guest after the recursive call, which corrupts the lineup for the sibling branches.
  • Reusing a guest who is already seated because the "remaining" pool wasn't shrunk correctly, producing arrangements with repeated guests.

4: I-mplement

Implement the code to solve the algorithm.

def permute(nums):
    arrangements = []

    def backtrack(current, remaining):
        # Base case: no guests left to place, so the arrangement is complete
        if not remaining:
            arrangements.append(current[:])
            return
        # Try each remaining guest in the next open seat
        for i in range(len(remaining)):
            current.append(remaining[i])
            backtrack(current, remaining[:i] + remaining[i + 1:])
            current.pop()  # Undo the choice before trying the next guest

    backtrack([], nums)
    return arrangements

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Input: nums = [1, 2, 3]

    • Start: current = [], remaining = [1, 2, 3].
    • Seat guest 1 first: current = [1], then guest 2 → [1, 2], then guest 3 completes [1, 2, 3]. Backtrack and seat guest 3 second instead → [1, 3, 2].
    • Backtrack to the top and seat guest 2 first, yielding [2, 1, 3] and [2, 3, 1].
    • Backtrack again and seat guest 3 first, yielding [3, 1, 2] and [3, 2, 1].
    • Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] — all 3! = 6 arrangements, matching the example output.

  • Input: nums = [7]

    • The only guest is seated immediately and remaining becomes empty.
    • Output: [[7]]

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of guests in nums.

  • Time Complexity: O(N * N!) because there are N! permutations, and each one takes O(N) work to build and copy (the list slicing at each level also costs O(N)).
  • Space Complexity: O(N) auxiliary space for the recursion stack and the current lineup, not counting the O(N * N!) space occupied by the returned list of arrangements.

Clone this wiki locally