What is the time complexity of Permutations II?

The optimal solution has a time complexity of O(n!).

What data structures are used to solve Permutations II?

This problem uses Array, Backtracking, Sorting. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Permutations II?

Insight 1: The core of the solution is using backtracking to explore all possible permutations. Insight 2: To avoid duplicate permutations when the input contains duplicate numbers, we need to sort the input array first and then skip over duplicate numbers during the backtracking process if the previous occurrence of that number has not been used in the current permutation.

Which companies ask LeetCode 47. Permutations II in interviews?

This problem is frequently asked at Adobe, Amazon, Apple, Bloomberg, Citadel and 4 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Permutations II - LeetCode 47 Solution

Q: How to solve Permutations II?

The provided solution uses a backtracking algorithm to generate all possible permutations. To handle duplicates effectively, the input array is first sorted. During the backtracking process, a 'used' array is maintained to track which numbers have been included in the current permutation. Crucially, before considering a number at index `i`, we check if it's the same as the previous number at `i-1`, and if the previous number hasn't been used yet. If both are true, we skip the current number to prevent generating duplicate permutations. This is the core optimization for handling duplicates.

Permutations II - Complete Solution Guide

Permutations II is LeetCode problem 47, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given a collection of numbers, nums , that might contain duplicates, return all possible unique permutations in any order . Example 1: Input: nums = [1,1,2] Output: [[1,1,2], [1,2,1], [2,1,1]] Example 2: Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] Constraints: 1 <= nums.length <= 8 -10 <= nums[i] <= 10

Detailed Explanation

The problem asks us to find all unique permutations of a given list of numbers which might contain duplicates. A permutation is an arrangement of the elements in a specific order. The 'unique' part means we should not include the same permutation more than once in our result. For example, if the input is [1, 1, 2], the output should be [[1, 1, 2], [1, 2, 1], [2, 1, 1]]. The order of the permutations in the output doesn't matter. The constraints tell us the input array's length will be between 1 and 8, and each number in the array will be between -10 and 10.

Solution Approach

The provided solution uses a backtracking algorithm to generate all possible permutations. To handle duplicates effectively, the input array is first sorted. During the backtracking process, a 'used' array is maintained to track which numbers have been included in the current permutation. Crucially, before considering a number at index `i`, we check if it's the same as the previous number at `i-1`, and if the previous number hasn't been used yet. If both are true, we skip the current number to prevent generating duplicate permutations. This is the core optimization for handling duplicates.

Step-by-Step Algorithm

Step 1: Sort the input array `nums`. This is necessary for the duplicate handling logic to work correctly.
Step 2: Initialize an empty list `results` to store the unique permutations.
Step 3: Initialize a boolean array `used` of the same length as `nums`, initialized to all `false`. This array will track which numbers are currently in the path.
Step 4: Define a recursive backtracking function `backtrack(path)`:
Step 5: If the length of the current `path` is equal to the length of `nums`, it means we have a complete permutation. Add a copy of `path` to `results` and return.
Step 6: Iterate through the numbers in `nums` using a loop from `i = 0` to `n-1`:
Step 7: If `used[i]` is `true`, it means `nums[i]` is already in the current `path`, so continue to the next number.
Step 8: If `i > 0` and `nums[i] == nums[i-1]` and `!used[i-1]`, it means the current number is a duplicate of the previous one, and the previous one hasn't been used in the current path. Skip this number to avoid duplicate permutations.
Step 9: Mark `used[i]` as `true` to indicate that we are now using `nums[i]` in the current `path`.
Step 10: Append `nums[i]` to the current `path`.
Step 11: Recursively call `backtrack(path)`.
Step 12: Remove the last element from `path` (backtrack) and set `used[i]` back to `false` to explore other possibilities.
Step 13: Call the `backtrack` function with an empty initial path.
Step 14: Return the `results` list containing all unique permutations.

Key Insights

Insight 1: The core of the solution is using backtracking to explore all possible permutations.
Insight 2: To avoid duplicate permutations when the input contains duplicate numbers, we need to sort the input array first and then skip over duplicate numbers during the backtracking process if the previous occurrence of that number has not been used in the current permutation.
Insight 3: The `used` array is crucial for tracking which numbers have already been included in the current permutation being built.

Complexity Analysis

Time Complexity: O(n!)

Space Complexity: O(n!)

Topics

This problem involves: Array, Backtracking, Sorting.

Companies

Asked at: Adobe, Amazon, Apple, Bloomberg, Citadel, LinkedIn, Meta, Microsoft, TikTok.

Permutations II | LeetCode 47

Medium

Array Backtracking Sorting

Time: O(n!)Space: O(n!)

Solution Code

