Prefix Sum

The performance of an algorithm is mostly measured by its time and space complexity. Some algorithms optimize a process by using more space, resulting in an overall improvement in time.

Case in point: Leetcode 2559 (open the Leetcode link to follow along)

A brute force solution to this is to

The pseudocode is in the docstring.

The time complexity for this approach is O(m?n) in the worst case, where m is the number of queries, and n is the length of the words list.

The space complexity is O(m), where m is the space occupied by the ans variable.

This solution would result in a "time limit exceeded" error on Leetcode, hence the need for a more time-efficient solution.

A more time-efficient solution involves implementing a prefix sum. There are repeated sub-problems that can be represented using a prefix sum. The prefix sum array stores the sum of words that start and end with a vowel. To find the sum of words that start and end with a vowel between indices 2 to 4, you simply subtract the prefix sums at the range boundaries.

A Python code implementation is below:

The time complexity in the worst case is O(m+n), where m is the number of queries, and n is the length of the words list.

The space complexity is O(m+n), where mmm is for the ans variable and n is for the extra array used by the prefix sum.

The prefix sum approach saves time but uses more space in this case.

1. Maximum score after splitting a string
2. Number of ways to split array
3. Unique length-3 palindromic sequence

#leetcode #algorithms #DSA