DP Prefix and Suffix Decomposition¶

Table of Contents¶

724. Find Pivot Index¶

LeetCode | LeetCode CH (Easy)
Tags: array, prefix sum

1991. Find the Middle Index in Array¶

LeetCode | LeetCode CH (Easy)
Tags: array, prefix sum

2270. Number of Ways to Split Array¶

LeetCode | LeetCode CH (Medium)
Tags: array, prefix sum

2256. Minimum Average Difference¶

LeetCode | LeetCode CH (Medium)
Tags: array, prefix sum

1422. Maximum Score After Splitting a String¶

LeetCode | LeetCode CH (Easy)
Tags: string, prefix sum

1493. Longest Subarray of 1's After Deleting One Element¶

LeetCode | LeetCode CH (Medium)
Tags: array, dynamic programming, sliding window

1493. Longest Subarray of 1's After Deleting One Element - Python Solution

from typing import List


# Sliding Window Variable Size
def longestSubarray(nums: List[int]) -> int:
    zeroCount = 0
    res = 0
    left = 0

    for right in range(len(nums)):
        if nums[right] == 0:
            zeroCount += 1

        while zeroCount > 1:
            if nums[left] == 0:
                zeroCount -= 1
            left += 1

        res = max(res, right - left)

    return res


nums = [1, 1, 0, 1]
print(longestSubarray(nums))  # 3

845. Longest Mountain in Array¶

LeetCode | LeetCode CH (Medium)
Tags: array, two pointers, dynamic programming, enumeration

845. Longest Mountain in Array - Python Solution

from typing import List


# Left Right Pointers
def longestMountain(arr: List[int]) -> int:
    n = len(arr)
    res = 0
    left = 0

    while left < n:
        right = left

        if right < n - 1 and arr[right] < arr[right + 1]:
            while right < n - 1 and arr[right] < arr[right + 1]:
                right += 1

            if right < n - 1 and arr[right] > arr[right + 1]:
                while right < n - 1 and arr[right] > arr[right + 1]:
                    right += 1
                res = max(res, right - left + 1)

        left = max(right, left + 1)

    return res


arr = [2, 1, 4, 7, 3, 2, 5]
print(longestMountain(arr))  # 5

2012. Sum of Beauty in the Array¶

LeetCode | LeetCode CH (Medium)
Tags: array

2012. Sum of Beauty in the Array - Python Solution

from typing import List


# DP Prefix and Suffix Decomposition
def sumOfBeauties(nums: List[int]) -> int:
    n = len(nums)
    suf_min = [0] * n
    suf_min[n - 1] = nums[n - 1]
    for i in range(n - 2, 1, -1):
        suf_min[i] = min(suf_min[i + 1], nums[i])

    res = 0
    pre_max = nums[0]
    for i in range(1, n - 1):
        x = nums[i]
        if pre_max < x < suf_min[i + 1]:
            res += 2
        elif nums[i - 1] < x < nums[i + 1]:
            res += 1
        pre_max = max(pre_max, x)

    return res


nums = [2, 4, 6, 4, 5]
print(sumOfBeauties(nums))  # 1

2909. Minimum Sum of Mountain Triplets II¶

LeetCode | LeetCode CH (Medium)
Tags: array

2483. Minimum Penalty for a Shop¶

LeetCode | LeetCode CH (Medium)
Tags: string, prefix sum

1525. Number of Good Ways to Split a String¶

LeetCode | LeetCode CH (Medium)
Tags: hash table, string, dynamic programming, bit manipulation

3354. Make Array Elements Equal to Zero¶

LeetCode | LeetCode CH (Easy)
Tags: array, simulation, prefix sum

2874. Maximum Value of an Ordered Triplet II¶

LeetCode | LeetCode CH (Medium)
Tags: array

2874. Maximum Value of an Ordered Triplet II - Python Solution

from typing import List


