DSAPROB16 - Editorial

editorial
, ,
1

Problem Link - Sort Array by Parity

Problem Statement:

You are given an array of integers. Your task is to sort the array such that all odd numbers come before all even numbers while maintaining the original relative order of the odd and even numbers.

Approach:

The key idea to solve this problem is to split the array into two parts: one for odd numbers and one for even numbers. First, we count how many odd numbers are in the array, which helps us place them in the correct positions. Then, we traverse the array again, placing odd numbers at the beginning and even numbers after all the odd numbers. We use two pointers: one (left) starting at the beginning for odd numbers, and another (right) starting after the last odd number for even numbers. This ensures we maintain the relative order of both odd and even numbers in the array.

Step-by-step process:

  1. Count Odd Numbers:
    Traverse the array to count how many odd numbers there are. This helps determine where to place the even numbers.

  2. Initialize Two Pointers:
    Use two pointers: left to place odd numbers starting from the beginning, and right (starting after the odd count) to place even numbers.

  3. Traverse the Array Again:
    For each number:

    • Place odd numbers at the left pointer.
    • Place even numbers at the right pointer. Move the pointers accordingly.

  4. Update the Original Array:
    Once all numbers are placed, update the original array with the sorted result.

Time Complexity:
O(n), where n is the size of the array, since we traverse the array twice.

Space Complexity:
O(n), as we use an extra array to store the result.