Sort Array By Parity II Leetcode Solution

Difficulty Level Easy
Frequently asked in Amazon
algorithms Array coding Interview interviewprep LeetCode LeetCodeSolutions SortingViews 4006

Problem statement

In the problem ” Sort Array By Parity II,” we are given a parity array where all the elements are positive integers. The array contains an even number of elements. The array contains an equal number of even and odd elements.

Our task is to rearrange the elements of the array in such a way that parity[i] contains an even element when i is even otherwise parity[i] should contain an odd element and then return the new array.

Example

parity=[1,2,3,4]
[2,1,4,3]

Explanation:  All the possible array that satisfies the condition are: [2,1,4,3] , [2,3,4,1] ,[4,1,2,3] ,[4,3,2,1]. Anyone of these array is correct answer.

Approach for Sort Array By Parity II Leetcode Solution

The first and basic approach to this problem is to create a new array and then traversing the old array. When we encounter an even element then put it into the even position of the new array and when we encounter an odd element then put it into the odd position of the new array. This approach uses extra space and we can improve our logic using in place rearrangement.

Sort Array By Parity II Leetcode Solution

The idea is if we put all the even elements in an even position then odd elements will be automatically at an odd position. So we only need to focus on how to put even elements at even position.  We will follow these steps:

  1. Initialize variable i with 0 and j with 1. Here i will travel only even position so we will increment its value by 2 every time and j will travel only odd position so we will increment its value by 2 every time.
  2. If parity[i] is odd then we will find a j for which parity[j] is even and then we will swap elements at i and j.
  3. We will do these steps until the value of i is smaller than the length of the parity array.
  4. Return the parity array.

Implementation

C++ code for Sort Array By Parity II

#include <bits/stdc++.h> 
using namespace std; 
    vector<int> sortArrayByParityII(vector<int>& A) {
        int n =A.size();
        int j=1;
         for (int i = 0; i < n; i += 2)
            if (A[i] % 2 == 1) {
                while (A[j] % 2 == 1)
                    j += 2;
                swap(A[i],A[j]); 
            }

        return A;
    }
int main() 
{ 
 vector<int> arr = {1,2,3,4}; 
  vector<int>ans=sortArrayByParityII(arr); 
 for(int i=0;i<arr.size();i++)
 cout<<ans[i]<<" ";
 cout<<endl;
 return 0;
}
[2,1,4,3]

Java code for Sort Array By Parity II

import java.util.Arrays; 
public class Tutorialcup {
    public static int[] sortArrayByParityII(int[] A) {
        int n =A.length;
        int j=1;
         for (int i = 0; i < n; i += 2)
            if (A[i] % 2 == 1) {
                while (A[j] % 2 == 1)
                    j += 2;
               swap(A, i, j);
                }

        return A;
    }
     private static void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
  public static void main(String[] args) {
        int [] arr = {1,2,3,4}; 
        int[]ans=sortArrayByParityII(arr); 
        System.out.println(Arrays.toString(ans));
  }
}
[2,1,4,3]

Complexity Analysis of Sort Array By Parity II Leetcode Solution

Time complexity

The time complexity of the above code is O(n) because we are traversing the parity array only once. Here n is the length of the parity array.

Space complexity

The space complexity of the above code is O(1) because we are using only a variable to store answer.

References

Translate »