def maximumTripletValue(nums: List[int]) -> int:
    res = 0
    max_diff = 0
    max_prev = 0

    for num in nums:
        res = max(res, max_diff * num)
        max_diff = max(max_diff, max_prev - num)
        max_prev = max(max_prev, num)

    return res


if __name__ == "__main__":
    nums = [12, 6, 1, 2, 7]
    print(maximumTripletValue(nums))  # 77

123. Best Time to Buy and Sell Stock III¶

LeetCode | LeetCode CH (Hard)
Tags: array, dynamic programming

123. Best Time to Buy and Sell Stock III - Python Solution

from typing import List


# 1. DP
def maxProfitDP1(prices: List[int]) -> int:
    n = len(prices)
    if n <= 1:
        return 0

    dp = [[0] * 5 for _ in range(n)]

    dp[0][0] = 0  # no transaction
    dp[0][1] = -prices[0]  # buy 1
    dp[0][2] = 0  # sell 1
    dp[0][3] = -prices[0]  # buy 2
    dp[0][4] = 0  # sell 2

    for i in range(1, n):
        dp[i][0] = dp[i - 1][0]
        dp[i][1] = max(dp[i - 1][1], -prices[i])
        dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i])
        dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i])
        dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i])

    return dp[-1][4]


# 2. DP - Optimized
def maxProfitDP2(prices: List[int]) -> int:
    b1, b2 = float("inf"), float("inf")
    s1, s2 = 0, 0

    for price in prices:
        b1 = min(b1, price)
        s1 = max(s1, price - b1)
        b2 = min(b2, price - s1)
        s2 = max(s2, price - b2)

    return s2


prices = [3, 3, 5, 0, 0, 3, 1, 4]
print(maxProfitDP1(prices))  # 6
print(maxProfitDP2(prices))  # 6

2222. Number of Ways to Select Buildings¶

LeetCode | LeetCode CH (Medium)
Tags: string, dynamic programming, prefix sum

1031. Maximum Sum of Two Non-Overlapping Subarrays¶

LeetCode | LeetCode CH (Medium)
Tags: array, dynamic programming, sliding window

689. Maximum Sum of 3 Non-Overlapping Subarrays¶

LeetCode | LeetCode CH (Hard)
Tags: array, dynamic programming

2420. Find All Good Indices¶

LeetCode | LeetCode CH (Medium)
Tags: array, dynamic programming, prefix sum

2100. Find Good Days to Rob the Bank¶

LeetCode | LeetCode CH (Medium)
Tags: array, dynamic programming, prefix sum

926. Flip String to Monotone Increasing¶

LeetCode | LeetCode CH (Medium)
Tags: string, dynamic programming

334. Increasing Triplet Subsequence¶

LeetCode | LeetCode CH (Medium)
Tags: array, greedy

2712. Minimum Cost to Make All Characters Equal¶

LeetCode | LeetCode CH (Medium)
Tags: string, dynamic programming, greedy

2712. Minimum Cost to Make All Characters Equal - Python Solution

def minimumCost(s: str) -> int:
    n = len(s)
    res = 0
    for i in range(1, n):
        if s[i - 1] != s[i]:
            res += min(i, n - i)

    return res


if __name__ == "__main__":
    s = "0011"
    print(minimumCost(s))  # 2

1653. Minimum Deletions to Make String Balanced¶

LeetCode | LeetCode CH (Medium)
Tags: string, dynamic programming, stack

1186. Maximum Subarray Sum with One Deletion¶

LeetCode | LeetCode CH (Medium)
Tags: array, dynamic programming

1186. Maximum Subarray Sum with One Deletion - Python Solution

from typing import List


# DP - Kadane
def maximumSum(arr: List[int]) -> int:
    dp0 = arr[0]
    dp1 = 0
    maxSum = dp0

    for i in range(1, len(arr)):
        dp1 = max(dp1 + arr[i], dp0)  # delete previous element or not
        dp0 = max(dp0, 0) + arr[i]  # delete current element or not
        maxSum = max(maxSum, dp0, dp1)  # update result

    return maxSum


