Sliding Window Maximum

Source

Problem

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. Following is an 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       5  1  3  -1  -3 [5  3  6] 7       6  1  3  -1  -3  5 [3  6  7]      7 

Input: A long array A[], and a window width w
Output: An array B[], B[i] is the maximum value of from A[i] to A[i+w-1]
Requirement: Find a good optimal way to get B[i]

Good sites for questions

• http://gurmeetsingh.wordpress.com/puzzles/
• http://www.khanacademy.org/ # brain teasers section
• http://pratikpoddarcse.blogspot.com/
• http://geeksforgeeks.org
• http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index
• http://www.ihas1337code.com
• http://dzmitryhuba.blogspot.com/
• http://www.careercup.com/

Finding the Minimum Window in S which Contains All Elements from T

Source

Problem

Find the smallest window in a string containing all characters of another string

Given two strings string1 and string2, find the smallest substring in string1 containing all characters ofstring2 efficiently.

For Example:

Input string1: “this is a test string”
Input string2: “tist”
Output string: “t stri”

Solution:

Best explained here

Search in a row wise and column wise sorted matrix

Source


Problem
Given an n x n matrix, where every row and column is sorted in increasing order. Given a number x, how to decide whether this x is in the matrix. The designed algorithm should have linear time complexity.

Solution

int search(int mat[4][4], int n, int x)

{

int i = 0, j = n-1; //set indexes for top right element

while ( i <>= 0 )

{

if ( mat[i][j] == x )

{

printf("\n Found at %d, %d", i, j);

return 1;

}

if ( mat[i][j] > x )

j--;

else // if mat[i][j] <>

i++;

}

printf("\n Element not found");

return 0; // if ( i==n || j== -1 )

}




My solution

Consider an element in the main diagonal.

If you were to think about a matrix with current diagonal element as the last element (last row, last column) that element is bound to be the largest element in the sub matrix. So if the number which we are looking for is

greater then the current diagonal element, we move to next element in

the diagonal (downward).

Moment we find the number we are searching for to be less then the diagonal element.

We can apply binary search in the part of the column above the diagonal element or part of the row on the LHS of the diagonal element.

Complexity: worst case we have to traverse to the bottom most element in the diagonal:

N iteration + 2 * logn for (binary search in row and column)

O(n + 2*logn) => O(n)