Skip to main content

Two Pointer

Sort Array By Parity II Solution In C++/Java/Python/JS

Sort Array By Parity II Problem Description:

Given an array of integers nums, half of the integers in nums are odd, and the other half are even.
Sort the array so that whenever nums[i] is odd, i is odd, and whenever nums[i] is even, i is even.Return any answer array that satisfies this condition.
Sort Array By Parity II-Problem-Description

Examples:

Input: nums = [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

Input: nums = [2,3]
Output: [2,3]

Constraints:

2 <= nums.length <= 2 * 10⁴
nums.length is even.
Half of the integers in nums are even.
0 <= nums[i] <= 1000

Brute Force Approach

What’s the first thing that comes to mind when we see this problem?

So, you’re given an array where half of the numbers are even and half are odd, and the task is to rearrange them such that all even numbers sit at even indices and odd numbers sit at odd indices.

At first glance, this feels like one of those puzzles where you have a jumbled row of red and blue balls, and you have to place all reds in even spots and blues in odd ones — without changing how many of each you have.

For example, look at this input:
[4, 2, 5, 7]

Now, positions 0 and 2 are even indices, so they must hold even numbers like 4, 2, etc.
And positions 1 and 3 are odd indices, so they must hold odd numbers like 5, 7, etc.

In the example above, [4, 5, 2, 7] would work because:

  • Index 0 → 4 (even)
  • Index 1 → 5 (odd)
  • Index 2 → 2 (even)
  • Index 3 → 7 (odd)

Perfect! So, how do we reach such an arrangement? That’s where the brute force idea kicks in.

The goal is to scan each index of the array and make sure it follows the rule:

  • If the index is even, the number must also be even
  • If the index is odd, the number must also be odd

If it doesn’t? Well, we go looking for a number that should be at this index and swap it in.

Alright, picture this: you're walking through the array from left to right. At each step, you're asking:

"Hey, does this index have the right number type? Like, is this an even index with an even number, or an odd index with an odd number?"

If yes — awesome! You move on.

But what if it doesn't?
Let’s say you're at index 0 (an even index), and the number there is 5 (which is odd ). That’s a mismatch.

You start scanning ahead — from index 1 onward — until you find another even number (since 5 doesn’t belong here), and once you find it, you swap it with 5.

That fixes index 0 — nice!

Now you move on to the next index. If it’s index 1 (odd), and it contains an even number like 4 — another mismatch!
Again, you scan ahead to find an odd number, then swap.

This is what we do throughout the array:

  • If the index and number mismatch, we search ahead for a number that does belong there.
  • Once found, we swap them.

In short,

We look at each position in the array one by one.

If a number is sitting in the wrong spot (like an odd number at an even index), we search ahead to find a number that should be here.

Once we find it, we swap the two to fix the mistake.

We keep doing this until every number is in the right place.

💡
Try it Yourself!

Let's understand with an example:

Sort Array By Parity II Example:

Take this input: [3, 2, 4, 1]

Let's go step by step:

  • Index 0 → 3 (odd) → should be even
    → Look ahead and find 4 at index 2 → swap → array becomes: [4, 2, 3, 1]
  • Index 1 → 2 (even) → should be odd
    → Look ahead and find 3 at index 2 → swap → array becomes: [4, 3, 2, 1]
  • Index 2 → 2 (even)
  • Index 3 → 1 (odd)

Boom! All done

Steps to Implement the Solution:

  • Get the size of the array nums and store it in n.
  • Loop through each index i from 0 to n - 1:
    • If i is even and nums[i] is odd → it's in the wrong spot.
      • Start a nested loop from j = i + 1 to n - 1.
      • Look for a number that is even.
      • When found, swap nums[i] and nums[j] to fix the mismatch.
    • If i is odd and nums[i] is even → also wrong.
      • Again, run a nested loop from j = i + 1 to n - 1.
      • Look for a number that is odd.
      • Swap nums[i] and nums[j].
  • Return the modified array.

Sort Array By Parity II Solution

Code Implementation / Leetcode solution of Sort Array By Parity II
1. Sort Array By Parity II solution in C++ Try on Compiler 
class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        // Get the size of the array
        int n = nums.size();

        // Traverse each index from 0 to n-1
        for(int i = 0; i < n; i++)
        {
            // Check if index is even but number is odd (invalid placement)
            if(i % 2 == 0 && nums[i] % 2 != 0)
            {
                // Find the next even number to swap
                for(int j = i + 1; j < n; j++)
                {
                    // If an even number is found
                    if(nums[j] % 2 == 0)
                    {
                        // Swap the elements to fix the mismatch
                        swap(nums[i], nums[j]);
                    }
                }
            }
            // Check if index is odd but number is even (invalid placement)
            else if(i % 2 != 0 && nums[i] % 2 == 0)
            {
                // Find the next odd number to swap
                for(int j = i + 1; j < n; j++)
                {
                    // If an odd number is found
                    if(nums[j] % 2 != 0)
                    {
                        // Swap the elements to fix the mismatch
                        swap(nums[i], nums[j]);
                    }
                }
            }
        }

        // Return the rearranged array
        return nums;
    }
};

