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.
Tag: Top-down
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.
Find maximum profit that can be earned by conditionally selling stocks
Given a list containing future price predictions of two different stocks for the next n–days, find the maximum profit earned by selling the stocks with a constraint that the second stock can be sold, only if no transaction happened on the previous day for any of the stock.
Find the minimum number of deletions required to convert a string into a palindrome
Given a string, find the minimum number of deletions required to convert it into a palindrome.
Find minimum jumps required to reach the destination
Given an array of non-negative integers, where each array element represents the maximum number of positions one can move forward from that element. Find the minimum number of jumps required to reach a given destination from a given source within the array.