educative.io

Educative

Solution without searching for non-negative number

Solution I came up is to have the two pointers at the start and at the end of the array and compare their absolute values. Square the larger one, put it to the result array and move the pointer forwards. Input array is iterated only once and I do not see any immediate issues with this approach. Code in C#:

public static int[] Square(int[] sortedArray)
{
    var result = new int[sortedArray.Length];
    var left = 0;
    var right = sortedArray.Length - 1;
    while (left < right)
    {
        if (Math.Abs(sortedArray[left]) < Math.Abs(sortedArray[right]))
        {
            result[right - left] = sortedArray[right] * sortedArray[right];
            right--;
        }
        else
        {
            result[right - left] = sortedArray[left] * sortedArray[left];
            left++;
        }
    }

    return result;
}
2 Likes

Thanks @Valdas for posting the solution. It looks great and efficient. We will definitely add this approach in the problem.

Came up with the same approach but your code is very easy to read and efficient.

I think this assumes the input contains a 0.

It will fail if you give it an input that does not have a 0 in it.

Example, [-2, -1, 2, 3]

I came up with following approach which does the job in-place. I do not see any issue with it. Let me know what do you guys think about it ?

def square_sorted_array(arr)
  return if arr.empty?

  _start, _end = 0, arr.length - 1

  while _end >= _start
    sq_start, sq_end = arr[_start] ** 2, arr[_end] ** 2

    # Start iterating the array in the reverse direction. For every index, figure out
    # which value should be used. Then place the unused number at `_start` index
    if sq_end >= sq_start
      arr[_end] = sq_end
    else
      arr[_start] = arr[_end]
      arr[_end] = sq_start
    end

    _end -= 1
  end

  arr.join(', ')
end