Day-7 Sort Array by Parity

This problem statement is a part of the introduction to data structures Arrays -101 section in Leetcode.

Problem Statement

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

You may return any answer array that satisfies this condition.

Example 1:

Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Note:

1. <= A.length <= 5000
2. 0 <= A[i] <= 5000

Solution Approach

1. Iterate over the list.
2. Add even elements to list 1. Add odd elements to another list.
3. Add odd elements to the list of even elements by using extend.

class Solution:
    def sortArrayByParity(self, A: List[int]) -> List[int]:
        even_values = []
        odd_values = []
        for x in range(0, len(A)):
            if A[x] % 2 == 0:
                even_values.append(A[x])
            else:
                odd_values.append(A[x])
        even_values.extend(odd_values)
        return even_values

Learnings

1. Time complexity - O(n), space complexity - O(n)
2. Time complexity of extending is 0(k) - k is the length of list to be extended.

TODO

Optimize space complexity further from O(n) to O(1). Write an in-place solution.

Comments

[Bekzod]

We could have bubble sort with a val % 2 ==0 predicate or a slighty modified version of a Dutch national flag sorting problem, the main idea is to have two pointers. IMO in that case the space complexity should be O(1)