2. Sort Array By Parity II solution in Java Try on Compiler 
class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        // Get the size of the array
        int n = nums.length;

        // Traverse each index from 0 to n-1
        for(int i = 0; i < n; i++) {
            // Check if index is even but number is odd (invalid placement)
            if(i % 2 == 0 && nums[i] % 2 != 0) {
                // Find the next even number to swap
                for(int j = i + 1; j < n; j++) {
                    // If an even number is found
                    if(nums[j] % 2 == 0) {
                        // Swap the elements to fix the mismatch
                        int temp = nums[i];
                        nums[i] = nums[j];
                        nums[j] = temp;
                    }
                }
            }
            // Check if index is odd but number is even (invalid placement)
            else if(i % 2 != 0 && nums[i] % 2 == 0) {
                // Find the next odd number to swap
                for(int j = i + 1; j < n; j++) {
                    // If an odd number is found
                    if(nums[j] % 2 != 0) {
                        // Swap the elements to fix the mismatch
                        int temp = nums[i];
                        nums[i] = nums[j];
                        nums[j] = temp;
                    }
                }
            }
        }

        // Return the rearranged array
        return nums;
    }
}

3. Sort Array By Parity II solution in Python Try on Compiler 
class Solution:
    def sortArrayByParityII(self, nums):

        # Get the size of the array
        n = len(nums)

        # Traverse each index from 0 to n-1
        for i in range(n):

            # Check if index is even but number is odd (invalid placement)
            if i % 2 == 0 and nums[i] % 2 != 0:

                # Find the next even number to swap
                for j in range(i + 1, n):

                    # If an even number is found
                    if nums[j] % 2 == 0:

                        # Swap the elements to fix the mismatch
                        nums[i], nums[j] = nums[j], nums[i]

            # Check if index is odd but number is even (invalid placement)
            elif i % 2 != 0 and nums[i] % 2 == 0:

                # Find the next odd number to swap
                for j in range(i + 1, n):

                    # If an odd number is found
                    if nums[j] % 2 != 0:
                        
                        # Swap the elements to fix the mismatch
                        nums[i], nums[j] = nums[j], nums[i]

        # Return the rearranged array
        return nums

4. Sort Array By Parity II solution in Javascript Try on Compiler 
var sortArrayByParityII = function(nums) {
    // Get the size of the array
    let n = nums.length;

    // Traverse each index from 0 to n-1
    for(let i = 0; i < n; i++) {

        // Check if index is even but number is odd (invalid placement)
        if(i % 2 === 0 && nums[i] % 2 !== 0) {

            // Find the next even number to swap
            for(let j = i + 1; j < n; j++) {

                // If an even number is found
                if(nums[j] % 2 === 0) {

                    // Swap the elements to fix the mismatch
                    [nums[i], nums[j]] = [nums[j], nums[i]];
                }
            }
        }

        // Check if index is odd but number is even (invalid placement)
        else if(i % 2 !== 0 && nums[i] % 2 === 0) {

            // Find the next odd number to swap
            for(let j = i + 1; j < n; j++) {

                // If an odd number is found
                if(nums[j] % 2 !== 0) {
                    
                    // Swap the elements to fix the mismatch
                    [nums[i], nums[j]] = [nums[j], nums[i]];
                }
            }
        }
    }

    // Return the rearranged array
    return nums;
};

