DEV Community

Mridu Bhatnagar
Mridu Bhatnagar

Posted on

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.

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

Top comments (1)

Collapse
 
ekologic profile image
Bekzod • Edited

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)

Image of Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay