3667. Sort Array By Absolute Value

Easy

Problem Description

You are given an integer array nums. Your task is to rearrange the elements in the array based on their absolute values, sorting them in non-decreasing order.

The absolute value of an integer is defined as:

For non-negative numbers (x >= 0): the absolute value is x itself
For negative numbers (x < 0): the absolute value is -x (the positive version)

For example:

The absolute value of 5 is 5
The absolute value of -3 is 3
The absolute value of 0 is 0

You need to sort the array so that elements with smaller absolute values come before elements with larger absolute values. If two elements have the same absolute value, their relative order doesn't matter - you can return any valid arrangement.

For instance, if the input array is [-4, -1, 3, 2]:

The absolute values are [4, 1, 3, 2]
After sorting by absolute value: [-1, 2, 3, -4] (or [-1, 2, -3, 4] would also be valid if -3 was in the array)

The solution uses Python's built-in sorted() function with a custom key that computes the absolute value of each element using abs(x). This ensures the array is sorted based on the magnitude of each number rather than its signed value.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

When we need to sort elements by their absolute values, we're essentially asking: "How can we arrange numbers so that those closer to zero come first, regardless of their sign?"

The key insight is that we don't need to manually implement a complex sorting algorithm or handle positive and negative numbers separately. Instead, we can leverage the fact that most programming languages provide sorting functions that accept custom comparison criteria.

Think about what we're really doing: we want to sort based on the "distance from zero" for each number. The absolute value function abs() gives us exactly this distance. A number like -2 has the same distance from zero as 2, which is why abs(-2) = abs(2) = 2.

By using the absolute value as our sorting key, we transform the problem from "sort these positive and negative numbers by their magnitude" to simply "sort these numbers by their transformed values." The sorting algorithm doesn't need to know about the original signs during comparison - it just needs to know which absolute value is smaller.

This approach is elegant because:

We don't need to separate positive and negative numbers
We don't need to write custom comparison logic
We let the built-in sorting function do the heavy lifting while we just specify what to compare (the absolute values)

The solution sorted(nums, key=lambda x: abs(x)) tells the sorting function: "for each element x, use abs(x) as the value to compare when determining order." This single line handles all the complexity of arranging numbers by their magnitude while preserving their original signs in the output.

Solution Approach

The solution uses a custom sorting approach, which is one of the most straightforward ways to solve this problem.

Implementation Details:

The implementation leverages Python's built-in sorted() function with a custom key function:

return sorted(nums, key=lambda x: abs(x))

Let's break down how this works:

The sorted() function: This creates a new list containing all elements from nums in sorted order. It doesn't modify the original array but returns a new sorted array.
The key parameter: This parameter accepts a function that will be called on each element before making comparisons. The sorting is done based on the return value of this key function.
The lambda function lambda x: abs(x): This is an anonymous function that takes an element x and returns its absolute value abs(x). For each element in the array, this function computes the absolute value, and that value is used for comparison during sorting.

How the sorting process works:

When the sorting algorithm compares two elements, say -4 and 2:

It computes abs(-4) = 4 and abs(2) = 2
Since 2 < 4, the element 2 will come before -4 in the sorted array
The original values (-4 and 2) are preserved in the output; only the comparison uses absolute values

Time and Space Complexity:

Time Complexity: O(n log n) where n is the length of the array. This is the standard time complexity for comparison-based sorting algorithms.
Space Complexity: O(n) because sorted() creates a new list rather than sorting in-place.

Alternative In-Place Approach:

If we wanted to sort in-place to save space, we could use:

nums.sort(key=lambda x: abs(x))
return nums

This would modify the original array directly with O(1) extra space (not counting the space used by the sorting algorithm itself).

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Input: nums = [-4, -1, 3, 2, -5]

Step 1: Identify absolute values For each element, we determine its absolute value:

-4 → abs(-4) = 4
-1 → abs(-1) = 1
3 → abs(3) = 3
2 → abs(2) = 2
-5 → abs(-5) = 5

Step 2: Create key-value pairs (conceptually) The sorting function internally pairs each original value with its absolute value:

(-4, 4), (-1, 1), (3, 3), (2, 2), (-5, 5)

Step 3: Sort by absolute values The pairs are sorted based on the second value (the absolute value):

(-1, 1) comes first (smallest absolute value)
(2, 2) comes second
(3, 3) comes third
(-4, 4) comes fourth
(-5, 5) comes last (largest absolute value)

Step 4: Extract original values The sorted array contains the original values in their new order: [-1, 2, 3, -4, -5]

Verification: Let's verify the result by checking absolute values:

abs(-1) = 1 ✓
abs(2) = 2 ✓
abs(3) = 3 ✓
abs(-4) = 4 ✓
abs(-5) = 5 ✓

The absolute values are in non-decreasing order: 1 ≤ 2 ≤ 3 ≤ 4 ≤ 5

Final Output: [-1, 2, 3, -4, -5]

Note that if two elements had the same absolute value (like -3 and 3), they could appear in any order relative to each other in the final result.

Solution Implementation

