Two Pointers: Given an array, sort the array by making element squares

Problem Statement:

You are given an array of both positive and negative integers.

You need to sort the array by making the square of the numbers.

Example:

Input: arr = [-3, -2, -1, 3, 4]
Output: arr = [1, 4, 9, 9, 16]

Solution 1: Brute force approach

Square the number in the array.
Then sort the array

Time Complexity: O(nlogn)
Space Complexity: O(1)

Solution 2: Two pointers solution

We will take help of the fact that the array is already sorted.

We can solve this problem by using two pointers approach and solve in-place.

Take 2 pointer left starts from left of the array and right starts from the right of the array

Take temp array to store the square of the values

If abs(left) > abs(right)then store in the left element square of the value in the result array and move the left pointer.

Else store in the right element square of the value in the result array and move the right pointer.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

void solution_1(vector<int>& arr, int n)
{

    for (int i = 0; i < n; i++)
        arr[i] = arr[i] * arr[i];

    sort(arr.begin(), arr.end());
}


void solution_2(vector<int>& arr, int n)
{
    int left = 0, right = n - 1;
    int result[n];

    for (int index = n - 1; index >= 0; index--) 
    {
      
      	if (abs(arr[left]) > arr[right]) 
        {
            result[index] = arr[left] * arr[left];
            left++;
        }
        else 
        {
            result[index] = arr[right] * arr[right];
            right--;
        }
    }

    for (int i = 0; i < n; i++)
        arr[i] = result[i];
}


int main()
{
    vector<int> arr = { -3, -2, -1, 3, 4 };
    int n = arr.size();

    solution_1(arr, n);

    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";

    cout << endl;

	arr = { -3, -2, -1, 3, 4 };
    n = arr.size();

    solution_2(arr, n);

    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";

    return 0;
}

Output

1 4 9 9 16 
1 4 9 9 16