JavaScript Problem Solvers: Sort Array By Parity

CASE 007: Shuffling The Deck

Today’s problem is going to be a simple one. It is a fairly easy sorting problem that goes along with the insertion algorithm that we wrote last week, and I felt it would be a good idea to get our feet wet with a basic sorting algorithm as well.

So let’s get solving.

THE PROBLEM

Here is a link to the problem on LeetCode

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.
Constraints:
  1 <= A.length <= 5000
  0 <= A[i] <= 5000
Test Cases
  [3,1,2,4] => [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.
***Since we are only given a single test case, I decided to add a couple more to make sure our solution works as advertised:
  [0, 1] => [0, 1]
  [0, 1, 2] => [0, 2, 1]
  [3, 2, 0, 5, 4, 1] => [0, 2, 4, 3, 5, 1]
  [1, 4, 2, 0, 1, 5, 3, 4, 3, 7] => [0, 2, 4, 4, 1, 1, 5, 3, 3, 7]

THE BREAK DOWN

I found this problem to have a straight forward explanation that doesn’t try to obfuscate any of it’s objectives. But as always, let’s breakdown all of the information given to us to make sure we understand what we are tasked in solving:

Given an array A of non-negative integers

This gives us three separate important pieces of information, and an idea of where to start. The function that we write is going to accept an array called A. The array will only contain integers, so we do not have to take other primitives into account and can rely on the fact that we will only have to handle integers. The last piece of information we get is that all integers will be non-negative, which is re enforced by the second of two constraints we are given.

return an array consisting of all the even elements of A followed by all the odd elements of A

Here we learn that our function needs to return an array, and reveals how the elements in the return array should be organized. All we are going to have to do is make sure all of the even elements in A appear before all of the odd elements in A. Simple and straight forward.

You may return any answer array that satisfies this condition.

This is the most interesting part to me. Since our return array is not restricted by anything other than having all even elements in A appear before all of the odd elements in A, we do not need to worry about any resorting or organization of what we are returning.

Honestly, I was originally thrown off by this at first, and found that I have been conditioned for solutions I write to have specific outputs, I didn’t know how to properly test or approach a solution.

We could write additional logic to make sure both odd and even numbers in our return array are sorted from least to greatest and use parts of the solution we came up with last week for the insertion algorithm, but it is unnecessary.

There are a few other things we could add into this solution to make it more complex, but for now, let’s not try to bite off more than we can chew and solve the problem as it is explained.

THE CONSTRAINTS

We are only given two basic constraints, which don’t offer much additional information. But once again, let’s go through both constraints just to make sure we understand them:

1 <= A.length <= 5000

The first constraint of 1 <= A.length <= 5000 gives us a lower limit and upper limit for how large our input array will be. With the lower limit of 1 <= A.length, we find out that we don’t have to worry about an input array being empty, or have a length of 0. The upper limit of A.length <= 5000 is not as vital, but as always, it is good to have an upper limit in case we wanted to calculate a maximum amount of operations for our function.

0 <= A[i] <= 5000

The second constraint 0 <= A[i] <= 5000 also gives us a lower limit and upper limit, but for the numbers we should expect in the input array (A).

While this is not as vital as the lower limit for A.length as stated above since all we are going to have to do is detect whether an element in the input array (A) is odd or even, it does reinforce the fact that no number in the input array (A) will be negative, and allows us to exclude a potential edge case.

THE EDGE CASES

While the majority of potential edge cases are covered by either the problem’s explanation or the two constraints, there is 1 possible edge case that I found interesting and could force us to come up with a more complex solution:

The input array (A) is an empty array

We won’t have to write an exception for an empty array given the constraint of 1 <= A.length

The input array (A) contains negative numbers

Here is another edge case we can forget about thanks to another constraint: 0 <= A[i]

The input array (A) contains a 0

This might not be considered an edge case, but I decided to include it since it is something we are going to have to account for. 0 is an even number, so we have to make sure that when we are checking if a number is odd or even, that 0 will be grouped with other even numbers.

The input array (A) contains an element that is a string

Yet another edge case we do not have to worry about since it is specifically stated in the problem’s explanation Given an array A of non-negative integers, and supported by the constraint 0 <= A[i] <= 5000.

The input array (A) contains two of the same integers

This is something not specifically stated or eluded to in this problems explanation, constraints, or test cases, and becomes a possible edge case we could encounter. If we had strict requirements regarding the order of the elements in our return array, this could come to be a problem. But all we need to do is make sure all even elements in our return array appear before all odd elements, this could become a non issue depending on how we write our solution.

Now that we have thoroughly gone through all of the information provided for us, we can start thinking about how we are going to solve this problem.

THE SUSPECT

As previously stated, I found this problem to be fairly simple, mostly due to the fact that we do not need to organize our return array in any specific manner. All we need to do is have all even elements in A appear before all of the odd elements in A.

The most naive solution I found involved splitting A into two separate arrays, with one containing all the even integers, and the other containing all the odd integers, then combining the two with a spread operator.

But the way I decided to iterate through A is a little different than usual. We can iterate through A using a while loop, and slowly empty A as we iterate through it (while(A.length > 0)).

We can check if each element is odd or even by checking if the first element of A (A[0]) returns a remainder when modulo’d by 2 (A[0] % 2 == 0). If it doesn’t, we can push the first element of A into the even array (even.push(A.shift())). If it does, push the first element of A into the odd array (odd.push(A.shift())).

By iterating through A in this fashion, we can push shift elements in A into either the even array, or the odd array based off a boolean expression, and end the while loop once A is empty.

Then at the end, we can return [ …even, …odd ]

Simple, easy, and straight forward.

THE PSEUDO CODE

So now that we have our simple solution, let’s write up some pseudo code before we put our plan into practice:

THE COMMENTS

With our pseudo code looking plausible, let’s start writing out a solution:

First, let’s define the function sortArrayByParity, our empty even and odd arrays, as well as the combination of the even and odd array as our return value:

Then, let’s write out our while loop:

Next, we can write our if statement to check if an integer is odd or even:

Last but not least, we can write the logic that pushes the first element of A to either the even or odd array:

If we run our solution, we should match the test case provided for us, and the extra ones I added:

THE FINAL SOLUTION

Let’s take a final look at our solutions without the comments, and clean up some of our syntax:

Nice.

MISSION COMPLETE

This might be the most basic problem I’ve written a blog about. Unfortunately, I have been extremely busy this week and did not have the time to find a more interesting or complex problem than the one we solved today.

I still find today’s problem interesting, even if it is far simpler than problems I have written about in the past. At the very least, I wanted to get a blog written this week, even if the blog itself is not as in depth as the ones that precede it.

Once again, the blogs I write about solving LeetCode or HackerRank problems isn’t about finding the solution with the lowest time or space complexity. Their focus is on the steps taken to come to a solution.

I definitely understand my solutions won’t be the best or most efficient, but either way I hope they help you or someone else figure out a way to solve a problem you encounter on this journey we call JavaScript.

Stay safe…stay healthy…and keep fighting the good fight.

Coding Interview Questions | Skilled.dev