Two Approaches: Sorting an Array by Parity

In my interviewing adventures I have ran into a handful of questions that have provided great frameworks for solutions to reference in future problems. One such question is the Sort Array By Parity problem.

Problem

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.

Brute Force:

def sort_array_by_parity(a)
    i = 0
    j =  a.length - 1
    while i < j
        if a[i] % 2 > a[j] % 2
            temp = a[i]
            a[i] = a[j]
            a[j] = temp
        end 
        if a[i] % 2 == 0
            i += 1
        end
        if a[j] % 2 == 1
            j -= 1
        end
    end
  return a
end

In my first attempt at this problem I decided to try a two pointer approach and iterate towards the middle of the array. This solution passed the tests but had a runtime of 56ms placing it solidly slower than the majority of ruby submissions on LeetCode. So let's do better!

Final Solution:

def sort_array_by_parity(a)
  # create an index to store the next even number you run into
  index = 0
  i = 0
  #iterate through
  while  i < a.length 
     # if you encounter an even number move it to a[index]
    if a[i] % 2 == 0
      temp = a[index]
      a[index] = a[i]
      index += 1
      a[i] = temp
    end
    i += 1
  end
  return a
end

This solution earned me a runtime of 40ms and beat 98.98% of all other ruby solution submissions.

My Takeaways

• Using an index variable can be useful for tracking where you want to place the next instance of something
• temporary variables can help you switch variables an array

Happy problem solving!