arr = [1, -2, 0, 3]
print(maximumSum(arr))  # 4

42. Trapping Rain Water¶

LeetCode | LeetCode CH (Hard)
Tags: array, two pointers, dynamic programming, stack, monotonic stack

Approach	Time	Space
DP	O(N)	O(N)
Left Right	O(N)	O(1)
Monotonic	O(N)	O(N)

42. Trapping Rain Water - Python Solution

from typing import List


# DP
def trapDP(height: List[int]) -> int:
    if not height:
        return 0

    n = len(height)
    maxLeft, maxRight = [0 for _ in range(n)], [0 for _ in range(n)]

    for i in range(1, n):
        maxLeft[i] = max(maxLeft[i - 1], height[i - 1])

    for i in range(n - 2, -1, -1):
        maxRight[i] = max(maxRight[i + 1], height[i + 1])

    res = 0
    for i in range(n):
        res += max(0, min(maxLeft[i], maxRight[i]) - height[i])

    return res


# Left Right Pointers
def trapLR(height: List[int]) -> int:
    if not height:
        return 0

    left, right = 0, len(height) - 1
    maxL, maxR = height[left], height[right]
    res = 0

    while left < right:
        if maxL < maxR:
            left += 1
            maxL = max(maxL, height[left])
            res += maxL - height[left]
        else:
            right -= 1
            maxR = max(maxR, height[right])
            res += maxR - height[right]

    return res


# Monotonic Stack
def trapStack(height: List[int]) -> int:
    stack = []
    total = 0

    for i in range(len(height)):
        while stack and height[i] > height[stack[-1]]:
            top = stack.pop()
            if not stack:
                break
            distance = i - stack[-1] - 1
            bounded_height = min(height[i], height[stack[-1]]) - height[top]
            total += distance * bounded_height
        stack.append(i)

    return total


height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
print(trapDP(height))  # 6
print(trapLR(height))  # 6
print(trapStack(height))  # 6

42. Trapping Rain Water - C++ Solution

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

class Solution
{
public:
    int trap(vector<int> &height)
    {
        if (height.empty())
            return 0;

        int res = 0;
        int left = 0, right = height.size() - 1;
        int maxL = height[left], maxR = height[right];

        while (left < right)
        {
            if (maxL < maxR)
            {
                left++;
                maxL = max(maxL, height[left]);
                res += maxL - height[left];
            }
            else
            {
                right--;
                maxR = max(maxR, height[right]);
                res += maxR - height[right];
            }
        }
        return res;
    }
};

int main()
{
    vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    Solution solution;
    cout << solution.trap(height) << endl;
    return 0;
}

2711. Difference of Number of Distinct Values on Diagonals¶

LeetCode | LeetCode CH (Medium)
Tags: array, hash table, matrix

2711. Difference of Number of Distinct Values on Diagonals - Python Solution

from typing import List


def differenceOfDistinctValues(grid: List[List[int]]) -> List[List[int]]:
    m, n = len(grid), len(grid[0])
    res = [[0] * n for _ in range(m)]
    st = set()

    for k in range(1, m + n):
        min_j = max(n - k, 0)
        max_j = min(m + n - 1 - k, n - 1)

        st.clear()
        for j in range(min_j, max_j + 1):
            i = k + j - n
            res[i][j] = len(st)
            st.add(grid[i][j])

        st.clear()
        for j in range(max_j, min_j - 1, -1):
            i = k + j - n
            res[i][j] = abs(res[i][j] - len(st))
            st.add(grid[i][j])

    return res


if __name__ == "__main__":
    grid = [[1, 2, 3], [3, 1, 5], [3, 2, 1]]
    print(differenceOfDistinctValues(grid))
    # [[1, 1, 0], [1, 0, 1], [0, 1, 1]]

