Minimum Size Subarray Sum

This is a leetCode problem: http://www.programcreek.com/2014/05/leetcode-minimum-size-subarray-sum-java/

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7, the subarray [4,3] has the minimal length of 2 under the problem constraint.

We can solve this by a sliding window, aka inch worm algorithm. Essentially we grow this sliding window to the right if the sum is smaller than the s, once sum >= s, then we update the minimal length of the window and then start to shrink the window from the left until sum < s. Here is the code:

Longest Continuous Ones of a String contains 0 or 1 - inch worm algorithm

Given a string consisted of only 0 or 1, and a number N.

We have N times to flip 0 to 1 in array. Find the longest continuous 1 after we flipped the N zero elements. Rotation is allowed.

For example, 100100111000, n=2, the best flip is 100111111000, return 6

10001101101, n=2, the best flip is 10001111111, return 8(rotation is allowed)

The following algorithm is more like a inch worm walking on a line, it tries to go forward as it can, then shrink from the tail, then move forward again.

/**
     * we first concatenate string to itself
     *
     * then use a sliding window, keep track of number of 0s in the window
     * grow the right side of window if not exceed max 0s allowed
     * otherwise shrink the left side to reduce the 0s
     *
     * the algorithm stops when left side reach the length of original string
     *
     */
    public static int maxContinuous1sWithRotation(String s, int maxFlips){
        int p1=0, p2=0, len = s.length(), num0=0, max=0;
        while(p1<len && p2-p1<len){
            if(s.charAt(p2%len) == '0'){
                num0++;
            }
           
            /*
             * if num0 reaches maxFlips+1
             * we need to shrink the sliding window from left
             * until we reaches a 0 and reduce the counter
             */
            if(num0 > maxFlips){               
                while(p1<len && s.charAt(p1)=='1')
                    p1++;
                p1++; num0--;
            }
           
            /*
             * we keep on growing the sliding window
             * to the right and update the max
             */
            p2++;
            max = Math.max(max, p2-p1);       
        }
        return max;
    }

minimum consecutive sub-string of S containing T

The problem is described from my friend Peng Li's blog:
http://allenlipeng47.com/PersonalPage/index/view/198/nkey

Given a random string S and another string T with unique elements,. find the minimum consecutive sub-string of S such that it contains all the elements in T
example:
S='adobecodebanc'
T='abc'
answer='banc"

We need a sliding window algorithm to solve this problem. The window data structure needs to tell us few things: 1)  are all characters in T found in the window? 2) how many times of each character found in the window appears so far? 3) if all characters are found in the window, can we shrink the window? 

To answer question 1 and 2, we can maintain a hashMap, its key is the character found, the value is the numbers of times the character appears in the window. 
To answer question 3, we need to maintain a data structure which can 1) represent the sliding window; 2) shrink the window if the number of first character in the window is more than once. We will use a Queue to do that, a double-ended queue actually in the below implementation. 

public static String miniSubstr(String s, String t){
        Deque<Item> q = new ArrayDeque<Item>();
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        int p=0, min=Integer.MAX_VALUE;
        String result = null;   
        while(p<s.length()){
            char c = s.charAt(p);
            if(t.indexOf(c)>-1){
                //update the sliding window
                q.add(new Item(c, p));   
                //update the counter map
                if(!map.containsKey(c))
                    map.put(c, 1);
                else
                    map.put(c, map.get(c)+1);   
                //shrink the sliding window if char in the head of q appears more than once
                while(true){
                    Item item = q.peek();
                    Integer num = map.get(item.c);
                    if(num>1){
                        q.removeFirst();
                        map.put(item.c, num-1);
                    }else
                        break;
                }
            }
           
            //when we find all characters, then we update result
            if(map.size() == t.length()){
                int current =  q.peekLast().p - q.peekFirst().p;
                if(current<min){
                    min = current;
                    result = s.substring(q.peekFirst().p, q.peekLast().p+1);
                }
            }
           
            p++;
        }       
        return result;
    }
   
    static class Item{
        char c;
        int p;
        Item(char c, int t){
            this.c = c; this.p = t;
        }
    }

find duplicate elements k indices away in matrix

There are two problems which are quite similar to each other.

Given an array of integer, find duplicates which are within k indices away.  See this link for reference:
http://www.geeksforgeeks.org/check-given-array-contains-duplicate-elements-within-k-distance/

Given a 2D array of integer, find duplicates which are within k indices away.

Both can be solved by using a sliding window of k indicies, maintain a hash storing the elements seen so far then check if the next element is in the hash, if not, remove the element at the start of sliding window and continue.

//for list of integers

public static boolean hasKDistanceDuplicate(int[] array, int k){

Set<Integer> store = new HashSet<Integer>();

for(int i=0, j=0; i<array.length; i++){

//maintain a sliding window of k size

while(j<array.length && j-i<=k){

if(store.contains(array[j])){

return true;

}else{

store.add(array[j]);

j++;

}

}

if(j<array.length)

store.remove(array[i]);

}

return false;

}

//for 2D matrix of integers

public static boolean determineKIndices(int[][] matrix, int k){

Map<Integer, Set<Pos>> store = new HashMap<Integer, Set<Pos>>();

for(int row=0; row<matrix.length; row++){

for(int col=0; col<matrix[0].length; col++){

int val = matrix[row][col];

if(store.containsKey(val)){

Set<Pos> set = store.get(val);

for(Pos p: set){

if(Math.abs(p.getRow() - row) + Math.abs(p.getCol()-col) <=k ){

return true;

}

      if(row - p.getRow() >k)
        set.remove(p);

}

set.add(new Pos(row, col));

}else{

Set<Pos> set = new HashSet<Pos>();

set.add(new Pos(row, col));

store.put(val, set);

}

}

}

return false;

}