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!
Top comments (0)