Try it on GfG Practice In the stock market, a person buys a stock and sells it on some future date. Given the stock prices of n days in an array prices[ ]. Find out the maximum profit a person can make in at most 2 transactions. A transaction is equivalent to (buying + selling) of a stock and a new…

Try it on GfG Practice Given a string s, the task is to find the longest repeating non-overlapping substring in it. In other words, find 2 identical substrings of maximum length which do not overlap. Return -1 if no such string exists. Note: Multiple Answers are possible but we have to return the…

Given a tree with n nodes and n-1 edges, the task is to find the maximum height of the tree when any node in the tree is considered as the root of the tree. Example: Input: Output: 5 Explanation: The below diagram represents a tree with 11 nodes and 10 edges and the path that gives us the maximum…

Try it on GfG Practice Given the dimension of a sequence of matrices in an array arr[], where the dimension of the ith matrix is (arr[i-1] * arr[i]), the task is to find the most efficient way to multiply these matrices together such that the total number of element multiplications is minimum. When…

Try it on GfG Practice Given a 2D array, the task is to find the maximum sum sub-matrix in it. Example: Input: mat=[[1,2,-1,-4,-20],[-8,-3,4,2,1],[3,8,10,1,3],[-4,-1,1,7,-6]] Output: 29 Explanation: The matrix is as follows and the green rectangle denotes the maximum sum rectangle which is equal to…

Given an array of strings arr[] and an array cost[] representing the cost to reverse each corresponding string. We are not allowed to move or reorder the strings in the array, we can only reverse individual strings if needed. The task is to choose which strings to reverse such that the final array…

Try it on GfG Practice Given an array arr[] which represents the chain of matrices such that the dimensions of the ith matrix are arr[i-1] x arr[i]. The task is to find the correct parenthesis of the matrices such that when we multiply all the matrices together, the cost or total number of element…

Given an array times[] of positive distinct integers denoting the crossing time of n people. These people are standing on one side of the bridge. There is only one torch with them and the bridge cannot be crossed without the torch. The bridge can hold at max two people at a time. When two people…

Try it on GfG Practice You are given n identical eggs and you have access to a k-floored building from 1 to k. There exists a floor f where 0 <= f <= k such that any egg dropped from a floor higher than f will break, and any egg dropped from or below floor f will not break. There are a few rules…