Available in:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        boolean[] used = new boolean[n];

        List<Integer> path = new ArrayList<>();

        backtrack(nums, used, path, results, n);
        return results;
    }

    private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> results, int n) {
        if (path.size() == n) {
            results.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < n; i++) {
            if (used[i]) {
                continue;
            }

            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }

            used[i] = true;
            path.add(nums[i]);

            backtrack(nums, used, path, results, n);

            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 47: Permutations II - Detailed explanation and solution approaches.

Topics

Array Backtracking Sorting

Companies

AdobeAmazonAppleBloombergCitadelLinkedInMetaMicrosoft

Stats

Difficulty:Medium

Languages:4

Companies:9

Problem #:47

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

14 steps

1
Step 1: Sort the input array `nums`. This is necessary for the duplicate handling logic to work correctly.
2
Step 2: Initialize an empty list `results` to store the unique permutations.
3
Step 3: Initialize a boolean array `used` of the same length as `nums`, initialized to all `false`. This array will track which numbers are currently in the path.
4
Step 4: Define a recursive backtracking function `backtrack(path)`:
5
Step 5: If the length of the current `path` is equal to the length of `nums`, it means we have a complete permutation. Add a copy of `path` to `results` and return.
6
Step 6: Iterate through the numbers in `nums` using a loop from `i = 0` to `n-1`:
7
Step 7: If `used[i]` is `true`, it means `nums[i]` is already in the current `path`, so continue to the next number.
8
Step 8: If `i > 0` and `nums[i] == nums[i-1]` and `!used[i-1]`, it means the current number is a duplicate of the previous one, and the previous one hasn't been used in the current path. Skip this number to avoid duplicate permutations.
9
Step 9: Mark `used[i]` as `true` to indicate that we are now using `nums[i]` in the current `path`.
10
Step 10: Append `nums[i]` to the current `path`.
11
Step 11: Recursively call `backtrack(path)`.
12
Step 12: Remove the last element from `path` (backtrack) and set `used[i]` back to `false` to explore other possibilities.
13
Step 13: Call the `backtrack` function with an empty initial path.
14
Step 14: Return the `results` list containing all unique permutations.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n!)

💾

Space Complexity

O(n!)

📝

Why?

The time complexity is derived from the fact that there are at most n! permutations. The backtracking algorithm essentially generates these permutations, so we must spend at least O(n!) time to even list all the permutations. The space complexity is determined by the number of unique permutations possible, which can grow up to n! In addition, we use auxiliary space to store the `used` array and the current `path` during recursion.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Iterative Approach using Heap's Algorithm

Heap's Algorithm is an iterative algorithm to generate all permutations. It can be modified to handle duplicate elements with some extra checks.

Time: O(n!)Space: O(n)

Trade-offs: The iterative approach avoids recursion, potentially saving on stack space. However, the implementation can be more complex than the recursive backtracking approach.

✨

Key Insights

1Insight 1: The core of the solution is using backtracking to explore all possible permutations.
2Insight 2: To avoid duplicate permutations when the input contains duplicate numbers, we need to sort the input array first and then skip over duplicate numbers during the backtracking process if the previous occurrence of that number has not been used in the current permutation.
3Insight 3: The `used` array is crucial for tracking which numbers have already been included in the current permutation being built.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Sorting

Arranging elements in a specific order (ascending/descending).

Edge Cases

Edge case 1: Empty input array `nums = []`. The solution will correctly return an empty list of permutations.
Edge case 2: Input array with only one element `nums = [5]`. The solution will return a list containing a single permutation: `[[5]]`.
Edge case 3: Input array with all duplicate elements `nums = [1, 1, 1]`. The solution will correctly return a list containing only one permutation: `[[1, 1, 1]]`.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to sort the input array when handling duplicates. Without sorting, the duplicate skipping logic won't work correctly, and the algorithm will generate duplicate permutations.

✗Common mistake 2: Incorrectly implementing the duplicate skipping condition. The condition `i > 0 and nums[i] == nums[i-1] and used[i-1]` is incorrect. It should be `!used[i-1]` not `used[i-1]` because we only want to skip if the previous element wasn't used *in the current path*. If the previous element was used, it must mean that the previous element belongs earlier in the sequence and therefore this is a valid permutation.

✗Common mistake 3: Not creating a *copy* of the current path before adding it to the results. Modifying the `path` after adding it to the `results` will change the permutation that was already added.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Generating password combinations. If you have a set of characters and need to generate all possible password combinations of a certain length, a permutation algorithm can be used. The constraint of unique permutations is relevant to avoid generating identical passwords.

🏦Real-world scenario 2: Task scheduling. You might have a set of tasks to be performed, and you need to find all possible orders in which the tasks can be executed. Permutations can help you explore different schedules, and constraints can be added to handle task dependencies or priorities.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 18, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 13

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 6

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How do I avoid duplicate solutions in backtracking?

Sort the input first, then skip consecutive duplicates at the same recursion level: if (i > start && nums[i] == nums[i-1]) continue. For permutations, use a visited array or swap-based approach. Always consider if order matters (permutations vs combinations).

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Permutations II"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether backtracking techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?