Skip to content

Enumerate Middle

Table of Contents

2909. Minimum Sum of Mountain Triplets II

1930. Unique Length-3 Palindromic Subsequences

3128. Right Triangles

2874. Maximum Value of an Ordered Triplet II

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

447. Number of Boomerangs

456. 132 Pattern

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, binary search, stack, monotonic stack, ordered set

456. 132 Pattern - Python Solution
from typing import List


# Monotonic Stack
def find132pattern(nums: List[int]) -> bool:
    n = len(nums)
    if n < 3:
        return False

    stack = []
    second_max = float("-inf")

    for i in range(n - 1, -1, -1):
        if nums[i] < second_max:
            return True

        while stack and stack[-1] < nums[i]:
            second_max = stack.pop()

        stack.append(nums[i])

    return False


nums = [-1, 3, 2, 0]
print(find132pattern(nums))  # True

3067. Count Pairs of Connectable Servers in a Weighted Tree Network

3455. Shortest Matching Substring

2242. Maximum Score of a Node Sequence

2867. Count Valid Paths in a Tree

  • LeetCode | LeetCode CH (Hard)

  • Tags: math, dynamic programming, tree, depth first search, number theory

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

3257. Maximum Value Sum by Placing Three Rooks II

3073. Maximum Increasing Triplet Value

Comments