LeetCode 977: Squares of a Sorted Array Solution

Master LeetCode problem 977 (Squares of a Sorted Array), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

977. Squares of a Sorted Array

Easy

Array Two Pointers Sorting

Problem Explanation

Explanation

To solve this problem in O(n) time complexity, we can use a two-pointer approach. Since the input array is already sorted in non-decreasing order, we can compare the squares of the elements at the beginning and end of the array. We will place the larger square at the end of the result array, moving inward based on which square is larger. This way, we ensure that the result array is sorted in non-decreasing order.

Algorithm:

Initialize two pointers, left pointing to the start of the array and right pointing to the end of the array.
Initialize an index variable to track the position to insert the next square in the result array.
Compare the squares of the elements at the left and right pointers.
Add the larger square to the result array at the correct position based on the index variable.
Move the corresponding pointer inward and update the index variable.
Repeat steps 3-5 until both pointers meet in the middle of the array.

Time complexity: O(n) - we only iterate through the array once Space complexity: O(n) - for the result array

Solution Code

class Solution {
    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;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 977 (Squares of a Sorted Array)?

This page provides optimized solutions for LeetCode problem 977 (Squares of a Sorted Array) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 977 (Squares of a Sorted Array)?

The time complexity for LeetCode 977 (Squares of a Sorted Array) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 977 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 977 in Java, C++, or Python.

Back to LeetCode Solutions