Sort Array By Parity II Complexity Analysis

Time Complexity: O(n²)

We're going through the array using a nested loop setup.

  • Outer Loop runs for each index i from 0 to n - 1 → O(n)
  • For some mismatched positions, the inner loop starts from j = i + 1 to n - 1 to find a correct number to swap.

In the worst case, every element is in the wrong position.
That means for almost every i, we enter the inner loop and may scan nearly the whole remaining part of the array to find the correct number.

So effectively:

  • Outer loop: O(n)
  • Inner loop (worst case): O(n)

Hence, total time complexity is: O(n²)

Time Complexity: O(n²)

Space Complexity: O(n)

  1. Auxiliary Space Complexity: O(1)
    Auxiliary space refers to the additional memory the algorithm requires, excluding the space occupied by the input.
    The extra space used — such as loop variables and temporary variables for swapping — are all primitive types and do not depend on the input size.
    Therefore, the auxiliary space complexity is O(1).
  2. Total Space Complexity: O(n)
    Total space is the overall memory used by the algorithm, including both the input and any extra space needed during execution.
    Since we are modifying the input array in-place and not creating any significant new data structures, the overall space used is mainly the input array itself.
    The input array size is n, so the total space complexity is O(n).
    So, the total space complexity is O(n) due to the input grid.

Will Brute Force Work Against the Given Constraints? 

For the current solution, the time complexity is O(n²), where n is the length of the input array nums. Given the constraint 2 <= nums.length <= 2 * 10⁴, this means the algorithm could perform up to O((2 * 10⁴)²) = 4 * 10⁸ operations in the worst-case scenario.

While O(n²) might sound heavy for the upper limit, the actual performance depends on the input and implementation details. In practice, this brute force approach may be slower for the largest inputs but can still work within time limits for many cases.

Therefore, even though this approach isn't optimized and might not scale efficiently to the maximum input size, it is completely acceptable for smaller or moderate inputs and serves as a straightforward, easy-to-understand solution.

In fact, this brute force solution often passes on platforms like LeetCode for the given constraints. So, while the time complexity doesn’t guarantee the best efficiency for very large inputs, it is sufficiently efficient within typical test limits and a good starting point before considering optimized solutions.

How to optimize it?

Hey! Remember how in the previous brute-force approach, we went through every index and if something didn’t belong there, we would search ahead to find a suitable number to swap it with? It worked, but it involved a lot of back-and-forth searching — and that’s why it ended up being O(n²) in time complexity. It was simple but definitely not the fastest when dealing with large arrays.

Now, let’s switch gears and look at a smarter and cleaner way to solve the same problem — one that makes you go, “Ah, that’s neat!”

What do we know from the problem?
We’re told that the array contains equal numbers of even and odd integers, and we must place:

  • All even numbers at even indices (like 0, 2, 4, ...)
  • All odd numbers at odd indices (like 1, 3, 5, ...)

This is a perfect scenario where the positions are predictable. We don’t need to search for where to place a number. We already know the exact kind of index it should go to. That’s the key insight here.

For example, if we get an even number, we know it should be placed at an even index — like 0, 2, 4, and so on. Similarly, if we get an odd number, it should go to an odd index — like 1, 3, 5, etc.

So let’s imagine we start with an empty array of the same size as the input. We also know that the first even position is index 0, and the first odd position is index 1. From there, we can just keep track of these positions using two pointers: one for even indices and one for odd indices.

Now, as we traverse the original array:

  • If we come across an even number, we place it at the current even index, and then move the even index forward by 2.
  • If we find an odd number, we place it at the current odd index, and then move the odd index forward by 2.

