DEV Community

Cover image for Leetcode Challenge #2
Micc Wan
Micc Wan

Posted on • Updated on

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

ID Name Difficulty Problem Solution
977 Squares of a Sorted Array easy link link
189 Rotate Array medium link link
283 Move Zeroes easy link link
167 Two Sum II - Input Array Is Sorted medium link link

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 -> ...
Enter fullscreen mode Exit fullscreen mode

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;
    }
  }
};
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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 link

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

Top comments (4)

Collapse
 
santoshmore088 profile image
santosh more

please do mention complexity also

Collapse
 
miccwan profile image
Micc Wan

Sure, I'll add the complexities on the problems I discussed!

Collapse
 
santoshmore088 profile image
santosh more

hey it will be really great if you could share every problems approach. notes or something like this.

Collapse
 
miccwan profile image
Micc Wan • Edited

Hi, thank u for ur advice.
I totally agree that this helps a lot with my English writing practice and I'm glad to help others to solve the problem. But unfortunately it might takes way more time then I expected.
Take challenge #2 for example, I finished the 5 problems with 1.5hr and wrote down this article with 2.5hrs. Sorry that I have to limit the time spent in a reasonable range.
If my writing skill gets improved in the future, I'll try to write down more about the problems :)
BTW, if u need some explanation or solution for the problems, go check the "Discuss" section in the leetcode problem page. Many programmers provide their solutions with good explanation with it.
E.g.: leetcode.com/problems/squares-of-a...