977. Squares of a Sorted Array #

Problem #

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

Example 1:


Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Example 2:


Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Note:

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A is sorted in non-decreasing order.

Problem Summary #

Given an already sorted array, the returned array must also be sorted, and each element in the array is obtained by squaring each number in the original array.

Solution Approach #

Since the original array is sorted, this problem should make full use of this characteristic to reduce time complexity.

In the final returned array, the last position is the maximum value. This value should come from either the maximum value or the minimum value of the original array, so we can start arranging the final array from its last position. Use 2 pointers to point to the beginning and end of the original array respectively, calculate the squared values respectively, then compare the two. Put the larger one at the back of the final array. Then move the pointer corresponding to the larger one. Continue until the two pointers meet, and the final array will be fully arranged.

Code #


package leetcode

import "sort"

// Solution One
func sortedSquares(A []int) []int {
	ans := make([]int, len(A))
	for i, k, j := 0, len(A)-1, len(ans)-1; i <= j; k-- {
		if A[i]*A[i] > A[j]*A[j] {
			ans[k] = A[i] * A[i]
			i++
		} else {
			ans[k] = A[j] * A[j]
			j--
		}
	}
	return ans
}

// Solution Two
func sortedSquares1(A []int) []int {
	for i, value := range A {
		A[i] = value * value
	}
	sort.Ints(A)
	return A
}