Sort Array By Absolute Value

Sort Array By Absolute Value

What is this problem about?

"Sort Array By Absolute Value" is an "Easy" difficulty problem that requires you to take an array of integers and return a new array where the elements are sorted based on their distance from zero, rather than their actual numerical value.

For example, -5 is numerically smaller than 2, but its absolute value (5) is larger than the absolute value of 2 (2). Therefore, in the output, 2 would appear before -5. This problem tests your ability to use custom sorting criteria and handle negative numbers effectively.

Why is this asked in interviews?

Companies like Cognizant ask this to test basic coding fluency and familiarity with sorting functions. It’s a common introductory question to see if a candidate knows how to provide a custom comparator or key to a sort function. It also provides an opportunity for the candidate to suggest a more optimized approach using Two Pointers if the input array is already numerically sorted.

Algorithmic pattern used

The most direct pattern is Sorting with a Custom Key. In many languages, you can sort an array and specify that the comparison should be done on abs(x). If the input array is already sorted numerically (e.g., [-10, -2, 0, 5, 12]), you can use a Two Pointers pattern to build the result in $O(N)$ time by comparing the absolute values at both ends of the array and moving inwards.

Example explanation

Input: [2, -7, -2, 4, 0]

1. Absolute values: [|2|=2, |-7|=7, |-2|=2, |4|=4, |0|=0]
2. Sort by these values: 0, 2, 2, 4, 7.
3. Map back to original values: [0, 2, -2, 4, -7] (or [0, -2, 2, 4, -7], the order of elements with the same absolute value usually doesn't matter unless specified).

Common mistakes candidates make

One common mistake is returning the absolute values themselves (e.g., [0, 2, 2, 4, 7]) instead of the original numbers (e.g., [0, 2, -2, 4, -7]). Another mistake is not considering the case where two numbers have the same absolute value (like 2 and -2); you should clarify if their relative order matters. Finally, using a full sort when a linear Two Pointers approach is possible (if the input is already sorted) is a missed opportunity for optimization.

Interview preparation tip

For the "Sort Array By Absolute Value coding problem," always ask the interviewer if the input is already sorted. If it is, demonstrate your seniority by proposing the $O(N)$ two-pointer solution instead of the $O(N \log N)$ sort. This shows you are thinking about efficiency beyond the most obvious solution. Also, get comfortable with the syntax for custom sorting in your preferred language.