1477. Find Two Non-overlapping Sub-arrays Each With Target Sum¶

LeetCode | LeetCode CH (Medium)
Tags: array, hash table, binary search, dynamic programming, sliding window

2680. Maximum OR¶

LeetCode | LeetCode CH (Medium)
Tags: array, greedy, bit manipulation, prefix sum

2680. Maximum OR - Python Solution

from typing import List


# Greedy
def maximumOr(nums: List[int], k: int) -> int:
    """Maximum OR of Array After k Operations

    Args:
        nums (List[int]): provided list of integers
        k (int): number of operations

    Returns:
        int: maximum OR of array after k operations
    """
    n = len(nums)
    suffix = [0 for _ in range(n)]

    for i in range(n - 2, -1, -1):
        suffix[i] = suffix[i + 1] | nums[i + 1]

    res, pre = 0, 0
    for num, suf in zip(nums, suffix):
        res = max(res, pre | (num << k) | suf)
        pre |= num

    return res


if __name__ == "__main__":
    print(maximumOr(nums=[8, 1, 2], k=2))  # 35

1671. Minimum Number of Removals to Make Mountain Array¶

LeetCode | LeetCode CH (Hard)
Tags: array, binary search, dynamic programming, greedy

1671. Minimum Number of Removals to Make Mountain Array - Python Solution

from typing import List


# DP - LIS
def minimumMountainRemovals(nums: List[int]) -> int:
    n = len(nums)
    lis = [1 for _ in range(n)]
    lds = [1 for _ in range(n)]

    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                lis[i] = max(lis[i], lis[j] + 1)

    for i in range(n - 2, -1, -1):
        for j in range(n - 1, i, -1):
            if nums[i] > nums[j]:
                lds[i] = max(lds[i], lds[j] + 1)

    maxLen = 0
    for i in range(1, n - 1):
        if lis[i] > 1 and lds[i] > 1:
            maxLen = max(maxLen, lis[i] + lds[i] - 1)

    return n - maxLen


nums = [2, 1, 1, 5, 6, 2, 3, 1]
print(minimumMountainRemovals(nums))  # 3

1888. Minimum Number of Flips to Make the Binary String Alternating¶

LeetCode | LeetCode CH (Medium)
Tags: string, dynamic programming, greedy, sliding window

238. Product of Array Except Self¶

LeetCode | LeetCode CH (Medium)
Tags: array, prefix sum
Classic Prefix Sum problem
Return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Approach	Time	Space
Prefix	O(n)	O(n)
Prefix (Optimized)	O(n)	O(1)

238. Product of Array Except Self - Python Solution

from typing import List


# Prefix
def productExceptSelf(nums: List[int]) -> List[int]:
    n = len(nums)
    prefix = [1 for _ in range(n)]
    suffix = [1 for _ in range(n)]

    for i in range(1, n):
        prefix[i] = nums[i - 1] * prefix[i - 1]

    for i in range(n - 2, -1, -1):
        suffix[i] = nums[i + 1] * suffix[i + 1]

    result = [i * j for i, j in zip(prefix, suffix)]

    return result


# Prefix (Optimized)
def productExceptSelfOptimized(nums: List[int]) -> List[int]:
    n = len(nums)
    result = [1 for _ in range(n)]

    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]

    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]

    return result


print(productExceptSelf([1, 2, 3, 4]))
# [24, 12, 8, 6]
print(productExceptSelfOptimized([1, 2, 3, 4]))
# [24, 12, 8, 6]

238. Product of Array Except Self - C++ Solution

#include <vector>
#include <iostream>
using namespace std;

// Prefix Sum
class Solution
{
public:
    vector<int> productExceptSelf(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> prefix(n, 1);
        vector<int> suffix(n, 1);
        vector<int> res(n, 1);

        for (int i = 1; i < n; i++)
        {
            prefix[i] = prefix[i - 1] * nums[i - 1];
        }

        for (int i = n - 2; i >= 0; i--)
        {
            suffix[i] = suffix[i + 1] * nums[i + 1];
        }

        for (int i = 0; i < n; i++)
        {
            res[i] = prefix[i] * suffix[i];
        }
        return res;
    }
};

