Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is: [ "((()))", "(()())", "(())()", "()(())", "()()()" ] This problem can be solved in many different ways. Some of them include “DFS”, “BFS”, “backtracking”, “Dynamic Programming”, “Recursion”. In this tutorial we shall consider “Recursion” solution. If you need help in solving in other method, please let […]
Letter Combinations of a Phone Number
Problem statement: Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters. Below is the sample input and output: Input: "23" Output: ["ad", […]
Remove Nth Node from End of List
Problem description: Given a linked list, remove the n-th node from the end of list and return its head. Example: Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5. Here I shall be solving with 2 different type of solution. Solution 1: Fast […]
Given an array n integers and an integer key, are there four elements a, b, c, and d in the array such that a + b + c + d = key? Find all unique quadruplets in the array which gives the sum of key.
Note: The solution set must not contain duplicate quadruplets. Example: Given array nums = [1, 0, -1, 0, -2, 2], and target = 0. A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ] This problem is also called as 4 sums. Now before we solve this […]
Given an array of n integers and an integer “key”, find three integers in the array such that the sum is closest to key.
Input: [-1, 2, 1, -4] Key = 1 Output: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2) This problem is also known as three sum closest The solution to this problem is similar to “two sums”. Hence I would recommend you to please check out the […]
Given an array, find 3 elements such that [a + b + c] = 0. Find all the 3 unique elements.
This question can also be called as “three sum”. Input = [-1, 0, 1, 2, -1, -4], Output: [ [-1, 0, 1], [-1, -1, 2] ] This problem can be solved in 2 ways. 1. Iterative. Time complexity O (n ^ 3). 2. With the help of “two sum” solution. Time complexity O(n^2). We shall […]
Given an array of non repeating numbers and a key, find all the unique combinations in that array, where the sum of those combination is equal to the key.
Input: Array = [2,3,6,7], key = 7, Output: [ [7], [2,2,3] ] Example 2: Input: candidates = [2,3,5], target = 8, A solution set is: [ [2,2,2,2], [2,3,3], [3,5] ] Note: The input array is sorted, with no repeated elements. Here as there is no time constraint we can solve this example with the help […]
Find the Container with Most Water explanation with diagram and solution
Problem description: Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains […]
Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’.
Note: ‘.’ Matches any single character. ‘*’ Matches zero or more of the preceding element. Example 1: Input: Pattern: a.b Valid Strings: acb – any character can be present in place of "." aab – same reason as above adb – same reason as above Invalid Strings: ab – Because in middle some element should […]
Longest Palindromic Substring In C++
Given a string, find the longest palindromic string in that array. A palindromic string will give the same string when read reverse. Example: “aba” reverse is “aba” hence is a palindromic string. Input: ashdkabajjseiw Output: aba Please try to solve in O(n^2). There are 3 approaches, in this topic we shall discuss 2 methods 1. […]