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
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.
Top comments (0)