2022-05-16

977. Squares of a Sorted Array

Description

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example 1:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

Example 2:

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

Constraints:

• 1 <= nums.length <= 10^4

• -10^4 <= nums[i] <= 10^4

• nums is sorted in non-decreasing order.

Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?

Solution

func sortedSquares(nums []int) []int {
    length := len(nums)
    left, right := 0, length-1
    res := make([]int, length)

    for pos := length - 1; pos >= 0; pos-- {
        if l, r := nums[left]*nums[left], nums[right]*nums[right]; l > r {
            res[pos] = l
            left++
        } else {
            res[pos] = r
            right--
        }
    }
    return res
}

189. Rotate Array

Description

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation: 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Constraints:

• 1 <= nums.length <= 105

• -231 <= nums[i] <= 231 - 1

• 0 <= k <= 105

Follow up:

• Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.

• Could you do it in-place with O(1) extra space?

Solution

func rev(nums []int) {
    length := len(nums)
    for i, j := 0, length-1; i < length/2; i++ {
        nums[i], nums[j-i] = nums[j-i], nums[i]
    }
}

func rotate(nums []int, k int) {
    k %= len(nums)
    rev(nums)
    rev(nums[k:])
    rev(nums[:k])
}