[Array] Squares of a Sorted Array - Easy

The “Squares of a Sorted Array” problem is about changing an array of integers. This array is sorted in non-decreasing order. We need to create a new array. Each element in the new array will be the square of the original elements. This new array also needs to be sorted in non-decreasing order. We can do this task easily using different methods. We can take advantage of the fact that the input array is already sorted. This helps us to make the squaring and sorting faster.

In this article, we will look at different ways to solve the “Squares of a Sorted Array” problem. We will check the best method using two pointers in Java, Python, and C++. We will also see a simple method for each of these programming languages. After that, we will compare these methods. We will also look at their time and space complexities. Finally, we will answer some common questions about this topic.

  • Understanding Array Squares of a Sorted Array Easy Problem
  • Optimal Approach Using Two Pointers in Java
  • Optimal Approach Using Two Pointers in Python
  • Optimal Approach Using Two Pointers in C++
  • Naive Approach for Array Squares in Java
  • Naive Approach for Array Squares in Python
  • Naive Approach for Array Squares in C++
  • Comparative Analysis of Approaches for Array Squares
  • Time Complexity and Space Complexity Analysis
  • Frequently Asked Questions

For more information on array manipulation, we can check related topics like Array Two Sum and Array Remove Duplicates from Sorted Array.

Optimal Approach Using Two Pointers in Java

We can solve the problem of squaring a sorted array by using the two-pointer technique. This method helps us arrange the squares in non-decreasing order. We do not need to sort again since the original array is already sorted.

Implementation Steps

  1. Initialize Pointers: We start with two pointers. One pointer is at the beginning (left) and the other is at the end (right) of the array.
  2. Create Result Array: We make a new array to hold the squared values.
  3. Fill Result Array: We go from the end of the result array to the beginning. We compare the absolute values at the left and right pointers:
    • If the absolute value at left is bigger, we square it. Then we put this value in the current position of the result array. After that, we move the left pointer to the right.
    • If not, we square the value at the right pointer, put it in the result array, and move the right pointer to the left.
  4. Continue Until Pointers Meet: We repeat this until the left pointer goes beyond the right pointer.

Java Code Example

public class SquaresOfSortedArray {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        int left = 0, right = n - 1;

        for (int i = n - 1; i >= 0; i--) {
            if (Math.abs(nums[left]) > Math.abs(nums[right])) {
                result[i] = nums[left] * nums[left];
                left++;
            } else {
                result[i] = nums[right] * nums[right];
                right--;
            }
        }
        return result;
    }
}

Explanation of the Code

  • The sortedSquares method takes an integer array nums as input.
  • We create the result array with the same size as nums.
  • We use a for loop to fill the result array from the end to the start. We do this based on the comparison of squared values from the left and right pointers.
  • In the end, we return the sorted array of squares.

This method helps us calculate the squares of a sorted array quickly. We get a time complexity of O(n) and a space complexity of O(n). This makes it a good choice for solving this problem.

Optimal Approach Using Two Pointers in Python

We can solve the “Squares of a Sorted Array” problem in Python by using the two-pointer technique. This method helps us handle the sorted array well. We can find the squares in one go while keeping them in order.

Algorithm Steps:

  1. We start with two pointers. One pointer is at the start (left) and the other is at the end (right) of the array.
  2. We make an output array to keep the squares in sorted order.
  3. We will loop while left is less than or equal to right:
    • We compare the absolute values of the numbers at both pointers.
    • We square the bigger absolute value and put it at the end of the output array.
    • We move the pointer that had the bigger value inward.
  4. We keep going until we process all the numbers.

Python Code:

def sortedSquares(nums):
    left, right = 0, len(nums) - 1
    result = [0] * len(nums)
    position = len(nums) - 1

    while left <= right:
        if abs(nums[left]) > abs(nums[right]):
            result[position] = nums[left] ** 2
            left += 1
        else:
            result[position] = nums[right] ** 2
            right -= 1
        position -= 1

    return result

Example:

If we have an input array nums = [-4, -1, 0, 3, 10], the output will be:

print(sortedSquares([-4, -1, 0, 3, 10]))  # Output: [0, 1, 9, 16, 100]

This way runs in O(n) time, where n is the number of items in the array. It also uses O(n) space for the result array. This method is good because it lets us handle the squares of a sorted array well while keeping the order in the results.

For more reading on similar problems, check Array Two Sum and Array Remove Duplicates from Sorted Array.

Optimal Approach Using Two Pointers in C++

We can solve the problem of finding the squares of a sorted array using the two-pointer method. This way is simple and it helps us create a new array with the squares of the original numbers while keeping the order. Here’s how we do it:

  1. Initialization: We set two pointers. One pointer is at the start (left) and the other is at the end (right) of the input array.
  2. Comparison: We compare the absolute values of the numbers at both pointers. We will place the bigger square at the end of the result array.
  3. Placement: We move the pointer closer (we can move the left pointer up or the right pointer down) based on which value is bigger.
  4. Result Construction: We fill the result array from the end to the start.