We just keep doing this for each number in the array. No checking, no swapping — just placing things directly where they belong.

Sort Array By Parity II Algorithm

Instead of going index-by-index and checking whether something is wrongly placed, we build a new array from scratch. This time, we use two pointers:

  • One pointer (evenIndex) that keeps track of the next even slot (starts from 0)
  • Another pointer (oddIndex) that keeps track of the next odd slot (starts from 1)

Then, we simply go through the original array once:

  • If we find an even number, we put it at the current evenIndex, and move evenIndex += 2
  • If we find an odd number, we place it at oddIndex, and move oddIndex += 2

Just like that — no searching, no swapping, no wasting time.

Because the rules of placement are fixed, we never have to waste time looking for where to put something — we just put it in its place and move on. It turns the problem into a linear time task, which is much more efficient for large input sizes.

Let us understand with a video,

0:00
/0:54

Sort Array By Parity II-Optimal-Approach

💡
Try it Yourself!

Let's understand with an example:

Sort Array By Parity II Example:

Suppose we have the input: [4, 2, 5, 7]

We create an empty array like: [_, _, _, _]
Now we scan the original array:

  • First is 4 (even) → goes to index 0 → [4, _, _, _]
  • Next is 2 (even) → goes to index 2 → [4, _, 2, _]
  • Then 5 (odd) → goes to index 1 → [4, 5, 2, _]
  • Lastly 7 (odd) → goes to index 3 → [4, 5, 2, 7]

Tadaa! All even numbers at even indices, odd numbers at odd indices, and done in just one pass.

How to code it up:

  • Initialize two pointers:
    • evenIndex = 0 (for even positions)
    • oddIndex = 1 (for odd positions)
  • Create a new array ans of the same size as nums to store the result.
  • Loop through each element in the input array nums.
  • For each element:
    • If it’s even, place it at evenIndex in ans, and increment evenIndex by 2.
    • If it’s odd, place it at oddIndex in ans, and increment oddIndex by 2.
  • Return the ans array after filling all elements.

Sort Array By Parity II Solution

Code Implementation / Sort Array By Parity II Leetcode Solution
1. Sort Array By Parity II solution in C++ Try on Compiler 
class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        
        // Get the size of the input array
        int n = nums.size();
        
        // Pointer to place the next even number at an even index
        int evenIndex = 0;

        // Pointer to place the next odd number at an odd index
        int oddIndex = 1;

        // Create a new result array of the same size
        vector<int> ans(n);

        // Traverse each number in the input array
        for(int i = 0; i < n; i++)
        {
            // If the current number is even
            if(nums[i] % 2 == 0)
            {
                // Place it at the current even index
                ans[evenIndex] = nums[i];

                // Move to the next even index
                evenIndex += 2;
            }
            else
            {
                // Place the odd number at the current odd index
                ans[oddIndex] = nums[i];

                // Move to the next odd index
                oddIndex += 2;
            }
        }

        // Return the sorted result array
        return ans;
    }
};

2. Sort Array By Parity II solution in Java Try on Compiler 
class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        
        // Length of the input array
        int n = nums.length;

        // Pointer for even indices
        int evenIndex = 0;

        // Pointer for odd indices
        int oddIndex = 1;

        // Result array
        int[] ans = new int[n];

        // Traverse the input array
        for (int i = 0; i < n; i++) {

            // If current number is even
            if (nums[i] % 2 == 0) {
                
                // Place it at the current even index
                ans[evenIndex] = nums[i];

                // Move to the next even index
                evenIndex += 2;
            } else {
                
                // Place it at the current odd index
                ans[oddIndex] = nums[i];

                // Move to the next odd index
                oddIndex += 2;
            }
        }

        // Return the result
        return ans;
    }
}

