Given n non-negative integers representing the height of bars of width one of a histogram, find the maximum area rectangle of histogram i.e. the maximum area rectangle contained in the histogram. For example, H = [4, 2, 1, 8, 6, 8, 5, 2] then the histogram has a rectangle of area of 20 showed in […]
Heap is a special data structure that has a shape of a complete binary tree (except possibly the deepest internal node) with a special property. We call it ‘Heap Property’. Heap property All nodes are either greater than or equal to (for max heap) or less than or equal to (for min heap) each of […]
Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring. For “(()”, the longest valid parentheses substring is “()”, which has length = 2. Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4. First look at the […]
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1. The trivial solution would be to do double for loop and from each […]
Given a string, find the longest substring that is also a palondrom. One simple solution is to find reverse of S and then find the longest common substring between S and reverse(s). This is also be the longest palindromic substring. That is, LongestPalindromicSubStr(S) = LCS(S, reverse(S)). LCS can be solved by DP in O(n^2) time […]
Given a string, find the longest palindromic substring in linear time i.e. substring that is also a palindrome. Subsequently, Find all palindromic substrings of a given string For example, longest palindromic substring of S = “babaabca” is “baab”. In a previous post I described a simple O(n^2) time solution for this problem. But there is a very beautiful […]
Given a string, find the longest palindromic substring in linear time i.e. substring that is also a palindrome. Subsequently, Find all palindromic substrings of a given string For example, longest palindromic substring of S = “babaabca” is “baab”. In a previous post I described a simple O(n^2) time solution for this problem. But there is a very beautiful […]
Given a string. Find minimum number of insertion (or deletions) required to make it a palindrom. For example, S=”abacba” can be transformed into the longest palindrom P1=”abacaba” just by inserting 1 char. Observe that as long as mirror positions has the same character we have a potential palindrome between the mirror positions (inclusive). Note that, […]
Given an integer matrix, find the length of the longest increasing path. From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed). Example 1: nums = [ [9,9,4], [6,6,8], [2,1,1] ] Return 4 The […]
Given a sequence as as array of positive integers. Find the length of longest bitonic subsequence. A bitonic subsequence is a subsequence that is first increasing up to a peak value and then decreasing from the peak value. For example, A=[1, 11, 2, 10, 4, 5, 2, 1] the longest bitonic sequence is 1, 2, […]