algoadvance

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.

Clarifying Questions

1. Input Constraints: What is the range of values for nums?
   • nums will be a list of integers.
   • The values will fit in a standard 32-bit integer.
2. Output: Should the relative order of the even/odd numbers be maintained?
   • The problem does not specify that the relative order must be maintained, so any order that segregates evens first and odds second is acceptable.
3. In-place vs. New Array: Should we modify the array in-place or can we use extra space?
   • The problem statement doesn’t specify, so we can use extra space if it simplifies the solution.

With these clarifications, we can proceed to devise a strategy to implement the solution.

Strategy

1. Simple Approach (Using Extra Space):
   • Initialize two empty lists: evens and odds.
   • Iterate through the array and append each number to evens if it is even, or to odds if it is odd.
   • Concatenate the evens and odds lists to form the desired output.
2. In-place Approach:
   • Use two pointers: one at the beginning (i = 0) and one at the end (j = len(nums) - 1).
   • Traverse the array and swap elements so that all even numbers are moved to the front and all odd numbers are moved to the back.

Given the simplicity and clarity of the first approach, let’s start with that.

Code

def sortArrayByParity(nums):
    evens = []
    odds = []
    
    for num in nums:
        if num % 2 == 0:
            evens.append(num)
        else:
            odds.append(num)
    
    return evens + odds

Time Complexity

• Time Complexity: O(N), where N is the length of the input list. We only make a single pass through the array.
• Space Complexity: O(N), where N is the length of the input list due to the additional space used by the evens and odds lists.

Now, let’s consider the in-place approach for completeness.

Alternative In-place Implementation

def sortArrayByParity(nums):
    i, j = 0, len(nums) - 1
    
    while i < j:
        if nums[i] % 2 > nums[j] % 2:
            nums[i], nums[j] = nums[j], nums[i]
        
        if nums[i] % 2 == 0:
            i += 1
        if nums[j] % 2 == 1:
            j -= 1
    
    return nums

Time Complexity for In-place Approach

• Time Complexity: O(N), due to a single pass through the array with the two pointers.
• Space Complexity: O(1), as we are sorting the array in-place without using additional space.

This provides a more memory-efficient solution while maintaining similar time complexity.

Try our interview co-pilot at AlgoAdvance.com

• 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?