Maximum value in a Sliding Window

Problem Statement Question: A long array A[] is given to you. There is a sliding window of size w, which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position. Example: The array is [1 3 -1 -3 5 3 6 7], and w is 3. Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 ...

Read More

Container With Most Water

http://n00tc0d3r.blogspot.in/2013/02/container-with-most-water.ht...

Read More

Maximum Area Rectangle in Histogram using linear search via stack of incomplete sub problems

We have already discussed lots of solution to solve this here, and using the stack to achieve is one of them. Problem Question: Find the maximum rectangle (in terms of area) under a histogram in linear time. I mean the area of largest rectangle that fits entirely in the Histogram. (Please refer figures before code section for clarity. If I include bar i completely, those figure will tell how much maximum area rectangle I can get.) Consider...

Read More

Arrays Index

Rotated array How to rotate an array? Rotated sorted array Find the minimum element in the rotated sorted array. Find the rotation count in rotated sorted array Find Nth largest element in the rotated sorted array Search an element in the sorted rotated array  Sorted Infinite Arrays Searching the element in sorted infinite array of integers Find the point of transition from 0 to 1 in an infinite sorted array containings only 0 and 1 .  Binary or only few integer arrays Find the point of transition from 0 to 1 in an infinite...

Read More

Maximum weight independent set (WIS) graph problem using DP

Input - A path graph G = (V,E) with non - negative weights on vertices eg.Consider the graph with vertex weights - 1,4,5,4 Desired output - subset of non-adjacent vertices - an independent set of maximum total weights. Solutions Brute force polynomial time, so lets do better. greedy approach Greedy algos are easy to implement but are sometimes not correct. To apply greedy approach here we have to iteratively choose the max-weight vertex ...

Read More

Sequence Alignment using Dynamic Programming

Problem : Input : 2 strings or sequence of characters i.e. X = x1x2...xm, Y = y1y2...yn Goal - To define the similarity matrix between the 2 sequences with best alignment. This is based on penalty score, called Needleman/Wunsch score. Eg. consider the sequence - AGGGCT and AGGCA , best alignment here is: AGGGCT  |  |  |      | AGG - CA Penalty Penalty = penalty of match+penalty of difference + penalty of...

Read More