✅ 96.32%  Two-Pointer & One-Line
Interview Guide: "Sort Array By Parity" Problem\n\n## Problem Understanding\n\nThe "Sort Array By Parity" problem requires sorting an array of integers so that 
# Interview Guide: "Sort Array By Parity" Problem\n\n## Problem Understanding\n\nThe "Sort Array By Parity" problem requires sorting an array of integers so that all even integers come before all odd integers. While the order of even and odd numbers doesn\'t matter, the even numbers should always precede the odd numbers in the resultant array.\n\n## Key Points to Consider\n\n### 1. Understand the Constraints\n\nBefore diving into the solution, it\'s essential to understand the problem\'s constraints. The length of the array `nums` is between 1 and 5000, and the integers in `nums` are between 0 and 5000. This provides insight into feasible solutions in terms of time and space complexity.\n\n### 2. Two-Pointer Approach\n\nOne efficient method to solve this problem is to use two pointers, one starting from the beginning and the other from the end of the array. The idea is to swap elements whenever the left pointer points to an odd number, and the right pointer points to an even number.\n\n### 3. Pythonic List Comprehension\n\nPython provides a powerful feature called list comprehension that allows concise representation. It can be used to create two separate lists of even and odd numbers, which can then be concatenated.\n\n### 4. Explain Your Thought Process\n\nAlways articulate the rationale behind your approach. Explain why the two-pointer method is effective in in-place sorting and how Python\'s list comprehension provides a more readable solution.\n\n## Conclusion\n\nThe "Sort Array By Parity" problem showcases the importance of understanding array manipulation techniques. By using a two-pointer approach or leveraging Python\'s list comprehension, you can sort the array based on parity efficiently.\n\n---\n\n## Live Coding & Explain\nhttps://youtu.be/8_5SklDeD7U?si=8KBFl6ZPfCiPe4Vj\n\n# Approach 1: Two-Pointer Approach\n\nTo solve the "Sort Array By Parity" problem using the two-pointer approach:\n\n## Key Data Structures:\n\n- **i and j**: Two pointers initialized to the start and end of the array, respectively.\n\n## Enhanced Breakdown:\n\n1. **Initialization**:\n   - Initialize `i` to 0 and `j` to the last index of the array.\n   \n2. **While Loop**:\n   - Keep iterating until `i` is less than `j`.\n   - Increment `i` if the element at `i` is even.\n   - Decrement `j` if the element at `j` is odd.\n   - Swap the elements at `i` and `j` if the above conditions aren\'t met.\n\n3. **Return the Modified Array**:\n   - After the loop completes, the array will be sorted by parity.\n\n# Approach 2: Pythonic List Comprehension\n\nTo provide a more Pythonic solution:\n\n## Key Steps:\n\n1. **List Comprehension**:\n   - Use list comprehension to construct a list of even numbers and then a list of odd numbers.\n   \n2. **Concatenate Lists**:\n   - Concatenate the two lists to get the desired output.\n\n# Complexity:\n\n**Time Complexity (for both approaches):** \n- Both solutions involve traversing the array once, leading to a time complexity of $$ O(n) $$, where `n` is the length of the array `nums`.\n\n**Space Complexity (for the two-pointer approach):** \n- The space complexity is $$ O(1) $$ since the solution modifies the array in place and doesn\'t use any additional data structures that scale with the input size.\n\n**Space Complexity (for the list comprehension approach):** \n- The space complexity is $$ O(n) $$ since we create two new lists that scale with the input size.\n\n# Code Two-Pointer\n``` Python []\nclass Solution:\n    def sortArrayByParity(self, nums: List[int]) -> List[int]:\n        i, j = 0, len(nums) - 1\n        \n        while i < j:\n            while i < j and nums[i] % 2 == 0:\n                i += 1\n            while i < j and nums[j] % 2 == 1:\n                j -= 1\n            \n            nums[i], nums[j] = nums[j], nums[i]\n        \n        return nums\n```\n``` Go []\nfunc sortArrayByParity(nums []int) []int {\n    i, j := 0, len(nums) - 1\n    \n    for i < j {\n        for i < j && nums[i] % 2 == 0 {\n            i++\n        }\n        for i < j && nums[j] % 2 == 1 {\n            j--\n        }\n        \n        nums[i], nums[j] = nums[j], nums[i]\n    }\n    \n    return nums\n}\n```\n``` Rust []\nimpl Solution {\n    pub fn sort_array_by_parity(nums: Vec<i32>) -> Vec<i32> {\n        let mut nums = nums;\n        let mut i = 0;\n        let mut j = nums.len() - 1;\n        \n        while i < j {\n            while i < j && nums[i] % 2 == 0 {\n                i += 1;\n            }\n            while i < j && nums[j] % 2 == 1 {\n                j -= 1;\n            }\n            \n            nums.swap(i, j);\n        }\n        \n        nums\n    }\n}\n```\n``` C++ []\nclass Solution {\npublic:\n    std::vector<int> sortArrayByParity(std::vector<int>& nums) {\n        int i = 0, j = nums.size() - 1;\n        \n        while (i < j) {\n            while (i < j && nums[i] % 2 == 0)\n                i++;\n            while (i < j && nums[j] % 2 == 1)\n                j--;\n            \n            std::swap(nums[i], nums[j]);\n        }\n        \n        return nums;\n    }\n};\n```\n``` Java []\npublic class Solution {\n    public int[] sortArrayByParity(int[] nums) {\n        int i = 0, j = nums.length - 1;\n        \n        while (i < j) {\n            while (i < j && nums[i] % 2 == 0)\n                i++;\n            while (i < j && nums[j] % 2 == 1)\n                j--;\n            \n            int temp = nums[i];\n            nums[i] = nums[j];\n            nums[j] = temp;\n        }\n        \n        return nums;\n    }\n}\n```\n``` PHP []\nclass Solution {\n    function sortArrayByParity($nums) {\n        $i = 0;\n        $j = count($nums) - 1;\n        \n        while ($i < $j) {\n            while ($i < $j && $nums[$i] % 2 == 0)\n                $i++;\n            while ($i < $j && $nums[$j] % 2 == 1)\n                $j--;\n            \n            list($nums[$i], $nums[$j]) = array($nums[$j], $nums[$i]);\n        }\n        \n        return $nums;\n    }\n}\n```\n``` JavaScript []\nvar sortArrayByParity = function(nums) {\n    let i = 0, j = nums.length - 1;\n    \n    while (i < j) {\n        while (i < j && nums[i] % 2 === 0)\n            i++;\n        while (i < j && nums[j] % 2 === 1)\n            j--;\n        \n        [nums[i], nums[j]] = [nums[j], nums[i]];\n    }\n    \n    return nums;\n};\n```\n``` C# []\npublic class Solution {\n    public int[] SortArrayByParity(int[] nums) {\n        int i = 0, j = nums.Length - 1;\n        \n        while (i < j) {\n            while (i < j && nums[i] % 2 == 0)\n                i++;\n            while (i < j && nums[j] % 2 == 1)\n                j--;\n            \n            int temp = nums[i];\n            nums[i] = nums[j];\n            nums[j] = temp;\n        }\n        \n        return nums;\n    }\n}\n```\n\n# Code List Comprehension\n``` Python []\nclass Solution:\n    def sortArrayByParity(self, nums: List[int]) -> List[int]:\n        return [x for x in nums if x % 2 == 0] + [x for x in nums if x % 2 == 1]\n```\n\n## Performance\n\nCertainly! Here\'s the data sorted by time (in ms) and presented in a markdown table format:\n\n| Language   | Execution Time (ms) | Memory Usage (MB) |\n|------------|---------------------|-------------------|\n| Rust       | 0                   | 2.4               |\n| Java       | 1                   | 44                |\n| Go         | 9                   | 4.8               |\n| C++        | 9                   | 16.5              |\n| PHP        | 22                  | 20.2              |\n| JavaScript | 62                  | 44.2              |\n| Python3    | 70                  | 16.9              |\n| C#         | 135                 | 46.5              |\n\n![v2.png](https://assets.leetcode.com/users/images/e43f7554-42c2-4347-8320-862dfbde5570_1695862172.851938.png)\n\n\nThe "Sort Array By Parity" problem is a classic example of array manipulation problems that can be approached in various ways. The choice of solution often depends on the trade-offs between readability, space, and efficiency. \uD83D\uDE80\uD83E\uDDE0\uD83D\uDC69\u200D\uD83D\uDCBB\uD83D\uDC68\u200D\uD83D\uDCBB.
['PHP', 'C++', 'Java', 'Go', 'Python3', 'Rust', 'JavaScript', 'C#']