1from typing import List
2
3class Solution:
4    def sortByAbsoluteValue(self, nums: List[int]) -> List[int]:
5        """
6        Sort an array of integers by their absolute values.
7
8        Args:
9            nums: List of integers to be sorted
10
11        Returns:
12            List of integers sorted by absolute value in ascending order
13        """
14        # Sort the list using absolute value as the sorting key
15        # Lambda function computes the absolute value for each element
16        return sorted(nums, key=lambda x: abs(x))
17

1class Solution {
2    /**
3     * Sorts an array of integers by their absolute values.
4     * Elements with smaller absolute values come first.
5     *
6     * @param nums the input array of integers to be sorted
7     * @return a new array with elements sorted by absolute value
8     */
9    public int[] sortByAbsoluteValue(int[] nums) {
10        // Convert primitive int array to Stream
11        return Arrays.stream(nums)
12            // Box each primitive int to Integer object for stream operations
13            .boxed()
14            // Sort elements by comparing their absolute values
15            .sorted(Comparator.comparingInt(Math::abs))
16            // Convert Integer objects back to primitive int values
17            .mapToInt(Integer::intValue)
18            // Collect the sorted stream into a new int array
19            .toArray();
20    }
21}
22

1class Solution {
2public:
3    /**
4     * Sorts an array of integers by their absolute values in ascending order
5     * @param nums - Input vector of integers to be sorted
6     * @return Vector of integers sorted by absolute value
7     */
8    vector<int> sortByAbsoluteValue(vector<int>& nums) {
9        // Sort the array using a custom comparator that compares absolute values
10        // Lambda function compares two integers based on their absolute values
11        sort(nums.begin(), nums.end(), [](int a, int b) {
12            // Return true if |a| < |b| to maintain ascending order
13            return abs(a) < abs(b);
14        });
15
16        // Return the sorted array
17        return nums;
18    }
19};
20

1/**
2 * Sorts an array of numbers by their absolute values in ascending order
3 * @param nums - The input array of numbers to be sorted
4 * @returns A sorted array where elements are ordered by their absolute values
5 */
6function sortByAbsoluteValue(nums: number[]): number[] {
7    // Sort the array using a custom comparator that compares absolute values
8    // For example: [-4, -1, 3, 2] becomes [-1, 2, 3, -4]
9    return nums.sort((a: number, b: number) => Math.abs(a) - Math.abs(b));
10}
11

Time and Space Complexity

The time complexity is O(n × log n), where n is the length of the array nums. This is because the sorted() function in Python uses Timsort algorithm, which has a worst-case and average-case time complexity of O(n × log n). Even though we're using a custom key function lambda x: abs(x), this only adds a constant factor to each comparison operation and doesn't change the overall time complexity.

The space complexity is O(log n), where n is the length of the array nums. While the sorted() function creates a new list which would normally suggest O(n) space complexity, the reference answer indicates O(log n). This refers to the auxiliary space used by the sorting algorithm itself (excluding the output array). Timsort uses O(log n) additional space for its merge operations and stack frames during the recursive sorting process. If we were to consider the space for the output array, the total space would be O(n), but following the reference answer's convention, we report the auxiliary space complexity as O(log n).

Common Pitfalls

1. Confusion About Stability When Elements Have Equal Absolute Values

A common misconception is assuming a specific order for elements with the same absolute value. For example, given [3, -3, 2, -2], some might expect a deterministic output like [2, -2, 3, -3] or [-2, 2, -3, 3].

The Issue: Python's sorted() is stable (preserves the relative order of equal elements), but this only applies to the original order in the input array. So [3, -3, 2, -2] would become [2, -2, 3, -3], while [-3, 3, -2, 2] would become [-2, 2, -3, 3].

Solution: If you need a specific ordering for equal absolute values (e.g., negative before positive), use a tuple as the key:

return sorted(nums, key=lambda x: (abs(x), x))

This sorts first by absolute value, then by the actual value for tie-breaking.

2. Assuming In-Place Modification

Developers might expect the original array to be modified, especially if coming from languages where sorting typically happens in-place.

The Issue: The sorted() function returns a new list and leaves the original unchanged:

nums = [3, -1, -2]
result = sorted(nums, key=lambda x: abs(x))
# nums is still [3, -1, -2]
# result is [-1, -2, 3]

Solution: Use list.sort() for in-place sorting:

nums.sort(key=lambda x: abs(x))
return nums

3. Integer Overflow Concerns (From Other Languages)

Developers from C++ or Java might worry about integer overflow when computing absolute values, particularly for the minimum integer value (e.g., -2^31 in 32-bit systems).

The Issue: In those languages, abs(INT_MIN) can cause overflow because the positive equivalent doesn't fit in the same data type.

Solution: Python handles arbitrary-precision integers automatically, so this isn't a concern. However, if implementing in other languages, be aware of this edge case and handle it appropriately.

4. Performance Assumptions with Large Arrays

Some might try to optimize by implementing custom sorting algorithms thinking it would be faster than the built-in sort.

The Issue: Python's built-in sorted() uses Timsort, which is highly optimized and performs better than most custom implementations, especially with partially sorted data.

Solution: Stick with the built-in sorting unless you have a very specific use case. The simple solution is often the best:

return sorted(nums, key=lambda x: abs(x))

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Add another stack to store the minimums

Add a heap to store the minimums

Add a variable to track the minimum

Add a queue to store the minumums

I don't know