Squares of a Sorted Array
Similar Problems:
- 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
// 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 }
Share It, If You Like It.