When dealing with sorted arrays that include negative numbers, an interesting challenge arises: Sorting the squares of the numbers efficiently. In this post, we’ll explore two approaches to solving this problem in JavaScript.

Problem Statement

Given a sorted array of integers (which may include negative numbers), return an array of the squares of each number, sorted in non-decreasing order.

Example 1:

console.log(sortedSquares([-7, -3, 2, 3, 11])); // Output: [4, 9, 9, 49, 121]

Example 2:

console.log(sortedSquares([-4, -1, 0, 3, 10])); // Output: [0, 1, 9, 16, 100]

Solution 1: Using Built-in Sorting

The simplest way to solve this problem is to:

1. Compute the square of each number.
2. Sort the resulting array using JavaScript’s built-in .sort() method.

JavaScript Implementation

var sortedSquares = function (nums) {
  let result = [];
  for (let index = 0; index < nums.length; index++) {
    const element = Math.abs(nums[index]);
    result.push(element * element);
  }

  result = result.sort((a, b) => a - b);
  return result;
};

Complexity Analysis

• Time Complexity: O(n log n), due to sorting.
• Space Complexity: O(n), as we create a new array.

Solution 2: Using Bubble Sort

Bubble Sort is a simple sorting algorithm that repeatedly swaps adjacent elements if they are in the wrong order. It’s not the most efficient sorting method (O(n²)) but is useful for learning purposes.

JavaScript Implementation Using Bubble Sort

const sortedSquaresUsingBubleSort = (nums) => {
  let result = [];
  for (let index = 0; index < nums.length; index++) {
    const element = Math.abs(nums[index]);
    result.push(element * element);
  }

  let swapped;
  do {
    swapped = false;
    for (let i = 0; i < result.length - 1; i++) { // Adjusted to prevent undefined comparison
      if (result[i] > result[i + 1]) {
        [result[i], result[i + 1]] = [result[i + 1], result[i]];
        swapped = true;
      }
    }
  } while (swapped);

  return result;
};

Complexity Analysis

• Time Complexity: O(n²), due to the nested loop.
• Space Complexity: O(n), as we store squared values in a new array.

Test Cases

console.log(sortedSquaresUsingBubleSort([-7, -3, 2, 3, 11])); // [4, 9, 9, 49, 121]
console.log(sortedSquaresUsingBubleSort([-4, -1, 0, 3, 10])); // [0, 1, 9, 16, 100]

Conclusion

Both approaches yield the correct results, but using the built-in sort method (O(n log n)) is significantly faster than Bubble Sort (O(n²)). However, understanding Bubble Sort is useful for learning sorting algorithms. For larger datasets, an even better approach would be the two-pointer technique, which sorts squares in O(n) time.

Do you have any other efficient solutions? Let me know in the comments! 🚀