Forem: Micc Wan

Leetcode Challenge (The end)

Micc Wan — Thu, 25 Aug 2022 07:17:03 +0000

It's been a while since the last post.

I'm sorry about that I am here to tell you this series will stop here, due to my personal reasons :(

I might continue updating the GitHub repo sometimes (and maybe not), but there won't be any new post.

Happy programming everyone :)

Leetcode Challenge #4 (Postponed)

Micc Wan — Mon, 25 Jul 2022 13:34:45 +0000

I finished the problems last Thursday using my notebook, but I forgot to push them to GitHub. I won't have access to my notebook for a while. So challenge #4 will be updated after I get my notebook back.

Leetcode Challenge #3

Micc Wan — Tue, 19 Jul 2022 16:46:50 +0000

Hi there! Today we are going to finish the last part of Two pointers.

Today's problems

Today's topic: Two pointers

ID	Name	Difficulty	Problem	Solution
344	Reverse String	easy	link	link
557	Reverse Words in a String III	easy	link	link
876	Middle of the Linked List	easy	link	link
19	Remove Nth Node From End of List	medium	link	link

There are 2 string manipulation problems and 2 linked list problems here.

344. Reverse String

This is a simple reverse problem. Just set the 2 pointers at the begining and end at the same time, swap the values at the pointers, and then move them inward. Repeat the process until left >= right.

The complexities are O(n) time and O(1) extra space.

NOTE: The problem was asking for in-place reverse, while JavaScript does not support in-place string manipulation. So leetcode sends char array as input. So sweet!

577. Reverse Words in a String III

In-place reverse is not required for this problem, so it's time to abuse the power of high-level language. LOL!
Only one line is needed. The split+join combo is a powerful tool dealing with string manipulation. Use it along with map to manipulate each segment.

return s.split(' ').map(x => x.split('').reverse().join('')).join(' ');

The complexities are O(n) time and O(n) extra space.

NOTE: O(1) extra space is impossible in this problem since the problem requires a new string as return instead of char array. And JS does not support in-place string manipulation.

876. Middle of the Linked List

A simple solution is to iterate through the linked list once to get the length. And iterate again for half of lengh to get the middle.

Another solution is maintain two pointers both starts at the head. In each iteration, the pointer A moves 2 steps while the pointer B move 1 step. This way, when pointer A reaches the end, pointer B is at the middle of the linked list.

Both solutions take O(n) time and O(1) extra space.

19. Remove Nth Node From End of List

Same as the last problem, a simple solution is to count the length first. And iterate again to get the n-th node from the end.

Another way is to set pointer A at the begining and set pointer B n step(s) ahead. Then move both of them at the same time, while pointer B reaches the end, pointer A is at the n-th node from the end.

Both solutions take O(n) time and O(1) extra space.

NOTE: For the second solution, be careful with some special cases like: removing the first element (so we have to return the second element as head instead of the removed head).

Additional Problem

ID	Name	Difficulty	Problem	Solution
2	Add two numbers	medium	link	link

I forgot to set the filter tag:two pointers, so the additional problem is not about two pointers.

The problem is simply implementing the integer addition the way we've been taught in elementary school.

Starts from the right most digit, add them up, record the modulo sum and carry, repeat the process in the next digit.

There are two more things need to handle carefully. The numbers may not be in same length and don't forget to add the last carry.

The complexities are O(n) time and O(n) space.

Conclusion

The 5 problems today are simpler than the last time. It only took about 50 min to finish them.
Next time, there will be 3 medium problems. Hope it will be more interesting for you to read.

<-- Previous | Home | Next -->

Leetcode Challenge #2

Micc Wan — Sun, 17 Jul 2022 15:33:14 +0000

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

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:

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

Leetcode Challenge #1

Micc Wan — Fri, 15 Jul 2022 11:09:58 +0000

P.S. If you are new here, check my Challenge Introduction before this post!

So let's start the challenge.

The Algorithm Study Plan

I found this study plan in the leetcode home page, it might be a good start for me. For the first part, the plan includes 2~3 problems(most are easy, some medium and no hard) every day. I'll try to finish them each day and maybe 0~2 additional problems to make sure I used the whole hour.

Today's problems

Today's topic: Binary Search

ID	Name	Difficulty	Problem	Solution
704	Binary Search	easy	link	link
278	First Bad Version	easy	link	link
35	Search Insert Position	easy	link	link

I've seen many implementations of binary search. They should all be done in O(log(n)) time and O(1) space.

The one I love the most is to maintain the left and right pointers under certain conditions, since it is intuitive to use. This works for all three problems above.

Another interesting implemention I've seen is to maintain one pointer which will be added either 2^k or 0 in each iteration.
E.g.

function binarySearch(arr, target) {
  let index = 0;
  let step = 1 << 20;
  while (step) {
    const next = index + step;
    if (next < arr.length && arr[next] <= target) {
      index = next;
    }
    step /= 2;
  }
  return index;
}

One could make use of the constrain of the problem to get the initial step size. Or dynamically find it with another loop.

Additional Problem

I picked another medium binary search problem today.

ID	Name	Difficulty	Problem	Solution
33	Search in Rotated Sorted Array	medium	link	link

First I come up with the most basic idea: use binary search to find the pivot, then apply binary search on either the first or the second part depends on whether nums[0] < target. This takes 53 lines and it's not easy to read.

Then I realize I could simply apply binary search on the whole array since realIndex = (originalIndex + pivot) % arr.length.
With this trick, the resulting code is reduced to 40 lines and it's more readable for me! The complexity are still O(log(n)) time and O(1) space.

Conclusion

That's my first post of my practice. Any suggestions would be appreciated! Thanks for your reading.

Home | Next -->

My Leetcode Challenge

Micc Wan — Fri, 15 Jul 2022 05:57:01 +0000

Helloworld from Taiwan! This is Michael. I'm a junior JS fullstack engineer who just graduated from university. I'm going to practice my English writing skill and programming skill before being enlisted in the army(mid October).

Starting today, I will solve some leetcode problems (with JS) about three times a week, one hour at a time, and post the progress here. Any suggestions or corrections are welcome!

The code will be collected in this Github repository:

Forem: Micc Wan

Leetcode Challenge (The end)

Leetcode Challenge #4 (Postponed)

Leetcode Challenge #3

Today's problems

344. Reverse String

577. Reverse Words in a String III

876. Middle of the Linked List

19. Remove Nth Node From End of List

Additional Problem

Conclusion

Leetcode Challenge #2

Today's problems

189. Rotate Array

Additional Problem

Conclusion

Leetcode Challenge #1

The Algorithm Study Plan

Today's problems

Additional Problem

Conclusion

My Leetcode Challenge

MiccWan / leetcode

Posts