Here’s the C++ code for this method:

#include <vector>
#include <algorithm>

std::vector<int> sortedSquares(std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> result(n);
    int left = 0, right = n - 1;

    for (int i = n - 1; i >= 0; --i) {
        if (std::abs(nums[left]) > std::abs(nums[right])) {
            result[i] = nums[left] * nums[left];
            left++;
        } else {
            result[i] = nums[right] * nums[right];
            right--;
        }
    }
    
    return result;
}

Key Points:

  • The time complexity is O(n). Here, n is the number of items in the input array.
  • The space complexity is also O(n) because we need the output array.
  • This method makes sure the squares are sorted without needing to sort again.

We can use this fast two-pointer technique in other problems too. For example, we can look at problems like Array Best Time to Buy and Sell Stock to learn more about working with arrays.

Naive Approach for Array Squares in Java

We can solve the “Squares of a Sorted Array” problem in Java using a simple way. This method looks at each number in the input array. We square each number and save the results in a new array. This way does not use the fact that the array is sorted. It has a time complexity of O(n). Here n is the number of elements in the input array.

Here is how we can write the naive approach in Java:

public class SquaresOfSortedArray {
    public static int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        
        for (int i = 0; i < n; i++) {
            result[i] = nums[i] * nums[i];
        }
        
        Arrays.sort(result); // Sorting the squared values
        return result;
    }
    
    public static void main(String[] args) {
        int[] input = {-4, -1, 0, 3, 10};
        int[] output = sortedSquares(input);
        System.out.println(Arrays.toString(output)); // Output: [0, 1, 9, 16, 100]
    }
}

Key Points:

  • We square each number and then sort the new array.
  • This way is easy to understand but not fast for big lists because of the sorting.
  • The total time complexity is O(n log n) because we need to sort the data.

This naive way can be a good start. But if we want to make it better, we can use other methods, like the two-pointer technique.

Naive Approach for Array Squares in Python

We can use the naive approach to square a sorted array. This means we go through the array. We square each number. Then, we return a new array. This method does not use the fact that the input array is sorted. So, we get a time complexity of O(n) for squaring. Then, we have O(n log n) for sorting the new array.

Here is how we can do it in Python:

def sortedSquares(nums):
    # Square each number in the array
    squared = [x * x for x in nums]
    # Sort the squared numbers
    squared.sort()
    return squared

# Example usage
nums = [-4, -1, 0, 3, 10]
result = sortedSquares(nums)
print(result)  # Output: [0, 1, 9, 16, 100]

In this code, we use a list comprehension to square each number. Then we use the sort() function to sort the squared numbers. This method is simple. But it is not the best for big datasets. The extra sorting step is not needed when we can use better methods.

For better ways to handle arrays, we can check out the two-pointer technique. This is in the sections about optimal approaches. If we want to see similar problems, we can read articles like Array Two Sum or Array Remove Duplicates from Sorted Array.

Naive Approach for Array Squares in C++

The naive way to find the squares of a sorted array is to go through each item in the array. We square the number and then put the squared numbers in a new array. This way is simple but not very good in time and space when we compare it to better methods.

Implementation

Here is a simple C++ code for the naive approach:

#include <iostream>
#include <vector>
using namespace std;

vector<int> sortedSquares(vector<int>& nums) {
    vector<int> result(nums.size());
    for (int i = 0; i < nums.size(); i++) {
        result[i] = nums[i] * nums[i];
    }
    sort(result.begin(), result.end());
    return result;
}

int main() {
    vector<int> nums = {-4, -1, 0, 3, 10};
    vector<int> squared = sortedSquares(nums);
    
    for (int num : squared) {
        cout << num << " ";
    }
    return 0;
}

Explanation

  • First, the algorithm makes a result vector that is the same size as the input array.
  • Then, it goes through each number in the input array, squares it, and puts that in the same place in the result vector.
  • After we square all the numbers, we sort the result vector to keep the order.

Time Complexity

  • The time complexity is O(n log n) because of the sorting step. Here, n is the number of items in the input array.

Space Complexity

  • The space complexity is O(n) since we use another array to keep the squared numbers.

This naive way works fine for small arrays but is not the best for bigger data sets. For a better solution, we can use the two-pointer method which can get O(n) time complexity.

For more related problems, we can look at Array Two Sum or Array Remove Duplicates from Sorted Array.

Comparative Analysis of Approaches for Array Squares

When we solve the problem of squaring a sorted array, we can use two main ways. One is the optimal two-pointer technique. The other is the naive approach. Let us look at both methods.

Optimal Approach Using Two Pointers

The two-pointer technique is good for this problem. It uses the sorted nature of the array. One pointer starts at the beginning (left) and the other at the end (right) of the array. We compute squares from both ends. The larger squared value goes into the result array from the end to the beginning.

Java Implementation:

