LeetCode 3667 - Sort Array By Absolute Value

LeetCode Problem 3667

Difficulty: 🟢 Easy
Topics: Array, Math, Two Pointers, Sorting

Solution

Problem Understanding

The problem asks us to reorder an integer array such that the elements are sorted in non-decreasing order of their absolute values. This means we are not sorting based on the actual numeric value, but rather based on how far each number is from zero on the number line, regardless of sign.

In simpler terms, we compute abs(nums[i]) for every element, and then arrange the original numbers so that these absolute values appear in sorted order. Importantly, when two numbers have the same absolute value, either order is acceptable, since the problem allows returning any valid rearrangement.

The input is a list of integers nums, with constraints ensuring a small input size: at most 100 elements, and values ranging between -100 and 100. This indicates that both simple sorting and even less efficient approaches would pass easily, but we should still aim for a clean optimal solution.

Edge cases include arrays with all positive numbers, all negative numbers, mixtures of equal absolute values like [1, -1], single-element arrays, and arrays already sorted by absolute value.

The key challenge is recognizing that we are not sorting by value but by a derived key, absolute value, which directly suggests a custom sort.

Approaches

The brute-force approach is to repeatedly select the element with the smallest absolute value from the remaining unsorted portion and append it to the result array. This behaves like a selection sort variant where comparison is based on abs(x). While correct, this requires scanning the remaining elements repeatedly, leading to quadratic time complexity.

The optimal approach leverages the built-in sorting mechanism with a custom key function. Since sorting algorithms in modern languages are highly optimized (typically Timsort), we simply sort the array using abs(x) as the key. This reduces the problem to a single pass sort operation.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly select minimum absolute value
Optimal	O(n log n)	O(1) to O(n)	Sort using absolute value as key

Algorithm Walkthrough

The optimal algorithm is straightforward due to the presence of a natural ordering key.

1. Define a comparison key based on absolute value, meaning each element x is compared using abs(x) instead of x. This ensures that sorting is guided by distance from zero rather than signed magnitude.
2. Apply a sorting algorithm to the entire array using this key. The sorting algorithm internally compares elements by their absolute values and rearranges them accordingly.
3. Since the problem allows any valid ordering when absolute values are equal, we do not need a secondary tie-break rule. The default stability of the sort implementation is sufficient.
4. Return the sorted array directly as it now satisfies the non-decreasing absolute value property.

Why it works

The correctness comes from the fact that sorting by a monotonic transformation key, in this case f(x) = abs(x), preserves a valid total ordering over all elements with respect to the required criterion. Every element is placed such that no later element has a smaller absolute value than an earlier one, which exactly matches the problem requirement.

Python Solution

from typing import List

class Solution:
    def sortByAbsoluteValue(self, nums: List[int]) -> List[int]:
        return sorted(nums, key=abs)

The implementation uses Python’s built-in sorted function with key=abs, which ensures each element is compared using its absolute value rather than its raw integer value. The function returns a new sorted list, leaving the original input unchanged.

Go Solution

import "sort"

func sortByAbsoluteValue(nums []int) []int {
    sort.Slice(nums, func(i, j int) bool {
        return abs(nums[i]) < abs(nums[j])
    })
    return nums
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

In Go, we use sort.Slice with a custom comparator function that compares absolute values. Unlike Python, Go requires explicitly defining the absolute value function. The sorting is done in-place on the slice, which is idiomatic in Go and avoids additional memory allocation.

Worked Examples

Example 1: nums = [3, -1, -4, 1, 5]

We compute absolute values and sort based on them.

Step	Array State	Absolute Values
Initial	[3, -1, -4, 1, 5]	[3, 1, 4, 1, 5]
After sorting	[-1, 1, 3, -4, 5]	[1, 1, 3, 4, 5]

The result is valid because elements are ordered by increasing absolute value.

Example 2: nums = [-100, 100]

Step	Array State	Absolute Values
Initial	[-100, 100]	[100, 100]
After sorting	[-100, 100]	[100, 100]

Both outputs are valid since the absolute values are equal, so any order is acceptable.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates, comparing elements by absolute value
Space	O(1) to O(n)	Depends on sorting implementation (Python uses Timsort auxiliary space in worst case)

The complexity is determined entirely by the sorting operation, as computing absolute values is O(1) per element and done during comparisons.

Test Cases

assert Solution().sortByAbsoluteValue([3,-1,-4,1,5]) in [[-1,1,3,-4,5],[1,-1,3,-4,5]]  # example case
assert Solution().sortByAbsoluteValue([-100,100]) in [[-100,100],[100,-100]]  # equal abs values
assert Solution().sortByAbsoluteValue([0]) == [0]  # single element
assert Solution().sortByAbsoluteValue([2, -2, 1, -1])[:2] in ([1,-1], [-1,1])  # ties in abs
assert Solution().sortByAbsoluteValue([5,4,3,2,1]) == [1,2,3,4,5]  # all positive
assert Solution().sortByAbsoluteValue([-5,-4,-3,-2,-1]) == [-1,-2,-3,-4,-5]  # all negative

Test	Why
mixed positives and negatives	validates general ordering
equal absolute values	checks tie handling
single element	minimal boundary
alternating signs	stress symmetry handling
already sorted positives	confirms no disruption
all negatives	ensures abs-based ordering

Edge Cases

A single-element array is an important edge case because the sorting operation should return the same array unchanged. This can expose incorrect implementations that assume at least two elements exist.

Arrays where all elements have identical absolute values, such as [3, -3, 3, -3], are also critical. Since all comparison keys are equal, any permutation is valid, and the implementation must not rely on unstable assumptions.

Another edge case involves already sorted or reverse-sorted inputs by absolute value. These test whether the sorting logic incorrectly disturbs already valid orderings or whether it correctly preserves a valid sorted result.

Finally, arrays containing zero should be considered carefully. Zero has absolute value zero and must always appear at the beginning of the result, and implementations must ensure it is not mishandled by custom absolute value logic or comparator errors.