Leetcode Challenge #2

It has been two days since the last post. I found out that the study plan 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

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:

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:

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 | Home | Next -->