Next Permutation

Medium

Uber

1 view

Topics:

Arrays

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integers. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

For example, the next permutation of arr = [1,2,3] is [1,3,2].
Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.

The replacement must be in place and use only constant extra memory.

Examples:

Input: nums = [1,2,3] Output: [1,3,2]
Input: nums = [3,2,1] Output: [1,2,3]
Input: nums = [1,1,5] Output: [1,5,1]

Can you provide an algorithm to solve this problem?

Next Permutation

Medium

Uber

1 view

Topics:

Arrays

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integers. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

For example, the next permutation of arr = [1,2,3] is [1,3,2].
Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.

The replacement must be in place and use only constant extra memory.

Examples:

Input: nums = [1,2,3] Output: [1,3,2]
Input: nums = [3,2,1] Output: [1,2,3]
Input: nums = [1,1,5] Output: [1,5,1]

Can you provide an algorithm to solve this problem?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of integer values within the `nums` array? Can they be negative, zero, or only positive?
What should happen if the input array `nums` is empty or contains only one element?
If the input array is already in descending order (i.e., the largest possible permutation), should I sort it in ascending order and modify the array in-place, or is there a specific return value I should use to indicate that no next permutation exists?
Are there any duplicate numbers present in the `nums` array, and if so, how should they be handled when determining the next permutation?
Is the input guaranteed to be an array of integers, or do I need to handle other data types?

Brute Force Solution

Approach

The brute force approach to finding the next permutation is about trying every possible ordering. We explore all arrangements of the given numbers until we find one that is larger than the current order but still the smallest possible one.

Here's how the algorithm would work step-by-step:

First, we generate every single possible arrangement of the given numbers.
Then, we compare each arrangement with the original sequence.
If an arrangement is larger than the original sequence, we mark it as a potential candidate.
After going through all possible arrangements, we choose the smallest candidate from the larger arrangements. This is the next permutation.
If no arrangement is larger than the original sequence, then the original sequence was already the largest possible arrangement. In this case, the next permutation is the smallest possible arrangement: the numbers in ascending order.

Code Implementation

def next_permutation_brute_force(numbers):
    import itertools

    original_numbers = numbers.copy()
    all_permutations = list(itertools.permutations(numbers))
    larger_permutations = []

    for permutation in all_permutations:
        # Compare the current permutation with the original
        if permutation > tuple(original_numbers):
            larger_permutations.append(list(permutation))

    if not larger_permutations:
        # If no larger permutation exists, return sorted array
        numbers.sort()
        return numbers
    else:
        # Find the smallest permutation among the larger ones
        next_permutation_candidate = larger_permutations[0]
        for permutation in larger_permutations:
            if permutation < next_permutation_candidate:
                next_permutation_candidate = permutation

        return next_permutation_candidate

Big(O) Analysis

Time Complexity

O(n!) – The brute force approach generates all possible permutations of the input array of size n. Generating all permutations has a time complexity of O(n!). Then, for each permutation, we compare it with the original sequence, which takes O(n) time. We also need to find the smallest candidate from all larger permutations, which may require comparing all n! permutations. Therefore the dominating factor is the generation of permutations leading to O(n!) complexity.

Space Complexity

O(N!) – The brute force approach generates every possible permutation of the input array of size N. Storing all these permutations requires space proportional to the number of permutations, which is N!. Therefore, the algorithm needs to store N! different arrays to hold all possible permutations. Since the algorithm stores every possible arrangement, the auxiliary space used scales factorially with the input size N. This makes the space complexity O(N!).

Optimal Solution

Approach

The goal is to rearrange a set of numbers into the next arrangement that's bigger than the current one. We want to do this efficiently, without checking every possible order. Instead of brute force, we locate a strategic spot to make a small change, then optimize the rest.

Here's how the algorithm would work step-by-step:

Starting from the right side, find the first instance where a number is smaller than the number right next to it.
If you can't find any spot, it means the numbers are already in descending order from the end and should be rearranged from smallest to biggest, completing the process.
If you found a spot, now look on the right side again but try to find the smallest number that's still bigger than the number found in the first spot.
Swap these two numbers. This slightly increases the value of the number sequence.
Finally, the section of numbers after the first spot should be rearranged from smallest to biggest, ensuring that no other possibilities exist between the current sequence and the arrangement we just made.

Code Implementation

def next_permutation(numbers):
    index_to_swap = -1
    for i in range(len(numbers) - 2, -1, -1):
        if numbers[i] < numbers[i+1]:
            index_to_swap = i
            break

    # If no such index exists, reverse the array
    if index_to_swap == -1:
        numbers.reverse()
        return

    index_to_find_replacement = -1

    # Find the smallest number to the right of index_to_swap
    # that is still greater than numbers[index_to_swap]
    for i in range(len(numbers) - 1, index_to_swap, -1):
        if numbers[i] > numbers[index_to_swap]:
            index_to_find_replacement = i
            break

    # Swap the numbers
    numbers[index_to_swap], numbers[index_to_find_replacement] = numbers[index_to_find_replacement], numbers[index_to_swap]

    # Reverse the sub-array to the right of index_to_swap
    left_index = index_to_swap + 1
    right_index = len(numbers) - 1

    # Reverse the portion of the array after the swapped element
    while left_index < right_index:
        numbers[left_index], numbers[right_index] = numbers[right_index], numbers[left_index]
        left_index += 1
        right_index -= 1

Big(O) Analysis

Time Complexity

O(n) – The algorithm consists of scanning the input array of size n from right to left to find the first element that is smaller than its right neighbor, taking O(n) time. Next, another scan from right to left is performed to find the smallest element larger than the previously found element, again taking O(n) time. Then, these two elements are swapped, an O(1) operation. Finally, the subarray to the right of the first element found is reversed, which takes O(n) time. Since all operations are at most linear, the overall time complexity is O(n).

Space Complexity

O(1) – The algorithm operates in place, modifying the input array directly. It uses a few index variables to track positions during the search and swapping operations. These variables require constant space, independent of the size of the input array, denoted as N. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input array	Return immediately or throw an IllegalArgumentException since there's no permutation to compute.
Array with one element	Return immediately as the array is already in its only possible permutation.
Array is already in descending order (largest permutation)	Reverse the array to get the smallest (ascending) permutation.
Array contains duplicate numbers	The algorithm should correctly handle duplicates during the swap and reverse operations, finding the next lexicographical permutation even with duplicates.
Array contains all identical numbers	The algorithm should correctly identify that no greater permutation is possible and reverse the array into ascending order.
Array with very large numbers potentially causing integer overflow during comparisons	Use appropriate data types to avoid overflow and ensure comparisons are accurate, considering potential constraints in the problem description.
Maximum sized input array (performance considerations)	The algorithm has a time complexity of O(n) which is efficient enough, but profiling large inputs can confirm performance.
Array contains negative numbers	The algorithm will correctly sort the negative numbers and find the next permutation in lexicographical order.