Leetcode: Squares of a Sorted Array Posted on January 21, 2019September 23, 2019 by braindenny Squares of a Sorted Array Similar Problems: CheatSheet: Leetcode For Code Interview Tag: #twopointer, #mergesort 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 // https://code.dennyzhang.com/squares-of-a-sorted-array // Basic Ideas: 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 // https://code.dennyzhang.com/squares-of-a-sorted-array // Basic Ideas: 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 Post navigation Leetcode: Valid Mountain ArrayLeetcode: Largest Perimeter Triangle Leave a Reply Cancel replyYour email address will not be published.Comment Name Email Website