My observation: If we fill a List of intervals with [first appearance, last appearance] for each char. Then the question suddenly turns into the 'merge intervals'
Q: Can worst-case time complexity be reduced in any way ? Yes, the worst-case time complexity can be significantly reduced from O(n^2) to O(n). Here's how we can optimize the algorithm: 1. Use an array to store the last occurrence of each character. 2. Make a single pass through the string to find partitions. Here's an optimized version of the code: ```java class PartitionLabels { public List partitionLabels(String s) { List partitions = new ArrayList(); if (s == null || s.length() == 0) return partitions; // Step 1: Create an array to store the last index of each character int[] lastIndex = new int[26]; for (int i = 0; i < s.length(); i++) { lastIndex[s.charAt(i) - 'a'] = i; } // Step 2: Find partitions in a single pass int start = 0, end = 0; for (int i = 0; i < s.length(); i++) { end = Math.max(end, lastIndex[s.charAt(i) - 'a']); if (i == end) { partitions.add(end - start + 1); start = i + 1; } } return partitions; } } ``` Time Complexity Analysis: 1. The first loop to fill the lastIndex array is O(n). 2. The second loop to find partitions is also O(n). 3. All operations inside the loops are O(1). Therefore, the overall time complexity is O(n), where n is the length of the input string. Space Complexity: 1. We use an additional array of size 26 (constant space). 2. The output list in the worst case could be of size n/2 if every other character forms a partition. The space complexity remains O(n). This optimized version eliminates the nested loops and repeated calls to lastIndexOf, significantly improving the time complexity while maintaining the same space complexity. It's much more efficient, especially for larger inputs.
its like fresh breath after neetcode videos) thank you
plus one!!!
your new look is as nice as your videos man. Really awesome. your sorting algo videos really help me in my technical interview.
we can also iterate from start, all occurrences will be updated in the map, so we will get last indexes of all chars.
You Explained very well, thank you, and make more videos like this.
fantastic explanation 👍
great explanation! Thank you.
what is this pen and notebook that you write into ? I like your teaching style , Can you please share about how you make it so easy to highlight
My observation: If we fill a List of intervals with [first appearance, last appearance] for each char. Then the question suddenly turns into the 'merge intervals'
Thank you
idk why this channel has so less subcribers
i wonder the same too 😅, please share as much as possible.
why did u not put any iteration expression like I++ in the for loop?
That gets confusing when you review your code
The time complexity isn’t O(n^2)?
Observe carefully, we iterate through the string only once.
Q: Can worst-case time complexity be reduced in any way ?
Yes, the worst-case time complexity can be significantly reduced from O(n^2) to O(n). Here's how we can optimize the algorithm:
1. Use an array to store the last occurrence of each character.
2. Make a single pass through the string to find partitions.
Here's an optimized version of the code:
```java
class PartitionLabels {
public List partitionLabels(String s) {
List partitions = new ArrayList();
if (s == null || s.length() == 0) return partitions;
// Step 1: Create an array to store the last index of each character
int[] lastIndex = new int[26];
for (int i = 0; i < s.length(); i++) {
lastIndex[s.charAt(i) - 'a'] = i;
}
// Step 2: Find partitions in a single pass
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
end = Math.max(end, lastIndex[s.charAt(i) - 'a']);
if (i == end) {
partitions.add(end - start + 1);
start = i + 1;
}
}
return partitions;
}
}
```
Time Complexity Analysis:
1. The first loop to fill the lastIndex array is O(n).
2. The second loop to find partitions is also O(n).
3. All operations inside the loops are O(1).
Therefore, the overall time complexity is O(n), where n is the length of the input string.
Space Complexity:
1. We use an additional array of size 26 (constant space).
2. The output list in the worst case could be of size n/2 if every other character forms a partition.
The space complexity remains O(n).
This optimized version eliminates the nested loops and repeated calls to lastIndexOf, significantly improving the time complexity while maintaining the same space complexity. It's much more efficient, especially for larger inputs.