Leetcode 905 - Sort Array by Parity (Easy) - C++ Code With Explanation

          

Leetcode 905 - Sort Array by Parity (Easy)

Problem- https://leetcode.com/problems/sort-array-by-parity

Approach-

This can be solved using two methods of brute force that use extra space and the other one is by using two pointers. 

For the first method we just have to take an empty vector and iterate the given array twice, in the first traversal push back all the even numbers to our final array and then in the second traversal push back all the odd numbers.

For the second method take two pointers i and j at the starting and the ending indices of the given array respectively. Now there can be four cases.

Case 1 nums[i] is odd and nums[j] is odd
Just decrease j as it has the correct element i.e. an odd element at the end side of the array. 
Case 2 nums[i] is odd and nums[j] is even
Swap nums[i] and nums[j]. Now both are at correct sides, so do i++ and j--.
Case 3 nums[i] is even and nums[j] is even
Both are at correct sides, so do i++ and j--.
Just increase i as it has the correct element i.e. an even element at the front side of the array. 
Case 4 nums[i] is even and nums[j] is odd

Code-

vector<int> sortArrayByParity(vector<int>& a) { int n=a.size(); int i=0; int j=n-1; while(i<j) { if(a[i]%2==0&&a[j]%2==1) { i++; j--; } else if(a[i]%2==1&&a[j]%2==0) { swap(a[i], a[j]); i++; j--; } else if(a[i]%2==1&&a[j]%2==1) { j--; } else { i++; } } return a; }

Link to All Problemset Solutions