Efficient way of Square of a Sorted Array-CodePudding

I am solving leetcode solution. The question is

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]

I solved this through map and then use sorted() for sorting purpose and lastly converted in toIntArray().

My solution

class Solution {
    fun sortedSquares(nums: IntArray): IntArray {
     return nums.map { it * it }.sorted().toIntArray()
    }
}

After all I am taking a look in the discuss success, I found this solution

class Solution {
    fun sortedSquares(A: IntArray): IntArray {
        
        // Create markers to use to navigate inward since we know that
        // the polar ends are (possibly, but not always) the largest
        var leftMarker = 0
        var rightMarker = A.size - 1
        
        // Create a marker to track insertions into the new array
        var resultIndex = A.size - 1
        val result = IntArray(A.size)
        
        // Iterate over the items until the markers reach each other.
        // Its likely a little faster to consider the case where the left
        // marker is no longer producing elements that are less than zero.
        while (leftMarker <= rightMarker) {
            // Grab the absolute values of the elements at the respective
            // markers so they can be compared and inserted into the right
            // index.
            val left = Math.abs(A[leftMarker])
            val right = Math.abs(A[rightMarker])
            
            // Do checks to decide which item to insert next.
            result[resultIndex] = if (right > left) {
                rightMarker--
                right * right
            } else {
                leftMarker  
                left * left
            }
            
            // Once the item is inserted we can update the index we want
            // to insert at next.
            resultIndex--
        }
        
        return result
    }
}

The guy also mention in the title Kotlin -- O(n), 95% time, 100% space

So my solution is equal in time and space complexity with other solution with efficient time and space? Or Is there any better solution?

CodePudding user response：

So my solution is equal in time and space complexity with other solution with efficient time and space?

No, your solution runs in O(n log n) time, as it relies on sorted(), which likely runs in O(n log n). Since the alternative solution does not sort the items, it indeed runs on O(n) time. Both solutions use O(n) space, although your solution uses three times as much space (each of map, sorted and toIntArray create a copy of the input).