This is from leetcode: link. Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. The solution is to maintain 2 array, maxLeft[], maxRight[]. maxLeft[i] maintains the max profit from price[0],…,price[i] by one transaction. maxRight[i] maintains from price[i],…,price[length-1] by… Read More »
This is from leetcode, Best Time to Buy and Sell Stock IV. Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most k transactions. The answer is to use dynamic programming by local and global 2-dimension array to implement… Read More »
I solved this problem one year ago. This time I solved it again and wrote some analysis for it. Problem definition: Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. For simplicity, assume that all bars have same width and the… Read More »
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. Below are the 2… Read More »
Problem description: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. For example, Given the input [0,1,0,2,1,0,1,3,2,1,2,1] the return value would be 6 This problem can be solved in O(n) time, by going through from left to… Read More »
I saw the original problem from G4G. Given an array of strings with R, G & B as characters. Sort the array such that all R comes first, followed by Gs & followed by Bs. Do it in O(n) time complexity. (Paper Code) For example: I/P: G G R B R B B G R B R O/P: R R R R G G… Read More »
Problem: Given n strings, check if exist 2 of strings which can group a palindrome. For example, for strings ‘aaa’, ‘aac’, ‘ab’, ‘acblb’, ‘ac’, ‘ddcaa’. ‘aac’ and ‘ddcaa’ can group into palindrome; ‘acblb’ and ‘ac’ can group into palindrome. We can solve this problem using trie and rolling hash queue. For example, below is when first 4… Read More »
This is from G4G. link Problem description: Given an array of size n where all elements are in range from 0 to n-1, change contents of arr[] so that arr[i] = j is changed to arr[j] = i. Examples: Example 1: Input: arr[] = {1, 3, 0, 2}; Output: arr[] = {2, 0, 3, 1};… Read More »
The characteristic of circle sort is that it takes least swap operation than any other sorting algorithm. Given an integer array a[], it loops the element start_pos from a[0] to a[length-2]. Each time, find the right position(next_pos) for a[start_pos]. And we should still find the position for a[next_pos], and update the next_pos on and on, until next_pos… Read More »
This problem is from careercup, link Problem description: 1. qaz is a value for a number where this number is less than the other next values which have indexes larger than the index of this number. for example: 33 , 25 , 26 , 58 , 41 , 59 -> qaz of (33) = 3… Read More »