Problem Implement an algorithm to print all valid (i.e., properly opened and closed) combinations of n-pairs of parentheses. OR Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. Follow up Make sure the returned list of strings are sorted. Examples Example 1: Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"] ...
Problem There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time. Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner. ...
What Catalan numbers form a sequence of natural numbers with applications in various combinatorial mathematics problems. They can be defined in several ways and appear in problems involving balanced parentheses, binary search trees, and more. More on wiki. The (n)-th Catalan number can be given by the formula: $$ C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!} $$ Some common properties of Catalan numbers include: They count the number of expressions containing (n) pairs of correctly matched parentheses. See - Generate Parentheses Problem. They count the number of rooted binary trees with (n + 1) leaves. They count the number of ways to completely parenthesise (n+1) factors in a product. Application of Catalan Number Algorithm The number of ways to stack coins on a base row of (n) consecutive coins in a plane, where no coins can be placed on the two sides of the bottom row and every additional coin must lie above two other coins, is given by the (n)th Catalan number. The number of ways to correctly group a string of (n) pairs of parentheses, ensuring each open parenthesis matches with a closing one, corresponds to the (n)th Catalan number. The number of ways to divide a convex polygon with (n+2) sides into triangles by drawing non-intersecting, straight lines between vertices is determined by the (n)th Catalan number, an application that interested Euler. Solution Method 1 - Recursion Just follow the recursive definition of Catalan numbers: $$ C_n = \sum_{i=0}^{n-1} C_i \cdot C_{n-1-i} $$ ...
Problem You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? OR There are n stairs, a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a time. Count the number of ways, the person can reach the top. ...
Freedom Trail Problem Problem In the video game Fallout 4, the quest “Road to Freedom” requires players to reach a metal dial called the “Freedom Trail Ring” and use the dial to spell a specific keyword to open the door. Given a string ring that represents the code engraved on the outer ring and another string key that represents the keyword that needs to be spelled, return the minimum number of steps to spell all the characters in the keyword. ...
Problem Alice and Bob continue their games with piles of stones. There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i]. The objective of the game is to end with the most stones. Alice and Bob take turns, with Alice starting first. Initially, M = 1. On each player’s turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M. Then, we set M = max(M, X). ...
Problem Given an integer n, return the nth ugly number. Ugly Number Definition Examples Example 1: Input: n = 10 Output: 12 Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers. Example 2: Input: n = 1 Output: 1 Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5. ...
Problem Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. Definition Palindrome Definition Examples Example 1: Input: s = "aab" Output: [ ["a","a","b"],["aa","b"] ] Example 2: Input: s = "a" Output: [ ["a"] ] ...
Problem Given a string s, return the longest palindromic substring in s. Incase of conflict, return the substring which occurs first ( with the least starting index ). Substring of string S: S[i...j] where 0 <= i <= j < len(S) Example Example 1: Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer. ...
Problem Given a set of distinct integers/characters, S, return all possible subsets. OR Given an integer array nums of unique elements, return all possible subsets (the power set). Examples If we’re given a set of integers such that S = {1, 2, 3}, how can we find all the subsets of that set? For example, given S, the set of all subsets i.e. P(S) we get are {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, and {1, 2, 3}. Here is {} is empty set denoted by Φ. ...