192 lines
6.9 KiB
Markdown
192 lines
6.9 KiB
Markdown
|
- Leetcode Insert Interval
|
||
|
|
id:: 642cd1a8-9707-4dc2-9d03-11464553e618
|
||
|
|
|
||
|
|
- Times:
|
||
|
|
- Time when completed: 10:05
|
||
|
|
- Time taken to complete: 20min (I looked up solution from chatGPT)
|
||
|
|
- Revisions:
|
||
|
|
- Tags:
|
||
|
|
- Algorithms: #greedy
|
||
|
|
- Data structures: #array #interval
|
||
|
|
- Difficulty: #difficulty_medium
|
||
|
|
- Platforms: #leetcode
|
||
|
|
- Links:
|
||
|
|
- [link to the problem](https://leetcode.com/problems/insert-interval/description/)
|
||
|
|
- Problem:
|
||
|
|
- You are given an array of non-overlapping intervals `intervals` where `intervals[i] = [starti, endi]` represent the start and the end of the `ith` interval and `intervals` is sorted in ascending order by `starti`. You are also given an interval `newInterval = [start, end]` that represents the start and end of another interval.
|
||
|
|
- Insert `newInterval` into `intervals` such that `intervals` is still sorted in ascending order by `starti` and `intervals` still does not have any overlapping intervals (merge overlapping intervals if necessary).
|
||
|
|
- Return `intervals`_ after the insertion_.
|
||
|
|
- Examples:
|
||
|
|
|
||
|
|
- ```
|
||
|
|
Example 1:
|
||
|
|
|
||
|
|
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
|
||
|
|
Output: [[1,5],[6,9]]
|
||
|
|
|
||
|
|
Example 2:
|
||
|
|
|
||
|
|
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
|
||
|
|
Output: [[1,2],[3,10],[12,16]]
|
||
|
|
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
|
||
|
|
|
||
|
|
```
|
||
|
|
|
||
|
|
- Constraints:
|
||
|
|
- `0 <= intervals.length <= 104`
|
||
|
|
- `intervals[i].length == 2`
|
||
|
|
- `0 <= starti <= endi <= 105`
|
||
|
|
- `intervals` is sorted by `starti` in **ascending** order.
|
||
|
|
- `newInterval.length == 2`
|
||
|
|
- `0 <= start <= end <= 105`
|
||
|
|
- Thoughts:
|
||
|
|
- AI's solution:
|
||
|
|
collapsed:: true
|
||
|
|
- ```java
|
||
|
|
class Solution {
|
||
|
|
public int[][] insert(int[][] intervals, int[] newInterval) {
|
||
|
|
List<int[]> result = new ArrayList<>();
|
||
|
|
int i = 0;
|
||
|
|
// add intervals that end before newInterval starts
|
||
|
|
while (i < intervals.length && intervals[i][1] < newInterval[0]) {
|
||
|
|
result.add(intervals[i]);
|
||
|
|
i++;
|
||
|
|
}
|
||
|
|
// merge overlapping intervals with newInterval
|
||
|
|
while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
|
||
|
|
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
|
||
|
|
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
|
||
|
|
i++;
|
||
|
|
}
|
||
|
|
result.add(newInterval);
|
||
|
|
// add remaining intervals
|
||
|
|
while (i < intervals.length) {
|
||
|
|
result.add(intervals[i]);
|
||
|
|
i++;
|
||
|
|
}
|
||
|
|
return result.toArray(new int[result.size()][2]);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
```
|
||
|
|
- The solution uses a greedy approach to merge the given intervals with the new interval. We first add all the intervals that end before the new interval starts, as they cannot overlap with the new interval. Then we merge any overlapping intervals with the new interval by updating its start and end values. Finally, we add any remaining intervals that start after the new interval ends.
|
||
|
|
- The time complexity of this solution is O(n), where n is the number of intervals in the input array. This is because we iterate over the intervals array only once. The space complexity is also O(n), as we may need to store all the intervals in the result array.
|
||
|
|
- Intuition:
|
||
|
|
- We use greedy algorithm here, since we are going to find the optimal
|
||
|
|
solution at each step. The code itself is simple to read and understand,
|
||
|
|
the difficulty for me to write the code is to check when intervals
|
||
|
|
overlap and how to merge them.
|
||
|
|
- Approach:
|
||
|
|
- The code has four steps:
|
||
|
|
- Construct an answer arrayList, and add every interval before `newInterval` to the answer
|
||
|
|
- Use a while loop, to merge overlapping intervals into `newIntreval`, and later we skip these already merged interval
|
||
|
|
- Add the `newInterval` to the answer array
|
||
|
|
- Add remaining intervals to the answer
|
||
|
|
- Solution:
|
||
|
|
|
||
|
|
- The code is $$O(n)$$ time $$O(n)$$ space
|
||
|
|
|
||
|
|
```java
|
||
|
|
class Solution {
|
||
|
|
public int[][] insert(int[][] intervals, int[] newInterval) {
|
||
|
|
// Simulation doesn't work lol
|
||
|
|
// We just merge the intervals
|
||
|
|
ArrayList<int[]> ans = new ArrayList();
|
||
|
|
|
||
|
|
// add the intervals before newInterval
|
||
|
|
int i = 0;
|
||
|
|
while (i < intervals.length && newInterval[0] > intervals[i][1]) {
|
||
|
|
ans.add(intervals[i]);
|
||
|
|
i++;
|
||
|
|
}
|
||
|
|
|
||
|
|
// merge all overlapping interval into newInterval
|
||
|
|
while (i < intervals.length && newInterval[1] >= intervals[i][0]) {
|
||
|
|
newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
|
||
|
|
newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
|
||
|
|
i++;
|
||
|
|
}
|
||
|
|
ans.add(newInterval);
|
||
|
|
|
||
|
|
// add the remaining to answer
|
||
|
|
while (i < intervals.length) {
|
||
|
|
ans.add(intervals[i++]);
|
||
|
|
}
|
||
|
|
|
||
|
|
return ans.toArray(new int[ans.size()][2]);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
```
|
||
|
|
|
||
|
|
-
|
||
|
|
- Leetcode - Length of Last Word
|
||
|
|
|
||
|
|
- Times:
|
||
|
|
- Time when completed: 10:49
|
||
|
|
- Time taken to complete: about 5 mins
|
||
|
|
- Revisions:
|
||
|
|
- Tags:
|
||
|
|
- Data structures: #array
|
||
|
|
- Difficulty: #difficulty_easy
|
||
|
|
- Platforms: #leetcode
|
||
|
|
- Links:
|
||
|
|
- [link to the problem](https://leetcode.com/problems/length-of-last-word/description/)
|
||
|
|
- Problem:
|
||
|
|
- Given a string `s` consisting of words and spaces, return _the length of the **last** word in the string._
|
||
|
|
- A **word** is a maximal substring consisting of non-space characters only.
|
||
|
|
- Examples:
|
||
|
|
|
||
|
|
- ```
|
||
|
|
Example 1:
|
||
|
|
|
||
|
|
Input: s = "Hello World"
|
||
|
|
Output: 5
|
||
|
|
Explanation: The last word is "World" with length 5.
|
||
|
|
|
||
|
|
Example 2:
|
||
|
|
|
||
|
|
Input: s = " fly me to the moon "
|
||
|
|
Output: 4
|
||
|
|
Explanation: The last word is "moon" with length 4.
|
||
|
|
|
||
|
|
Example 3:
|
||
|
|
|
||
|
|
Input: s = "luffy is still joyboy"
|
||
|
|
Output: 6
|
||
|
|
Explanation: The last word is "joyboy" with length 6.
|
||
|
|
|
||
|
|
```
|
||
|
|
|
||
|
|
- Constraints:
|
||
|
|
- `1 <= s.length <= 104`
|
||
|
|
- `s` consists of only English letters and spaces `' '`.
|
||
|
|
- There will be at least one word in `s`.
|
||
|
|
- Thoughts:
|
||
|
|
- Intuition:
|
||
|
|
- The most important part is to count from end, this avoids traversing the entire array and helps with speed. $$O(n)$$ time and space.
|
||
|
|
- Approach:
|
||
|
|
- First, skip any spaces
|
||
|
|
- Then start counting until a space is encountered
|
||
|
|
- Solution:
|
||
|
|
|
||
|
|
- Code
|
||
|
|
|
||
|
|
```java
|
||
|
|
class Solution {
|
||
|
|
public int lengthOfLastWord(String s) {
|
||
|
|
int len = 0;
|
||
|
|
int i = s.length() - 1;
|
||
|
|
|
||
|
|
while (i >= 0 && s.charAt(i) == ' ') {
|
||
|
|
i--;
|
||
|
|
}
|
||
|
|
|
||
|
|
while (i >= 0 && s.charAt(i) != ' ') {
|
||
|
|
i--;
|
||
|
|
len++;
|
||
|
|
}
|
||
|
|
|
||
|
|
return len;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
```
|