How to solve ‘sortedSquaredArray’ in CodeFights

The Problem

Note: Come up with a linear solution, since that is what you would be asked to do in an interview.

You have a sorted array of integers. Write a function that returns a sorted array containing the squares of those integers.


For array = [-6, -4, 1, 2, 3, 5], the output should be
sortedSquaredArray(array) = [1, 4, 9, 16, 25, 36].

The array of squared integers from array is: [36, 16, 1, 4, 9, 25]. When sorted, it becomes: [1, 4, 9, 16, 25, 36].


  • [time limit] 4000ms (py)
  • [input] array.integer array

    A sorted array of integers.

    1 ≤ array.length ≤ 104,
    -104 ≤ array[i] ≤ 104.

  • [output] array.integer

    A sorted array of integers composed of the squared integers from the input array.

The Solution


The Explanation

We start from both ends and compare the smallest and largest numbers in the array. (The reason we need to do this is we may have negative numbers whose squared value will be greater than some of the positive numbers.) Every time we pick something from the start, we move the index forward, every time we pick something from the end, we move it backward.

We add the number we pick to a new array. The array is now in non-increasing (or decreasing) order. We return the reversed array.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s