You are given a list of integers. Modify the list in-place such that all even numbers appear at the beginning of the list and all odd numbers appear at the end. The relative order of even numbers and odd numbers does not matter.

For example:

If the input list is [3, 1, 2, 4, 6, 7], a valid output would be [2, 4, 6, 3, 1, 7]. Another valid output would be [4, 2, 6, 1, 3, 7]. The even numbers (2, 4, 6) are at the beginning, and the odd numbers (3, 1, 7) are at the end.
If the input list is [1, 3, 5, 7], the output should be [1, 3, 5, 7] since all numbers are already odd.
If the input list is [2, 4, 6, 8], the output should be [2, 4, 6, 8] since all numbers are already even.
If the input list is [], the output should be [].

Write a function that takes a list of integers as input and modifies it in-place to satisfy these conditions. Your solution should be efficient, ideally completing the modification in O(n) time complexity and O(1) space complexity.

Problem: Modify List In-Place

Naive Solution

A naive solution would be to create two new lists, one for even numbers and one for odd numbers. Then, concatenate the two lists. However, this would not be an in-place modification and would require O(n) extra space.

def modify_list_naive(nums):
    even_nums = []
    odd_nums = []
    for num in nums:
        if num % 2 == 0:
            even_nums.append(num)
        else:
            odd_nums.append(num)
    return even_nums + odd_nums

Optimal Solution

The optimal solution uses the two-pointer approach. We maintain two pointers, left and right, initialized to the start and end of the list, respectively. We move the left pointer to the right until we find an odd number. We move the right pointer to the left until we find an even number. If left is less than right, we swap the elements at the left and right pointers. We repeat this process until left and right cross each other.

def modify_list_inplace(nums):
    left = 0
    right = len(nums) - 1

    while left < right:
        # Find the next odd number from the left
        while left < len(nums) and nums[left] % 2 == 0:
            left += 1

        # Find the next even number from the right
        while right >= 0 and nums[right] % 2 != 0:
            right -= 1

        # If left and right pointers haven't crossed, swap
        if left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

    return nums

Big(O) Run-Time Analysis

The optimal solution has a time complexity of O(n), where n is the length of the list. This is because we iterate through the list at most once.

The while loop while left < len(nums) and nums[left] % 2 == 0: can, at most, iterate through every even number in the list. Similarly, the while loop while right >= 0 and nums[right] % 2 != 0: can, at most, iterate through every odd number in the list. Therefore, these loops, in total, can execute a maximum of n times.

Big(O) Space Usage Analysis

The optimal solution has a space complexity of O(1), which means it uses constant extra space. We are modifying the list in-place, so we are not creating any new lists or data structures that depend on the input size. We are only using a few extra variables (left, right) to store indices, which takes constant space.

Edge Cases

Empty List: If the input list is empty, the function should return the empty list without any modification.
List with only even numbers: If the input list contains only even numbers, the function should return the list as is.
List with only odd numbers: If the input list contains only odd numbers, the function should return the list as is.

These cases are handled correctly by the provided code because the while loops will simply stop when left and right cross each other without performing any swaps.

How can you modify a list in-place to move even numbers to the front and odd numbers to the end efficiently, without preserving relative order?