algoadvance

Leetcode 905. Sort Array By Parity

Problem Statement

Given an array of integers 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.

Clarifying Questions

Before we dive into the solution, let’s clarify the following questions:

1. Is the order of even and odd numbers required to be preserved among themselves?
   • No, the problem doesn’t specify that. Any order within even and odd groups is acceptable.
2. Can we assume that the input array nums will always contain integers?
   • Yes, we can assume the input is a valid array of integers.

Strategy

We can solve this problem efficiently using a two-pointer approach:

1. Initialize two pointers: one (start) at the beginning of the array and another (end) at the end of the array.
2. Traverse the array starting from both ends.
   • Increment the start pointer if the current element is even.
   • Decrement the end pointer if the current element is odd.
   • If start points to an odd number and end points to an even number, swap the elements.
3. Continue until the start pointer is greater than or equal to the end pointer.

This approach ensures that all even numbers are moved to the front and odd numbers to the back with minimal swaps.

Code

Here is the implementation in C++:

#include <vector>

std::vector<int> sortArrayByParity(std::vector<int>& nums) {
    int start = 0;
    int end = nums.size() - 1;
    
    while (start < end) {
        if (nums[start] % 2 == 0) {
            ++start;
        } else if (nums[end] % 2 == 1) {
            --end;
        } else {
            std::swap(nums[start], nums[end]);
            ++start;
            --end;
        }
    }
    
    return nums;
}

Explanation

• Initialization: We start with two pointers, start at the beginning (0) and end at the last element (nums.size()-1).
• Traversal:
  • If nums[start] is even (nums[start] % 2 == 0), move the start pointer to the right.
  • If nums[end] is odd (nums[end] % 2 == 1), move the end pointer to the left.
  • If nums[start] is odd and nums[end] is even, swap the two values and adjust both pointers (start right, end left).
• Termination: The loop stops when start is no longer less than end.

Time Complexity

• Time Complexity: O(n), where n is the number of elements in the input array. We traverse each element at most once.
• Space Complexity: O(1). The sorting is done in place, requiring no additional storage.

This method is optimal in terms of both time and space, making it a suitable solution for the problem.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?