Leetcode 905. Sort Array By Parity

Problem Explanation

The problem is asking to return an array where all the even numbers come first, then all the odd numbers. Any possible combination of this condition is accepted.

For instance, if you have an array [3,1,2,4]. You can return [2,4,3,1], [4,2,3,1], [2,4,1,3], [4,2,1,3] etc. All of these have even numbers at the beginning, and odd numbers following the even numbers.

To solve this problem, we'll use a two-pointer approach. We initialize two pointers, one at the beginning of the array and one at the end. Then we start checking elements.

If the one at the beginning is odd and the one at the end is even, we swap them. If the one at the beginning is even, we move the pointer to the right. If the one at the end is odd, we move the pointer to the left. We continue this process until the two pointers meet.

Solution

Python

1
2python
3class Solution:
4    def sortArrayByParity(self, nums):
5        l = 0
6        r = len(nums) - 1
7
8        while l < r:
9            if nums[l] % 2 == 1 and nums[r] % 2 == 0:
10                nums[l], nums[r] = nums[r], nums[l]
11
12            if nums[l] % 2 == 0:
13                l += 1
14            if nums[r] % 2 == 1:
15                r -= 1
16
17        return nums

Java

1
2java
3class Solution {
4    public int[] sortArrayByParity(int[] nums) {
5        int l = 0;
6        int r = nums.length - 1;
7
8        while (l < r) {
9            if (nums[l] % 2 == 1 && nums[r] % 2 == 0) {
10                int temp = nums[l];
11                nums[l] = nums[r];
12                nums[r] = temp;
13            }
14
15            if (nums[l] % 2 == 0)
16                l++;
17            if (nums[r] % 2 == 1)
18                r--;
19        }
20
21        return nums;
22    }
23}

JavaScript

1
2javascript
3class Solution {
4    sortArrayByParity(nums) {
5        let l = 0;
6        let r = nums.length - 1;
7
8        while (l < r) {
9            if (nums[l] % 2 == 1 && nums[r] % 2 == 0) {
10                [nums[l], nums[r]] = [nums[r], nums[l]];
11            }
12
13            if (nums[l] % 2 == 0)
14                l++;
15            if (nums[r] % 2 == 1)
16                r--;
17        }
18
19        return nums;
20    }
21}

C++

1
2cpp
3class Solution {
4public:
5    vector<int> sortArrayByParity(vector<int>& nums) {
6        int l = 0;
7        int r = nums.size() - 1;
8
9        while (l < r) {
10            if (nums[l] % 2 == 1 && nums[r] % 2 == 0)
11                swap(nums[l], nums[r]);
12
13            if (nums[l] % 2 == 0)
14                l++;
15            if (nums[r] % 2 == 1)
16                r--;
17        }
18
19        return nums;
20    }
21};

C#

1
2csharp
3public class Solution {
4    public int[] SortArrayByParity(int[] nums) {
5        int l = 0;
6        int r = nums.Length - 1;
7
8        while (l < r) {
9            if (nums[l] % 2 == 1 && nums[r] % 2 == 0) {
10                int temp = nums[l];
11                nums[l] = nums[r];
12                nums[r] = temp;
13            }
14
15            if (nums[l] % 2 == 0)
16                l++;
17            if (nums[r] % 2 == 1)
18                r--;
19        }
20
21        return nums;
22    }
23}

Understanding the Code

To solve the problem, the code follows a straightforward logic, comparing the values of two pointers, one at the start of the array and one at the end. The code continues until the two pointers meet, ultimately resulting in an array where all even numbers precede the odd numbers.

If the number at the beginning pointer is odd and the number at the end pointer is even, the code will swap the numbers and move the start pointer to the right and the end pointer to the left. If the number at the beginning pointer is even, the code will simply move the start pointer to the right. Similarly, if the number at the end pointer is odd, the code will move the end pointer to the left.

Thus, in Python, Java, JavaScript, C++, and C#, the code follows this principle and logic. Furthermore, the code can be easily modified according to the conditions of other questions, thereby making it applicable in many scenarios.

It's important to note that the code returns an array in O(n) time complexity and O(1) space complexity, making it efficient to solve this problem.

That's all the explanation needed to understand the given solutions. Happy Coding!!


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