Try it on GfG Practice Given a matrix mat[][] of size n x n where every element is either 'O' or 'X', the task is to find the size of the largest square subgrid that is completely surrounded by 'X', i.e. the largest square where all its border cells are 'X'. Examples: Input: mat[][] = [ ['X', 'X'],…

Try it on GfG Practice Rahul and Ankit are the only two waiters in the Royal Restaurant. Today, the restaurant received N orders. The amount of tips may differ when handled by different waiters and given as arrays A[] and B[] such that if Rahul takes the ith Order, he would be tipped A[i] rupees,…

Try it on GfG Practice Given a binary matrix mat of size n * m, the task is to find out the maximum length of a side of a square sub-matrix with all 1s. Example: Input: mat = [ [0, 1, 1, 0, 1], [1, 1, 0, 1, 0], [0, 1, 1, 1, 0], [1, 1, 1, 1, 0], [1, 1, 1, 1, 1], [0, 0, 0, 0, 0] ] Output: 3…

Try it on GfG Practice Given a string s, the task is to find the minimum number of characters to be inserted to convert it to a palindrome. Examples: Input: s = "geeks" Output: 3 Explanation: "skgeegks" is a palindromic string, which requires 3 insertions. Input: s= "abcd" Output: 3 Explanation:…

Try it on GfG Practice Given an array arr[] of size n, the task is to find the longest subsequence such that the absolute difference between adjacent elements is 1. Examples: Input: arr[] = [10, 9, 4, 5, 4, 8, 6] Output: 3 Explanation: The three possible subsequences of length 3 are [10, 9, 8], [4,…

Try it on GfG Practice There are 'p' balls of type P, 'q' balls of type Q and 'r' balls of type R. Using the balls we want to create a straight line such that no two balls of the same type are adjacent. Examples : Input: p = 1, q = 1, r = 0 Output: 2 Explanation: There are only two arrangements PQ…

Try it on GfG Practice Given a string s, find the length of the Longest Palindromic Subsequence in it. Note: The Longest Palindromic Subsequence (LPS) is the maximum-length subsequence of a given string that is also a Palindrome. Longest Palindromic Subsequence Examples: Input: s = "bbabcbcab"…

Try it on GfG Practice Given an array arr[], the task is to check if it can be partitioned into two parts such that the sum of elements in both parts is the same. Note: Each element is present in either the first subset or the second subset, but not in both. Examples: Input: arr[] = [1, 5, 11, 5]…

Try it on GfG Practice A Derangement is a permutation of n elements, such that no element appears in its original position. For example, a derangement of [0, 1, 2, 3] is [2, 3, 1, 0]. Given a number n, find the total number of Derangements of a set of n elements. Examples : Input: n = 2 Output: 1…

Try it on GfG Practice Given an array arr[] of size n, the task is to find a distinct sum that can be generated from the subsets of the given sets and return them in increasing order. It is given that the sum of array elements is small. Examples: Input: arr[] = [1, 2] Output: [0, 1, 2, 3]…

Try it on GfG Practice Given two arrays, a[] and b[], find the length of the longest common increasing subsequence(LCIS). LCIS refers to a subsequence that is present in both arrays and strictly increases. Prerequisites: LCS, LIS. Examples: Input: a[] = [3, 4, 9, 1], b[] = [5, 3, 8, 9, 10, 2, 1]…

Try it on GfG Practice Given a string s and y a dictionary of n words dictionary, check if s can be segmented into a sequence of valid words from the dictionary, separated by spaces. Examples: Input: s = "ilike", dictionary[] = ["i", "like", "gfg"] Output: true Explanation: The string can be…

Try it on GfG Practice Given three arrays height[], width[], and length[] of size n, where height[i], width[i], and length[i] represent the dimensions of a box. The task is to create a stack of boxes that is as tall as possible, but we can only stack a box on top of another box if the dimensions of…

Given integers n (the height of the tower), m (the maximum size of tiles available), and k (the maximum number of times each tile size can be used), the task is to calculate the number of distinct stable towers of height n that can be built. Note: A stable tower consists of exactly n tiles, each…

Try it on GfG Practice Given a knapsack weight, say capacity and a set of n items with certain value vali and weight wti, The task is to fill the knapsack in such a way that we can get the maximum profit. This is different from the classical Knapsack problem, here we are allowed to use an unlimited…

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays, val[0..n-1] and wt[0..n-1] represent values and weights associated with n items respectively. Also given an integer W which…

Try it on GfG Practice Given two strings s1 and s2 and below operations that can be performed on s1. The task is to find the minimum number of edits (operations) to convert 's1' into 's2'. Insert: Insert any character before or after any index of s1Remove: Remove a character of s1Replace: Replace a…

Try it on GfG Practice This is a famous interview question asked in Google and many other company interviews. Below is the problem statement. Imagine you have a special keyboard with the following keys: Key 1: Prints 'A' on screen Key 2: (Ctrl-A): Select screen Key 3: (Ctrl-C): Copy selection to…

Try it on GfG Practice Given n items where each item has some weight and profit associated with it and also given a bag with capacity W, [i.e., the bag can hold at most W weight in it]. The task is to put the items into the bag such that the sum of profits associated with them is the maximum…

Given a 2D array jobs[][] of order n*3, where each element jobs[i] defines start time, end time, and the profit associated with the job. The task is to find the maximum profit you can take such that there are no two jobs with overlapping time ranges. Note: If the job ends at time X, it is allowed to…

Try it on GfG Practice Given an array arr[], find the largest divisible subset in the given array. If there are multiple subsets of the largest size, return the lexicographically greatest one after sorting in ascending order. Note: A subset is called divisible if for every pair (x, y) in the subset,…

Try it on GfG Practice Given an matrix of size m x n, the task is to find the count of all unique possible paths from top left to the bottom right with the constraints that from each cell we can either move only to the right or down. Examples: Input: m = 2, n = 2 Output: 2 Explanation: There are two…

Try it on GfG Practice Given two strings, s1 and s2, the task is to find the length of the Longest Common Subsequence. If there is no common subsequence, return 0. A subsequence is a string generated from the original string by deleting 0 or more characters, without changing the relative order of…

Try it on GfG Practice There is a stack of water glasses in the form of a Pascal triangle and a person wants to pour the water at the topmost glass, but the capacity of each glass is 1 unit. Overflow occurs in such a way that after 1 unit, 1/2 of the remaining unit gets into the bottom left glass…

Try it on GfG Practice We are given two numbers n and k, the task is to find how many permutations of the first n number have exactly k inversion. Two elements in a sequence form an inversion if the smaller element appears before the larger element. Examples: Input: n = 3, k = 1 Output: 2…

Try it on GfG Practice Given a matrix mat[][] of size n * m, where mat[i][j] = 1 indicates an obstacle and mat[i][j] = 0 indicates an empty space. The task is to find the number of unique paths to reach (n-1, m-1) starting from (0, 0). You are allowed to move in the right or downward direction.…

Try it on GfG Practice Given a non-negative integer n, the task is to find the nth row of Pascal's Triangle. Note: The row index starts from 1. Examples: Input: n = 4 Output: 1 3 3 1 Explanation: The elements in the 4th row are 1 3 3 1 as shown in Pascal Triangle. Input: n = 1 Output: 1 Explanation:…

Try it on GfG Practice Given an integer values n and k, the task is to find the value of Binomial Coefficient C(n, k). A binomial coefficient C(n, k) can be defined as the coefficient of x^k in the expansion of (1 + x)^n.A binomial coefficient C(n, k) also gives the number of ways, disregarding…

Try it on GfG Practice Given two strings ‘s1‘ and ‘s2‘, find the length of the longest common substring. Example: Input: s1 = “GeeksforGeeks”, s2 = “GeeksQuiz” Output : 5 Explanation: The longest common substring is “Geeks” and is of length 5. Input: s1 = “abcdxyz”, s2 = “xyzabcd” Output : 4…

Try it on GfG Practice Given a rod of length n inches and an array price[]. price[i] denotes the value of a piece of length i. The task is to determine the maximum value obtainable by cutting up the rod and selling the pieces. Note: price[] is 1-indexed array. Input: price[] = [1, 5, 8, 9, 10, 17,…

Given a convex polygon with n sides. The task is to calculate the number of ways in which triangles can be formed by connecting vertices with non-crossing line segments. Examples: Input: n = 3 Output: 1 It is already a triangle so it can only be formed in 1 way. Input: n = 4 Output: 2 It can be cut…