DevExCode

LeetCode 3437: Permutations III Solution

Master LeetCode problem 3437 (Permutations III), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

3437. Permutations III

Medium
ArrayBacktracking

Problem Explanation

Explanation

To solve this problem, we can use backtracking to generate all possible permutations of numbers from 1 to n without repeating the same number twice in a row. We will start with an empty list and recursively add numbers to it, keeping track of which numbers have been used already. At each step, we will check if the current number can be added to the list based on the constraint of not repeating the same number twice in a row. If a valid permutation is found, we will add it to the result list.

Algorithm

  1. Initialize an empty list permutations to store the valid permutations.
  2. Create a recursive function generatePermutations that takes parameters such as the current permutation, the current number, the total number of elements, and a set to keep track of used numbers.
  3. In the recursive function: a. Base case: If the current permutation's length is equal to the total number of elements, add it to the permutations list. b. Iterate over the numbers from 1 to n:
    • If the number is not used yet and not equal to the last number in the current permutation (if it exists), add it to the current permutation and recursively call the function with updated parameters.
  4. Call the generatePermutations function with initial parameters and return the permutations list.

Time Complexity

The time complexity of this algorithm is O(n!) as we are generating all possible permutations of the numbers from 1 to n.

Space Complexity

The space complexity of this algorithm is O(n) for the recursion stack where n is the total number of elements.

Solution Code

class Solution {
    public List<List<Integer>> permuteUnique(int n) {
        List<List<Integer>> permutations = new ArrayList<>();
        generatePermutations(new ArrayList<>(), n, new HashSet<>(), permutations);
        return permutations;
    }
    
    private void generatePermutations(List<Integer> current, int n, Set<Integer> used, List<List<Integer>> permutations) {
        if (current.size() == n) {
            permutations.add(new ArrayList<>(current));
            return;
        }
        
        for (int i = 1; i <= n; i++) {
            if (!used.contains(i) && (current.isEmpty() || i != current.get(current.size() - 1))) {
                current.add(i);
                used.add(i);
                generatePermutations(current, n, used, permutations);
                used.remove(i);
                current.remove(current.size() - 1);
            }
        }
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 3437 (Permutations III)?

This page provides optimized solutions for LeetCode problem 3437 (Permutations III) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3437 (Permutations III)?

The time complexity for LeetCode 3437 (Permutations III) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3437 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3437 in Java, C++, or Python.

Back to LeetCode Solutions