public int[] sortedSquares(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    int left = 0, right = n - 1, index = n - 1;
    
    while (left <= right) {
        int leftSquare = nums[left] * nums[left];
        int rightSquare = nums[right] * nums[right];
        
        if (leftSquare > rightSquare) {
            result[index--] = leftSquare;
            left++;
        } else {
            result[index--] = rightSquare;
            right--;
        }
    }
    return result;
}

Python Implementation:

def sortedSquares(nums):
    n = len(nums)
    result = [0] * n
    left, right, index = 0, n - 1, n - 1
    
    while left <= right:
        leftSquare = nums[left] ** 2
        rightSquare = nums[right] ** 2
        
        if leftSquare > rightSquare:
            result[index] = leftSquare
            left += 1
        else:
            result[index] = rightSquare
            right -= 1
        index -= 1
    return result

C++ Implementation:

vector<int> sortedSquares(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n);
    int left = 0, right = n - 1, index = n - 1;
    
    while (left <= right) {
        int leftSquare = nums[left] * nums[left];
        int rightSquare = nums[right] * nums[right];
        
        if (leftSquare > rightSquare) {
            result[index--] = leftSquare;
            left++;
        } else {
            result[index--] = rightSquare;
            right--;
        }
    }
    return result;
}

Naive Approach

The naive approach squares each element in the original array. Then we sort the new array. This method is easier but not as efficient, especially for big arrays.

Java Implementation:

public int[] sortedSquares(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        nums[i] *= nums[i];
    }
    Arrays.sort(nums);
    return nums;
}

Python Implementation:

def sortedSquares(nums):
    return sorted(x * x for x in nums)

C++ Implementation:

vector<int> sortedSquares(vector<int>& nums) {
    for (int& num : nums) {
        num *= num;
    }
    sort(nums.begin(), nums.end());
    return nums;
}

Performance Comparison

  • Time Complexity:
    • Optimal Approach: O(n) because we make one pass through the array with two pointers.
    • Naive Approach: O(n log n) because we need to sort the squared values.
  • Space Complexity:
    • Both ways need O(n) space for the output array.

We prefer the two-pointer technique because it has linear time complexity. This makes it better for larger datasets than the naive sorting method. For more about array manipulation, we can read articles like Array Two Sum and Array Remove Duplicates from Sorted Array.

Time Complexity and Space Complexity Analysis

We can solve the problem of finding the squares of a sorted array in different ways. Each way has its own time and space complexity.

Optimal Approach Using Two Pointers

  • Time Complexity: O(n)
    We go through the array one time to fill the result array. This means it takes linear time.

  • Space Complexity: O(n)
    We create a separate result array to keep the squares of the elements.

Naive Approach

  • Time Complexity: O(n)
    The naive way also goes through the input array one time. It calculates and stores each square.

  • Space Complexity: O(n)
    Like the optimal way, it needs extra space for the results.

Comparative Analysis

For both the optimal and naive ways, the time complexity stays linear (O(n)). This shows good performance even with bigger arrays. But we may choose a method based on things like space limits or how easy it is to do.

In short, both ways can do the job of squaring elements in a sorted array. They keep a linear time complexity and need linear space for the output.

For more reading on similar array problems, we can check these articles: - Array Maximum Subarray - Easy - Array Remove Duplicates from Sorted Array - Easy

Frequently Asked Questions

1. What is the problem statement for Squares of a Sorted Array?

The “Squares of a Sorted Array” problem is about changing a sorted integer array. We need to replace each number with its square. Then we return a new array that is also sorted. This task is important for working with sorted data. It is a common problem for beginners. Knowing this problem helps us understand more complex tasks with arrays.

2. How can I solve the Squares of a Sorted Array problem using the two-pointer technique?

To solve the “Squares of a Sorted Array” problem well, we can use a two-pointer method. We start with one pointer at the start of the array and another at the end. We compare the squares of the numbers at both pointers. Then we fill a new result array from the back to the front. This way, we keep a good time complexity of O(n). This makes it a good solution.

3. What is the time complexity of the optimal solution for this problem?

The best solution for the “Squares of a Sorted Array” problem uses the two-pointer method. Its time complexity is O(n). Each element in the array is processed once. On the other hand, the simple method has a higher time complexity because it needs to sort again. This makes the best method much better for bigger datasets.

4. Can you give an example of the naive approach to solve this problem?

In the simple approach for the “Squares of a Sorted Array” problem, we first square each element of the array. Then we sort the new array. Here is a simple Java example:

int[] sortedSquares(int[] nums) {
    int[] squares = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
        squares[i] = nums[i] * nums[i];
    }
    Arrays.sort(squares);
    return squares;
}

This method works, but it is not as good as the two-pointer method.

5. Where can I find more resources on similar array problems?

If we want to learn more about array problems and algorithms, we can look at articles on related topics. For example, we can check out the Array - Two Sum problem. This is another basic challenge that uses similar ideas. These resources can help us see more about how to work with arrays.