3. Sort Array By Parity II solution in Python Try on Compiler 
class Solution:
    def sortArrayByParityII(self, nums):
        
        # Length of the array
        n = len(nums)
        
        # Pointer for even indices
        even_index = 0

        # Pointer for odd indices
        odd_index = 1

        # Create a result list of same length
        ans = [0] * n

        # Traverse through each number in nums
        for num in nums:

            # If the number is even
            if num % 2 == 0:

                # Place at the current even index
                ans[even_index] = num

                # Move to the next even index
                even_index += 2
            else:
                
                # Place at the current odd index
                ans[odd_index] = num

                # Move to the next odd index
                odd_index += 2

        # Return the final result
        return ans

4. Sort Array By Parity II solution in Javascript Try on Compiler 
var sortArrayByParityII = function(nums) {

    // Get the length of the array
    let n = nums.length;

    // Pointer for even indices
    let evenIndex = 0;

    // Pointer for odd indices
    let oddIndex = 1;

    // Create a result array
    let ans = new Array(n);

    // Iterate through each number
    for (let i = 0; i < n; i++) {

        // If number is even
        if (nums[i] % 2 === 0) {

            // Place at even index
            ans[evenIndex] = nums[i];

            // Move to next even index
            evenIndex += 2;
        } else {

            // Place at odd index
            ans[oddIndex] = nums[i];

            // Move to next odd index
            oddIndex += 2;
        }
    }

    // Return the result
    return ans;
};

Sort Array By Parity II Complexity Analysis

Time Complexity: O(n)

  • We iterate through the input array once, where n = nums.length.
  • Each element is processed exactly once — checking if it’s even or odd and placing it in the correct position in the result array.
  • There are no nested loops or costly operations, so the time complexity is linear in terms of the array size.

Time Complexity: O(n)

Space Complexity: O(n)

  1. Auxiliary Space Complexity: O(n)
    Auxiliary space refers to the additional memory the algorithm requires, excluding the space occupied by the input.
    We use an extra array ans of size n to store the result.
    Apart from that, we only use a few integer variables (evenIndex, oddIndex, i), which take constant space.
    So, auxiliary space used is O(n) due to the additional array.
  2. Total Space Complexity: O(n)
    Total space is the overall memory used by the algorithm, including both the input and any extra space needed during execution.
    The main space consumer here is the result array we create.
    So the total space complexity is O(n).

Can there be another approach?

Now, let’s switch gears again and take a look at another smart approach — one that saves even more space and makes you go, “Whoa, that's efficient!”

What do we know about the problem?

Just like before, we’re told that:

  • The array has equal numbers of even and odd elements.
  • And we need to arrange even numbers at even indices (0, 2, 4, …) and odd numbers at odd indices (1, 3, 5, …).

So earlier, we used an extra array and directly placed the elements in their rightful spots using two pointers — one for even positions and one for odd. That was clean, simple, and direct.

But what if we want to do the same thing without using any extra space?
No new array. No rebuilding from scratch.
Just work directly on the original array.

Think about it like this — if a number is already where it should be, we leave it there. No need to touch it.

But if a number is not where it belongs — for example, we find an odd number at an even index or vice versa — we fix it by swapping it with a number that’s also misplaced in the opposite way.

Let’s say you’re at index 0 (even index) and find an odd number there. That’s a mistake. So what do you do? You go find an even number sitting at some odd index — that’s also a mistake — and you swap them! Boom — now both numbers are at the right places.

We don’t need to search through the entire array blindly. We can do this smartly using two pointers again:

  • One pointer (e) starts at index 0 and tracks the next even index.
  • Another pointer (o) starts at index 1 and tracks the next odd index.

Now, we start walking through the array:

  • If nums[e] is already even, then it’s perfectly placed — we just move e forward by 2.
  • If nums[o] is already odd, great — it’s also correctly placed — so we move o forward by 2.

But if we find a mismatch — like an odd number at an even index and an even number at an odd index — that’s our golden moment. We just swap the two, and both are now fixed in one go. No wasted time, no wasted space.

Sort Array By Parity II – Two Pointer In-Place Algorithm

Here’s what’s going on:

  • We use two pointers: one for even indices (e) and one for odd indices (o).
  • We move e forward by 2 until we find a wrongly placed odd number.
  • We move o forward by 2 until we find a wrongly placed even number.
  • When both are pointing to wrong elements — we swap them to fix both in one step.

