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.

Example

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].

Input/Output

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

    A sorted array of integers.

    Constraints:
    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

upup.png

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.

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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