int main()
{
    vector<int> nums = {1, 2, 3, 4};
    Solution obj;
    vector<int> result = obj.productExceptSelf(nums);

    for (int i = 0; i < result.size(); i++)
    {
        cout << result[i] << "\n";
    }
    cout << endl;
    // 24, 12, 8, 6
    return 0;
}

2906. Construct Product Matrix¶

LeetCode | LeetCode CH (Medium)
Tags: array, matrix, prefix sum

3334. Find the Maximum Factor Score of Array¶

LeetCode | LeetCode CH (Medium)
Tags: array, math, number theory

2167. Minimum Time to Remove All Cars Containing Illegal Goods¶

LeetCode | LeetCode CH (Hard)
Tags: string, dynamic programming

2484. Count Palindromic Subsequences¶

LeetCode | LeetCode CH (Hard)
Tags: string, dynamic programming

2163. Minimum Difference in Sums After Removal of Elements¶

LeetCode | LeetCode CH (Hard)
Tags: array, dynamic programming, heap priority queue

2565. Subsequence With the Minimum Score¶

LeetCode | LeetCode CH (Hard)
Tags: two pointers, string, binary search

1995. Count Special Quadruplets¶

LeetCode | LeetCode CH (Easy)
Tags: array, hash table, enumeration

2552. Count Increasing Quadruplets¶

LeetCode | LeetCode CH (Hard)
Tags: array, dynamic programming, binary indexed tree, enumeration, prefix sum

2552. Count Increasing Quadruplets - Python Solution

from typing import List


# DP
def countQuadruplets(nums: List[int]) -> int:
    n = len(nums)
    great = [[0] * (n + 1) for _ in range(n)]
    less = [0 for _ in range(n + 1)]

    for k in range(n - 2, 1, -1):
        great[k] = great[k + 1].copy()
        for x in range(1, nums[k + 1]):
            great[k][x] += 1

    ans = 0

    for j in range(1, n - 1):
        for x in range(nums[j - 1] + 1, n + 1):
            less[x] += 1
        for k in range(j + 1, n - 1):
            if nums[j] > nums[k]:
                ans += less[nums[k]] * great[k][nums[j]]
    return ans


nums = [1, 3, 2, 4, 5]
print(countQuadruplets(nums))  # 2

3302. Find the Lexicographically Smallest Valid Sequence¶

LeetCode | LeetCode CH (Medium)
Tags: two pointers, string, dynamic programming, greedy

3404. Count Special Subsequences¶

LeetCode | LeetCode CH (Medium)
Tags: array, hash table, math, enumeration

3303. Find the Occurrence of First Almost Equal Substring¶

LeetCode | LeetCode CH (Hard)
Tags: string, string matching

3287. Find the Maximum Sequence Value of Array¶

LeetCode | LeetCode CH (Hard)
Tags: array, dynamic programming, bit manipulation

3257. Maximum Value Sum by Placing Three Rooks II¶

LeetCode | LeetCode CH (Hard)
Tags: array, dynamic programming, matrix, enumeration

3410. Maximize Subarray Sum After Removing All Occurrences of One Element¶

LeetCode | LeetCode CH (Hard)
Tags: array, dynamic programming, segment tree

3003. Maximize the Number of Partitions After Operations¶

LeetCode | LeetCode CH (Hard)
Tags: string, dynamic programming, bit manipulation, bitmask

487. Max Consecutive Ones II¶

LeetCode | LeetCode CH (Medium)
Tags: array, dynamic programming, sliding window

1746. Maximum Subarray Sum After One Operation¶

LeetCode | LeetCode CH (Medium)
Tags: array, dynamic programming