Solution Explanation: Sort Array By Parity

This problem asks to rearrange an integer array such that all even numbers come before all odd numbers. The order within even and odd numbers doesn't matter. We can efficiently solve this using a two-pointer approach.

Algorithm (Two Pointers):

1. Initialization: Initialize two pointers, left (pointing to the beginning of the array) and right (pointing to the end of the array).

2. Iteration: While left is less than right:

   • If nums[left] is even, increment left. We've found an even number in the correct position.
   • If nums[right] is odd, decrement right. We've found an odd number in the correct position.
   • If nums[left] is odd and nums[right] is even, we've found a pair that needs swapping. Swap nums[left] and nums[right], then increment left and decrement right.

3. Return: The array nums is now sorted with even numbers followed by odd numbers. Return nums.

Time Complexity: O(N), where N is the length of the input array. In the worst case, we iterate through the array once.

Space Complexity: O(1). We use only a constant amount of extra space for the pointers.

Code Implementation (Python):

class Solution:
    def sortArrayByParity(self, nums: List[int]) -> List[int]:
        left, right = 0, len(nums) - 1
        while left < right:
            if nums[left] % 2 == 0:  # Even number in correct place
                left += 1
            elif nums[right] % 2 == 1:  # Odd number in correct place
                right -= 1
            else:  # Odd and even numbers in wrong places - swap
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1
        return nums

Code Implementation (Java):

class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            if (nums[left] % 2 == 0) {
                left++;
            } else if (nums[right] % 2 == 1) {
                right--;
            } else {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
                right--;
            }
        }
        return nums;
    }
}

(Other Languages - C++, Go, TypeScript, Rust, JavaScript): The implementations in other languages follow the same logic, only differing in syntax. Refer to the provided code snippets in the original response for these examples. The core algorithm remains the same.