Let us understand this with a video,

0:00
/0:50

Sort Array By Parity II-Other-Optimal-Approach

This approach doesn’t build a new array. It fixes the original array in-place using just the two pointers — making it space-efficient and cleaner in memory usage.

💡
Try it Yourself!

Let's understand with an example:

Sort Array By Parity II Example:

Take this array: [4, 1, 2, 3]

  • At index 0 (even), we have 4 → good.
  • At index 1 (odd), we have 1 → good.
  • At index 2 (even), we have 2 → good.
  • At index 3 (odd), we have 3 → good.

So in this case, no swaps are needed.
But let’s mess it up a bit: [3, 2, 1, 4]

  • Index 0 → 3 (odd at even) → mismatch.
  • Index 1 → 2 (even at odd) → mismatch.

Perfect! We swap them.

Now we get [2, 3, 1, 4].

How to code it up:

  • Initialize two pointers:
    • e = 0 → points to even indices
    • o = 1 → points to odd indices
  • Run a while loop as long as both e and o are within the array bounds.
  • Advance the e pointer:
    • While nums[e] is even, move e += 2 to skip already-correct values.
  • Advance the o pointer:
    • While nums[o] is odd, move o += 2 to skip already-correct values.
  • If both e and o are in bounds, swap the mismatched elements at those indices.
  • Repeat until all elements are at correct positions.
  • Return the modified array.

Sort Array By Parity II Solution

Code Implementation / Sort Array By Parity II Leetcode Solution
1. Sort Array By Parity II solution in C++ Try on Compiler 
class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
    
        // Initialize two pointers: even index and odd index
        int e = 0, o = 1;

        // Loop until either pointer exceeds the array size
        while(e < nums.size() && o < nums.size()) {

            // Move even pointer forward if the number is already even
            while(e < nums.size() && nums[e] % 2 == 0) {
                e += 2;
            }

            // Move odd pointer forward if the number is already odd
            while(o < nums.size() && nums[o] % 2 == 1) {
                o += 2;
            }

            // Swap if both pointers point to incorrect placements
            if(e < nums.size() && o < nums.size()) {
                swap(nums[o], nums[e]);
            }
        }

        // Return the corrected array
        return nums;
    }
};

2. Sort Array By Parity II solution in Java Try on Compiler 
class Solution {
    public int[] sortArrayByParityII(int[] nums) {
    
        // Initialize two pointers for even and odd indices
        int e = 0, o = 1;

        // Loop until either pointer exceeds the array length
        while(e < nums.length && o < nums.length) {

            // Skip if current even index already holds an even number
            while(e < nums.length && nums[e] % 2 == 0) {
                e += 2;
            }

            // Skip if current odd index already holds an odd number
            while(o < nums.length && nums[o] % 2 == 1) {
                o += 2;
            }

            // Swap the elements if both pointers point to incorrect values
            if(e < nums.length && o < nums.length) {
                int temp = nums[e];
                nums[e] = nums[o];
                nums[o] = temp;
            }
        }

        // Return the fixed array
        return nums;
    }
}

3. Sort Array By Parity II solution in Python Try on Compiler 
class Solution:
    def sortArrayByParityII(self, nums):
    
        # Initialize pointers for even and odd indices
        e, o = 0, 1

        # Loop until either pointer reaches the end
        while e < len(nums) and o < len(nums):

            # Move even pointer if current number is already even
            while e < len(nums) and nums[e] % 2 == 0:
                e += 2

            # Move odd pointer if current number is already odd
            while o < len(nums) and nums[o] % 2 == 1:
                o += 2

            # Swap elements at incorrect positions
            if e < len(nums) and o < len(nums):
                nums[e], nums[o] = nums[o], nums[e]

        # Return the rearranged array
        return nums

