Find minimum path sum in a triangle-shaped matrix
Given a right-angled triangle-shaped matrix, find the shortest path sum from the top element to any element in the last row of the matrix.
Category: Dynamic Programming
Count distinct permutations of an array that sums to a target
Given an array of distinct positive integers, find the total number of distinct permutations that add up to a given target, where each array element may be used any number of times.
Longest Alternating Subsequence Problem – II
Given an integer array, find the length of the longest subsequence with alternate low and high elements in the array.
Shrink an array by removing triplets that satisfy given constraints
Given an integer array, shrink it by removing adjacent triplets that satisfy the given constraints and return the total number of elements in the resultant array.
Find height of a binary tree represented by the parent array
Given an array representing the parent-child relationship in a binary tree, find the tree’s height without building it. The parent-child relationship is defined by (A[i], i) for every index i in array A.
Find total arrangements such that no two balls of the same color are together
Given r red, b blue, and g green balls, find the total number of arrangements in a row such that no two balls of the same color end up together.
Truncate an integer array such that `2×min` becomes more than `max`
Given an integer array, truncate it such that 2×min becomes more than max, and the total number of removals is minimal. The elements can be removed either from the start or end of the array if the above condition does not meet.
Maximum Independent Set Problem
An independent set is a set of nodes in a binary tree, no two of which are adjacent. The maximum independent set problem is finding an independent set of the largest possible size for a given binary tree.
Find the minimum number of squares that sum to a given number
Given a positive integer n, find the minimum number of squares that sum to n.
Hat Check Problem – Counting Derangements
Find the total number of ways in which n hats can be returned to n people such that no hat makes it back to its owner.
Count decodings of a given sequence of digits
Given a positive number, map its digits to the corresponding alphabet in the mapping table, and return the count of the total number of decodings possible.
Minimum-weight triangulation of a convex polygon
A triangulation of a convex polygon results in a set of non-intersecting diagonals between non-adjacent vertices, which completely partition the interior of the convex hull of the polygon into triangles.