Array101 Squares of a Sorted Array in Go

Accepted Solutions Runtime Distribution

Accepted Solutions Memory Distribution

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 <= 104
• -104 <= nums[i] <= 104
• 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?

My code

func sortedSquares(nums []int) []int {
    length := len(nums)
    lp, rp := 0, length-1
    temp := make([]int, length)

    for lp <= rp {
        length--
        if nums[lp]*nums[lp] >= nums[rp]*nums[rp] {
            temp[length] = nums[lp] * nums[lp]
            lp++
        } else {
            temp[length] = nums[rp] * nums[rp]
            rp--
        }
    }
    return temp
}

https://go.dev/play/p/76w6n1tm990

• Because this is already ordered, I just needed to square values when comparing them.
• First I tried to use in-place array, but it didn't work when negative numbers are in array.
• So I made array to store squared number.
• length used as writepointer.

sample 12 ms submission

func sortedSquares(nums []int) []int {
    l := 0
    r := len(nums) - 1
    ans := make([]int, len(nums))

    for i := len(nums)-1; i >= 0; i-- {
        rSq := nums[r] * nums[r]
        lSq := nums[l] * nums[l]
        if lSq < rSq {
            ans[i] = rSq
            r--
        } else {
            ans[i] = lSq
            l++
        }
    }

    return ans
}

• This code is simple.
• For loop is doing until i is 0.

sample 16 ms submission

func sortedSquares(nums []int) []int {
    n := len(nums)

    ans := make([]int, n)

    right := n - 1
    left := 0

    for i := n - 1; i >= 0; i-- {
        targetValue := 0

        if abs(nums[right]) > abs(nums[left]) {
            targetValue = nums[right]
            right--
        } else {
            targetValue = nums[left]
            left++
        }

        ans[i] = targetValue * targetValue
    }

    return ans
}

func abs(x int) int {
    if x > 0 {
        return x
    }
    return -x
}

• This code uses abs function.
• First, this code compares both values.
• Second, the graeter number will be allocated to targetValue
• Third, doubled target value will be allocatd to end of array.

sample 6700 KB submission

func sortedSquares(nums []int) []int {
    output := make([]int, len(nums))
    l := 0
    r := len(nums)-1
    i := len(nums)-1

    for l <= r {
        if math.Abs(float64(nums[l])) <= math.Abs(float64(nums[r])) {
            output[i] = nums[r]*nums[r]
            r--
        } else {
            output[i] = nums[l]*nums[l]
            l++
        }
        i--
    }

    return output
}

• I don't know why float64 was used.

• Embedded abs function requests float64.

  Line 8: Char 25: cannot use nums[l] (type int) as type float64 in argument to math.Abs (solution.go) Line 8: Char 46: cannot use nums[r] (type int) as type float64 in argument to math.Abs (solution.go)

sample 6800 KB submission

func sortedSquares(nums []int) []int {
    A_end, B_start := -1, 0
    response := make([]int, len(nums))
    i := 0

    for i := 0 ; i < len(nums) ; i++ {
        if nums[i] > 0 && A_end < 0 {
            A_end = i - 1
            B_start = i
        }

        nums[i] = nums[i]*nums[i]
    }

    if len(nums) == 1 {
        return nums
    }

    if A_end == 0 {
      return nums
    }

    if B_start == 0 {
        for j := len(nums) -1 ; j >= 0; j-- {
            response[i] = nums[j]
            i += 1
        }

        return response            
    }

    for j, k := A_end, B_start;; {
        if j < 0 {            
            response[i] = nums[k]
            k += 1            
        } else if k > len(nums) - 1 {
            response[i] = nums[j]
            j -= 1
        } else if nums[j] < nums[k] {
            response[i] = nums[j]
            j -= 1
        } else {
            response[i] = nums[k]
            k += 1
        }

        i += 1

        if j == -1 && k > len(nums) - 1 {
            return response
        }

    }
}

• Looks complicated code.
• When values are all negative then B_start will have 0.
• So all values will be reverted to new array(response).
• When values are all positive then A_end will have 0.
• So all values will be return intactly after squared.
• A_end will point less than 1
• B_start will point more than 0
• Based on this, they will check which is greater.
• Somehow two pointer.
• But looks so complicated

sample 7000 KB submission

 func sortedSquares(nums []int) []int {
    negatives := []int{}
    result := []int{}

    index := 0
    for index < len(nums) && nums[index] < 0 {
        negatives = append(negatives, nums[index]*nums[index])
        index++
    }

    negatives_index := index - 1

    for len(result) < len(nums) {
        if index < len(nums) && negatives_index >= 0 {
            result, index, negatives_index = AppendSmallerSquare(nums, index, negatives, negatives_index, result)
        } else if negatives_index < 0 {
            result, index = AppendPositivesSquare(nums, index, result)
        } else {
            result, negatives_index = AppendNegativesSquare(negatives, negatives_index, result)
        }
    }

    return result
}

func AppendSmallerSquare(nums []int, index int, negatives []int, negatives_index int, result []int) ([]int, int, int) {
    non_negative_element := nums[index] * nums[index]
    negative_element := negatives[negatives_index]
    if non_negative_element <= negative_element {
        result = append(result, non_negative_element)
        index++
    } else {
        result = append(result, negative_element)
        negatives_index--
    }

    return result, index, negatives_index
}

func AppendPositivesSquare(nums []int, index int, result []int) ([]int, int) {
    result = append(result, nums[index]*nums[index])
    index++
    return result, index
}

func AppendNegativesSquare(negatives []int, negatives_index int, result []int) ([]int, int) {
    result = append(result, negatives[negatives_index])
    negatives_index--
    return result, negatives_index
}

• First, this code checks how many negative this array has.
• If array has, then It will be allocated to negatives array after doubled.
• Index shows how many negatives there are.
• for loop is running until result length is same with nums length(original)
• If with SmallerSuqare will run if it has both negative and positive.
• Index will point positive one(grater than -1) and negatives_index will point negarive one(less than 0).
• Else if with Positive Suqare will run if negative index is -1
• Second Else if will work when index is same with len(nums)