Leetcode: Squares of a Sorted Array

Posted on January 21, 2019September 10, 2019 by braindenny

Squares of a Sorted Array

Similar Problems:

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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Two pointers

// Blog link: https://code.dennyzhang.com/squares-of-a-sorted-array
// Basic Idea: Two pointers
// Complexity: Time O(n), Space O(1)
func sortedSquares(A []int) []int {
    res := make([]int, len(A))
    i, j := 0, len(A)-1
    for k:=len(A)-1; k>=0; k-- {
        v1, v2 := A[i]*A[i], A[j]*A[j]
        if v1>=v2 {
            res[k] = v1
            i++
        } else {
            res[k] = v2
            j--
        }
    }
    return res
}

Merge sort

// Blog link: https://code.dennyzhang.com/squares-of-a-sorted-array
// Basic Idea: merge sort
// Complexity: Time O(n), Space O(n)
func sortedSquares(A []int) []int {
    B1, B2 := []int{}, []int{}
    for _, v := range A {
        if v < 0 {
            B1 = append(B1, v*v)
        } else {
            B2 = append(B2, v*v)
        }
    }
    // Merge B1 and B2
    i, j := len(B1)-1, 0
    res := []int{}
    for i>=0 && j<len(B2) {
        if B1[i] <= B2[j] {
            res = append(res, B1[i])
            i--
        } else {
            res = append(res, B2[j])
            j++
        }
    }
    for i>=0 {
        res = append(res, B1[i])
        i--        
    }
    for j<len(B2) {
        res = append(res, B2[j])
        j++
    }
    return res
}

Post Views: 0