Leetcode Challenge #2
Tags: javascript, algorithms, beginners
Published: 2022-07-17 15:33:14

It has been two days since the last post. I found out that the [study plan](https://leetcode.com/study-plan/algorithm/) is supposed to be done daily. It unlocks new problem set everyday. So I'll just try to finish two days at a time (at least for the part I) and see if I need to adjust my schedule when I get to the second part .



## Today's problems

Today's topic: `Two pointers`

| ID | Name | Difficulty | Problem | Solution |
| --- | --- | --- | --- | --- |
| 977 | Squares of a Sorted Array | easy | [link](https://leetcode.com/problems/squares-of-a-sorted-array/) | [link](https://github.com/MiccWan/leetcode/blob/main/js/src/0977_squares_of_a_sorted_array.js) |
| 189 | Rotate Array | medium | [link](https://leetcode.com/problems/rotate-array/) | [link](https://github.com/MiccWan/leetcode/blob/main/js/src/0189_rotate_array.js) |
| 283 | Move Zeroes | easy | [link](https://leetcode.com/problems/move-zeroes/) | [link](https://github.com/MiccWan/leetcode/blob/main/js/src/0283_move_zeros.js) |
| 167 | Two Sum II - Input Array Is Sorted | medium | [link](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/) | [link](https://github.com/MiccWan/leetcode/blob/main/js/src/0167_two_sum_2.js) |

The topic for Day 2~5 is `Two pointers`. I'm not familiar with this word but I think the binary search method I used last time is a kind of two pointers.

I'm gonna skip problems 977, 283, 167 since they are actually pretty easy and the solutions were intuitive.

### 189. Rotate Array
The problem is really interesting.
Some simple methods like **slice+concat** or **rotate from the end** costs too much space (_O(n)_ and _O(k)_ respectively).
It tooks me some time to come up with an _O(1)_ space solution (though they are all _O(n)_ time).
The main idea is: 
If you move the **nums[0]** to **nums[k]**, and move the original **nums[k]** to **nums[2*k]**, ...(under modulo n, of course), it will come back to **nums[0]** at some point. But in some cases, this cycle does not contain all of the numbers. More precisely, only indexes in the form `0 + m * gcd(n, k)` will be included. So we need to repeat the same procedure but starts from `1 ~ gcd(n, k)`.

e.g. consider `n = 9, k = 6`
```
0 -> 6 -> 3 -> 0 -> ...
1 -> 7 -> 4 -> 1 -> ...
2 -> 8 -> 5 -> 2 -> ...
```

The resulting code:

```js
var rotate = function (nums, k) {
  const g = gcd(nums.length, k);

  for (let i = 0; i < g; i++) {
    let j = i;
    let tmp = nums[j];
    let next;
    while (next != i) {
      next = (j + k) % nums.length;
      [nums[next], tmp] = [tmp, nums[next]];
      j = next;
    }
  }
};
```

This solution is some kind of inflexible. So I checked leetcode discussion and found a beautiful magic. The key concept is:
`rotate(n, k) = reverse(0, n-1) + reverse(0, k-1) + reverse(k, n-1)`

e.g. consider `n = 7, n = 3`
```
   [1, 2, 3, 4, 5, 6, 7] // original
-> [7, 6, 5, 4, 3, 2, 1] // reverse(0, 6)
-> [5, 6, 7, 4, 3, 2, 1] // reverse(0, 2)
-> [5, 6, 7, 1, 2, 3, 4] // reverse(3, 6)
```

I haven't figured out how this magic was discovered, but it was really shocking for me.

## Additional Problem

Another two pointer problem I picked today is:

| ID | Name | Difficulty | Problem | Solution |
| --- | --- | --- | --- | --- |
| 11 | Container With Most Water | medium | [link](https://leetcode.com/problems/container-with-most-water/) | [link](https://github.com/MiccWan/leetcode/blob/main/js/src/0011_container_with_most_water.js) |

Unexpectedly, this problem took me about 40 minutes. According to the constraint, `n < 10^5`, _O(n^2)_ is not acceptable. So brute force enumeration is not good enough.

After tackled with many examples, I noticed that the area formula `(l - r) * Math.min(height[l], height[r])` only takes the minimum of the heights into account. Some greedy algorithm that prioritize the smaller height might come in handy in this case.

The final algorithm becomes: 
Starts from the most outer pair, record the area value and **shrink the smaller side inward** until it found some larger height. If the new area is bigger, update the record. Then repeat the steps again and again until the two pointers coinside. Note that if the heights of the both sides are the same, we have to shrink them at the same time, since the area will never get larger if only one side is shrinked.

Each time we shrink the border, the width of the container will become smaller. So we only needs to focus on **maximizing the heights**. The greedy algorithm works due to the property of area formula.

The complexities are _O(n)_ time and _O(1)_ space, since the process of shrinking border will be done in total of n-1 times and calculating the area is _O(1)_.

## Conclusion

The five problems above took me about 1.5 hrs, due to the unexpected difficulty of the last problem. Also, they are more difficult than the problems last time. The proof of correctness for the last algorithm even require some mathematical techniques, e.g. Loop invariant. But this series is not an algorithm tutorial, sorry I will skip those details.

So that's my challenge today, hope u enjoy. :)

---

<-- [Previous](https://dev.to/miccwan/leetcode-practice-day-1-1k) | [Home](https://dev.to/miccwan/my-leetcode-practice-diary-3415) | [Next](https://dev.to/miccwan/leetcode-challenge-3-1ki0) -->