4. Sort Array By Parity II solution in Javascript Try on Compiler 
var sortArrayByParityII = function(nums) {
  
    // Initialize even and odd pointers
    let e = 0, o = 1;

    // Loop until both pointers are within array bounds
    while(e < nums.length && o < nums.length) {

        // Move even pointer if current number is correctly placed
        while(e < nums.length && nums[e] % 2 === 0) {
            e += 2;
        }

        // Move odd pointer if current number is correctly placed
        while(o < nums.length && nums[o] % 2 === 1) {
            o += 2;
        }

        // Swap values if both pointers are pointing to mismatched elements
        if(e < nums.length && o < nums.length) {
            [nums[e], nums[o]] = [nums[o], nums[e]];
        }
    }

    // Return the sorted array
    return nums;
};

Sort Array By Parity II Complexity Analysis

Time Complexity: O(n)

We’re using two pointers here — one for even indices and one for odd indices.

The outer loop runs as long as both pointers are still inside the array. Think of it like this: we’re moving through the array in chunks of 2, checking only the even positions with the even pointer, and only the odd positions with the odd pointer.

Now, inside that outer loop, we have two inner loops that do something very clever:

  • The first inner loop keeps moving the even pointer forward as long as the number at that even index is already even. In other words, if everything is fine, just skip ahead.
  • Similarly, the second inner loop keeps moving the odd pointer forward as long as the number at that odd index is already odd.

So basically, we skip over all the correctly placed numbers and only stop when we find a mismatch.

Since we're visiting each element at most once, the total amount of work we do grows in a straight line with the size of the array. That’s what we call linear time, or O(n) in technical terms.

Space Complexity: O(n)

  1. Auxiliary Space Complexity: O(1)
    Auxiliary space refers to the additional memory the algorithm requires, excluding the space occupied by the input.
    This solution works in-place, meaning it directly rearranges the elements within the original array. It does not use any extra data structures like another array or list.
    So, auxiliary space used is O(1).
  2. Total Space Complexity: O(n)
    Total space is the overall memory used by the algorithm, including both the input and any extra space needed during execution.
    Even though we’re not creating a new array, the original array still takes up space in memory — that’s why total space is O(n), but again, no extra memory is added on top of that (beyond a few variables).
    So the total space complexity is O(n).

Similar Problems

When working with an array, sometimes using a simple two pointer technique can help solve problems efficiently without relying on sorting. By naturally placing elements in their correct positions as we traverse, we avoid unnecessary overhead and keep the logic clean and fast.

Now that we have successfully tackled this problem, let's try similar problems.

1. Sort Array By Parity

Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers.

Return any array that satisfies this condition.

2. Rearrange Array Elements by Sign

You are given a 0-indexed integer array nums of even length consisting of an equal number of positive and negative integers.

You should return the array of nums such that the the array follows the given conditions:

Every consecutive pair of integers have opposite signs.
For all integers with the same sign, the order in which they were present in nums is preserved.
The rearranged array begins with a positive integer.
Return the modified array after rearranging the elements to satisfy the aforementioned conditions.

3. Sort Even and Odd Indices Independently

You are given a 0-indexed integer array nums. Rearrange the values of nums according to the following rules:

Sort the values at odd indices of nums in non-increasing order.
For example, if nums = [4,1,2,3] before this step, it becomes [4,3,2,1] after. The values at odd indices 1 and 3 are sorted in non-increasing order.
Sort the values at even indices of nums in non-decreasing order.
For example, if nums = [4,1,2,3] before this step, it becomes [2,1,4,3] after. The values at even indices 0 and 2 are sorted in non-decreasing order.
Return the array formed after rearranging the values of nums.

4. Largest Number After Digit Swaps by Parity

You are given a positive integer num. You may swap any two digits of num that have the same parity (i.e. both odd digits or both even digits).

Return the largest possible value of num after any number of swaps.

5. Find the Number of K-Even Arrays

Given an array arr[] of n integers and an integer K, the task is to find the number of ways to select exactly K even numbers from the given array.

💡
Showcase your skills by joining LearnYard Technologies FZ-LLC as a Technical Content Writer. Apply now and inspire the next generation of learners—fill out the form: https://forms.gle/CGDsbGkcapSfvXKM8