Next Permutation Interview Question for Google

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 integer. 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.

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 100

Can you implement a function to solve this problem efficiently?

## Next Permutation

This problem asks us to find the next lexicographically greater permutation of an array of integers. If no such permutation exists, we must rearrange the array into ascending order. The solution should be performed in-place with constant extra memory.

### Brute Force Solution

A brute-force approach would involve generating all possible permutations of the array and then finding the next greater permutation in lexicographical order.  However, generating all permutations is highly inefficient, with a time complexity of O(n!), where n is the length of the array.  This makes it impractical for larger arrays.

### Optimal Solution

The optimal solution involves a clever algorithm that modifies the array in-place. Here's the breakdown:

1.  **Find the first decreasing element:**  Starting from the right, find the first element `nums[i]` that is smaller than `nums[i+1]`.  This indicates a potential point where we can swap elements to create a larger permutation.
2.  **Find the smallest element to the right to swap with:** Again, starting from the right, find the smallest element `nums[j]` that is greater than `nums[i]`. This is the element we'll swap with `nums[i]` to increase the permutation.
3.  **Swap:** Swap `nums[i]` and `nums[j]`.
4.  **Reverse the suffix:** Reverse the subarray starting from `nums[i+1]` to the end of the array.  This ensures that the suffix is in ascending order, resulting in the next lexicographically greater permutation.

If no decreasing element is found in step 1, it means the array is in descending order, and we simply reverse the entire array to get the smallest possible permutation (ascending order).

```python
def next_permutation(nums):
    """
    Finds the next permutation of an array of integers in-place.
    """
    n = len(nums)
    
    # 1. Find the first decreasing element from the right
    i = n - 2
    while i >= 0 and nums[i] >= nums[i+1]:
        i -= 1
    
    if i >= 0:
        # 2. Find the smallest element to the right of nums[i] that's greater than nums[i]
        j = n - 1
        while j >= 0 and nums[j] <= nums[i]:
            j -= 1
            
        # 3. Swap nums[i] and nums[j]
        nums[i], nums[j] = nums[j], nums[i]
    
    # 4. Reverse the suffix from i+1 to the end
    left = i + 1
    right = n - 1
    while left < right> 0:
        # Find the first element nums[i] that is smaller than its next element nums[i+1]
        i = len(nums) - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1

        if i >= 0:
            # Find the smallest element nums[j] to the right of nums[i] that is greater than nums[i]
            j = len(nums) - 1
            while j >= 0 and nums[j] <= nums[i]:
                j -= 1

            # Swap nums[i] and nums[j]
            nums[i], nums[j] = nums[j], nums[i]

        # Reverse the portion of the array after index i
        left = i + 1
        right = len(nums) - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

Example Walkthrough

Let's trace the algorithm with nums = [1, 2, 3]:

i starts at 1 (len(nums) - 2). nums[1] < nums[2] (2 < 3), so the loop stops. i = 1.
j starts at 2 (len(nums) - 1). nums[2] > nums[1] (3 > 2), so the loop stops. j = 2.
Swap nums[1] and nums[2]: nums becomes [1, 3, 2].
Reverse the suffix from index 2 to the end (just index 2 in this case, so no change).

Result: [1, 3, 2]

Let's consider nums = [3, 2, 1]:

i starts at 1. nums[1] >= nums[2] (2 >= 1), so i becomes 0. nums[0] >= nums[1] (3 >= 2), so i becomes -1. The loop terminates.
Since i < 0, we reverse the entire array. nums becomes [1, 2, 3].

Result: [1, 2, 3]

Big O Runtime Analysis

The algorithm consists of:

Finding the decreasing element: O(n) in the worst case.
Finding the element to swap: O(n) in the worst case.
Swapping: O(1).
Reversing the suffix: O(n/2) which is O(n).

Therefore, the overall time complexity is O(n).

Big O Space Usage Analysis

The algorithm operates in-place, meaning it only uses a constant amount of extra memory for variables like i, j, left, and right. The space complexity is therefore O(1), constant space.

Edge Cases and Handling

Empty array: The code handles an empty array gracefully because the loops won't execute.
Array with one element: The code also implicitly handles an array with one element, as no permutation is possible, and it will not change the array.
Array already in descending order: As shown in the example [3, 2, 1], the algorithm correctly reverses the array to produce the smallest permutation.
Array with duplicate elements: The algorithm works correctly even if the array has duplicate elements because the comparison operators (>= and <=) ensure the correct element is found for the swap. For example, the input [1, 1, 5] is correctly handled, and so is [1, 5, 1].