Day 2 - Two pointers O(n)
Published: 2023-04-08 12:52:07


![Day 2 algorithm problem sets of Two Pointers](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wvbrvw69p8p2rwrlq5do.png)

## Question: 977. Squares of a Sorted Array

Given an integer array nums sorted in **non-decreasing order**, return an array of the squares of each number 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?

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


## First attempt: using bubble sort
- My initial thought was 'do I have to sort this before or after squaring each number? which sort method would be efficient?'
- To make it less than O(N2), it seemed like I have use heap sort. But heap sort still is not O(N), which **follow-up** question prefers. It is O(n*logn).
- For here, though I knew that bubble sort is O(N2), I just wanted to practice bubble sort, which is one of the simple sorts we usually first learn.

## Second attempt: using two pointers and aim O(N)
- It seemed like I can take an advantage of **non-decreasing order**. 
- I tried to think of ways, asking `how to move a negative number or its squared value to the correct position?`
- It seemed like I had to compare the value of `square(positive num) vs. square(negative num)`
- I also referred to [this post](https://leetcode.com/problems/squares-of-a-sorted-array/solutions/3355848/two-pointers-o-n-with-explanation/?envType=study-plan&id=algorithm-i) at the end to refine my solution.
- In this solution, it adds bigger **squared(value)** to a beginning of `result array`. And then reverse the `result array` at the end to make it **non-decreasing order*.
- In my solution, I started adding **squared(value)** from the end of `result array`. And then make it to its index 0.
- Here, I first thought I can use `upper_index` as and index for adding new item to `result array`. But two different conditional cases returned different outcomes. So I created `last_index` variable to be clear and working for both cases. 

### Psuedo code
```js
var sortedSquares = function(nums) {
    // 2. O(n) with two pointers
    // #1. if all nums are positive, just return simple squared result.
   
    // #2. if there's negative nums, we need two pointers leftmost, rightmost
    // similar to binary search two pointers.
    // compare two pointers' squared values
    // and add bigger number to the end of the list, aka at upper_bound index.
    let lower_bound = 0;
    let upper_bound = nums.length - 1;
    let reordered_arr = [];
    while(lower_bound <= upper_bound) {
        // if lower val is bigger than upper val
        // add lower(bigger) val to upper index of new arr
        // move lower index + 1

        // if upper val is bigger than lower val
        // add upper(bigger) val to upper index of new arr
        // move upper index - 1
       
    }
    return reordered_arr;

};

```

### Final code
```js
var sortedSquares = function(nums) {
    // 2. O(n) with two pointers
    // #1. if all nums are positive, just return simple squared result.
    let has_negative = false;
    for(let i = 0; i < nums.length; i++) {
       if(nums[i] < 0) {
           has_negative = true;
           break;
       }
    }
    if(!has_negative) {
        let squared_arr = [];
        for(let i = 0; i < nums.length; i++) {
            squared_arr.push(nums[i]*nums[i]);
        }
        return squared_arr;
    }
    // #2. if there's negative nums, we need two pointers leftmost, rightmost
    let lower_bound = 0;
    let upper_bound = nums.length - 1;
    let reordered_arr = [];
    let last_index = upper_bound;
    while(lower_bound <= upper_bound) {
        if(nums[lower_bound]*nums[lower_bound] >= nums[upper_bound]*nums[upper_bound]) {
            reordered_arr[last_index] = nums[lower_bound]*nums[lower_bound];
            lower_bound += 1;
        } else if(nums[upper_bound]*nums[upper_bound] > nums[lower_bound]*nums[lower_bound]) {
            reordered_arr[last_index] = nums[upper_bound]*nums[upper_bound];
            upper_bound -= 1;
        }
        last_index -= 1;
        // i initially put the squared num to [upper_bound] index, but it messes the insertion.
        // using last_index is more clear
    }
    return reordered_arr;
};

```


### Similar algorithm problems
- [88. Merge Sorted Array](https://leetcode.com/problems/merge-sorted-array/)
- [360. Sort Transformed Array](https://leetcode.com/problems/sort-transformed-array/)

![Similar algorithm problems](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2gvb54wdhgr9bua1vhma.png)