3667. Sort Array By Absolute Value 🔒
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 isx
itself - For negative numbers (
x < 0
): the absolute value is-x
(the positive version)
For example:
- The absolute value of
5
is5
- The absolute value of
-3
is3
- The absolute value of
0
is0
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.
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 fromnums
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 elementx
and returns its absolute valueabs(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
andabs(2) = 2
- Since
2 < 4
, the element2
will come before-4
in the sorted array - The original values (
-4
and2
) are preserved in the output; only the comparison uses absolute values
Time and Space Complexity:
- Time Complexity:
O(n log n)
wheren
is the length of the array. This is the standard time complexity for comparison-based sorting algorithms. - Space Complexity:
O(n)
becausesorted()
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 3-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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))
Which algorithm is best for finding the shortest distance between two points in an unweighted graph?
Recommended Readings
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Don’t Miss This!