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:
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. :)
Top comments (4)
please do mention complexity also
Sure, I'll add the complexities on the problems I discussed!
hey it will be really great if you could share every problems approach. notes or something like this.
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...