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.
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.
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!
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.
- 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!