Max submatrix sum in a matrix

Problem

Given an NxN matrix of positive and negative integers, write code to find the sub- matrix with the largest possible sum.

Solution

This is DP problem. Here is the good solution.
References

• http://tianrunhe.wordpress.com/2012/06/11/max-submatrix-sum-in-a-matrix/

Read More

Find max subsquare whose border values are all 1

Problem

Imagine you have a square matrix, where each cell is filled with either black or white. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels.

Solution

We are going to scan column by column, checking to see if this column can be the left-border of the desired subsquare. Along each column, we build “sliding windows”, from large size to small size. The size of the window is the size of the subsquare. The winodw starts at different row, moving from top to bottom. When the window is fixed in a position, we chan check if this subsquare is valid or not. If so, we update the max subsquare we have found then continue.
Example:
111
011
000

1. 1st column:
   1. 1st row: window size = 3: {{1,1,1,},{0,1,1},{0,0,0}} is not valid; window size = 2: {{1,1,},{0,1}} is not valid; window size = 1: {{1}} is valid, so update it.
   2. 2nd row: window size = 2: {{0,1},{0,0}} is not valid; window size = 1: no need to check. already have a current max subsquare with size 1.
2. 2nd column:
   1. 1st row: window size = 2: {{1,1},{1,1}} is valid, so update it; window size = 1: no need to check.
   2. 2nd row: no need to check. Max subsquare can be found is of size 2, but we already have a valid one with size 2.
3. 3rd column:No need to check.

Java code

public static int[][] findMaxSubsquare(int[][] square) {
    int[][] maxSubsquare = null;
    int maxSize = 0;
    for (int col = 0; square.length - col > maxSize; ++col) {
        for (int row = 0; square.length - row > maxSize; ++row) {
            for (int size = square.length - Math.max(row, col); 
                        size > maxSize; --size) {
                if (isValidSubsquare(square, row, col, size)) {
                    maxSize = size;
                    maxSubsquare = new int[size][size];
                    for (int i = row; i < size + row; ++i)
                        System.arraycopy(square[i], col, maxSubsquare[i
                                - row], 0, size);
                }
            }
        }
    }
    return maxSubsquare;
}
 
private static boolean isValidSubsquare(int[][] square, int row, int col,
        int size) {
    // up and bottom border
    for (int j = col; j < col + size; ++j) {
        if (square[row][j] == 0)
            return false;
        if (square[row + size - 1][j] == 0)
            return false;
    }
    // left and right border
    for (int i = row; i < row + size; ++i) {
        if (square[i][col] == 0)
            return false;
        if (square[i][col + size - 1] == 0)
            return false;
    }
    return true;
}

References

• http://tianrunhe.wordpress.com/2012/06/11/find-max-subsquare-whose-border-values-are-all-1/

Read More

Transform one word into another by changing only one letter at a time

Problem

Given two words of equal length that are in a dictionary, write a method to transform one word into another word by changing only one letter at a time. The new word you get in each step must be in the dictionary.
EXAMPLE
Input: DAMP, LIKE
Output: DAMP -> LAMP -> LIMP -> LIME -> LIKE

Solution

Try thinking this problem in terms of graphs: Consider all words in a dictionary as vertices, and insert an edge between each two vertices that differ by only one letter. The output is a well-known object in the graph, and you probably already know an algorithm to solve the problem.

The output is a path in the graph, and the question is solved by finding a path. A breadth-first search (BFS) or Dijkstra's algorithm solve the problem elegantly.


Java code

public static List<String> transform(String src, String des,
    Set<String> dictionary) {
    Queue<String> Q = new LinkedList<String>();
    Set<String> visited = new HashSet<String>();
    Map<String, String> routes = new HashMap<String, String>();
    Q.add(src);
    visited.add(src);
    while (!Q.isEmpty()) {
        String t = Q.poll();
        if (t.equals(des)) {
            LinkedList<String> list = new LinkedList<String>();
            while (t != null) {
                list.add(0, t);
                t = routes.get(t);
            }
            return list;
        }
        for (String o : getAllTransformations(t, dictionary)) {
            if (!visited.contains(o)) {
                visited.add(o);
                Q.add(o);
                routes.put(o, t);
            }
        }
    }
    return null;
}
 
private static List<String> getAllTransformations(String src,
        Set<String> dictionary) {
    List<String> results = new LinkedList<String>();
    for (int i = 0; i < src.length(); ++i) {
        for (char c = 'A'; c <= 'Z'; ++c) {
            String newStr = src.substring(0, i) + c + src.substring(i + 1);
            if (!src.equals(newStr) && dictionary.contains(newStr))
                results.add(newStr);
        }
    }
    return results;
}

Thanks.

References

• http://tianrunhe.wordpress.com/2012/06/10/transform-one-word-into-another-by-changing-only-one-letter-at-a-time/
• http://stackoverflow.com/questions/11509636/transforming-one-word-into-another-word-by-changing-only-one-letter-at-a-time 

Read More

Search a long string for small strings in an array

Problem

Given a string s and an array of smaller strings T, design a method to search s for each small string in T.

Solution

Method 1 - Using suffix tree
We can first get all the suffices of s and check for each element  t in T to see if t is the beginning part of any suffices. To make this more efficient, we can build a suffix tree and do the operations.

For example, s = “mississippi”; T = { “is”, “sip”, “hi”, “sis” }.
The suffices of s

[0]	“mississippi”
[1]	“ississippi”
[2]	“ssissippi”
[3]	“sissippi”
[4]	“issippi”
[5]	“ssippi”
[6]	“sippi”
[7]	“ippi”
[8]	“ppi”
[9]	“pi”
[10]	“i”

Then for “is” in T, we see it sits in the beginning of suffices [1] and [4]. for “sip”, we see it in [6]. We do not see any “hi” in the suffices but we do see “sis” in [3].

Java code

public static class SuffixTree {
    SuffixTreeNode root = new SuffixTreeNode();
 
    public SuffixTree(String s) {
        for (int i = 0; i < s.length(); ++i) {
            root.insert(s.substring(i), i);
        }
    }
 
    public List<Integer> getIndexes(String s) {
        return root.getIndices(s);
    }
}
 
public static class SuffixTreeNode {
    private char c;
    private List<Integer> indices = new ArrayList<Integer>();;
    private Map<Character, SuffixTreeNode> children = 
        new HashMap<Character, SuffixTreeNode>();
 
    public void insert(String s, int index) {
        indices.add(index);
        if (s != null && s.length() > 0) {
            char character = s.charAt(0);
            if (children.keySet().contains(character)) {
                children.get(character).insert(
                        s.substring(1), index);
            } else {
                SuffixTreeNode child = new SuffixTreeNode();
                children.put(character, child);
                child.insert(s.substring(1), index);
            }
        }
    }
 
    public List<Integer> getIndices(String s) {
        if (s == null || s.length() == 0)
            return indices;
        else {
            char character = s.charAt(0);
            if (children.containsKey(character))
                return children.get(character).getIndices(
                        s.substring(1));
            else
                return null;
        }
    }
}

Thanks.

References

• http://tianrunhe.wordpress.com/2012/06/10/search-a-long-string-for-small-strings-in-an-array/

Read More

Longest word made of other words in an array

Problem

Write a program to find the longest word made of other words.
EXAMPLE
Input: test, tester, testertest, testing, testingtester
Output: testingtester

Solution

1. This problem can be easily solved using a "Trie data structure"
2. First I sort the strings in descending order "Lengthwise", so longest string comes first.
3. Start with the first string and loop over sorted strings
4. Check if it can be made of other words by dividing strings into all possible combinations and doing same thing for each splits. So, whenever we find the word in the larger string, we delete the shorter word from the bigger word.
5. Retrun true if it is made of other strings and Save that string onto an array list.
6. Return the top string because that would be the longest string.
7. The size of array list will give you the total number of words that can be made of other words.

Java code

public static class LengthComparator implements Comparator<String> {
    public int compare(String o1, String o2) {
        if (o1.length() < o2.length())
            return 1;
        else if (o1.length() > o2.length())
            return -1;
        else
            return 0;
    }
}
 
public static String longestWordMadeOfOtherWords(String[] words) {
    Arrays.sort(words, new LengthComparator());
    for (String word : words) {
        String backup = new String(word);
        for (String otherWord : words) {
            if (!otherWord.equals(backup) && word.contains(otherWord)) {
                word = word.replace(otherWord, "");
            }
        }
        if (word.length() == 0)
            return backup;
    }
    return null;
}

Thanks.
References

• http://tianrunhe.wordpress.com/2012/06/10/longest-word-made-of-other-words-in-an-array/

Read More

Find largest 1M numbers in 1B numbers

Problem

Describe an algorithm to find the largest 1 million numbers in 1 billion numbers. Assume that the computer memory can hold all one billion numbers.

Solutions

Method 1 - Sorting
We can certainly sort those numbers and return the last 1 million of them. That takes O(n log n).

Method 2 - Sort partially using some pivot
If we think about it, we actually do not need to sort them. After all, we just need the largest 1 million numbers, in whatever orders. Therefore we can sort of “partially” sort the numbers and try to find the parts that we need. To do this, we get inspiration from Quicksort, where we get two partitions around pivot during each run.

For simplicity, Let us denote the number of elements in the right part as m.
If m is exactly equal to 1 million, we have found the largest 1 million numbers!
If m is larger than 1 million, we need to keep looking for the 1 million numbers, but in the left part of the array this time. We can do this in a recursive way.
If m is less than 1 million, we first remember those m numbers and then we search for the largest (1 million - m) numbers in the left part of the array. Again, recursion here.
Using the random pivot choosing approach, this algorithm takes O(n) time complexity and it does not need any additional space since we can do the partition in place.

Java code

public static int quickPartition(int[] array, int low, int high) {
    if (high <= low)
        return -1;
 
    // randomly choose a pivot
    int index = new Random().nextInt(high - low + 1) + low;
    int pivot = array[index];
 
    // swap the pivot to the front
    int num = array[index];
    array[index] = array[low];
    array[low] = num;
 
    // partition as in Quicksort
    int L = low + 1;
    int R = high;
 
    while (R >= L) {
        while (R >= L && array[L] < pivot)
            L++;
        while (R >= L && array[R] >= pivot)
            R--;
        if (R >= L) {
            int temp = array[L];
            array[L] = array[R];
            array[R] = temp;
            L++;
            R--;
        }
    }
 
    // swap the pivot back to appropriate position.
    num = array[R];
    array[R] = array[low];
    array[low] = num;
 
    return R;
}
 
public static List<Integer> largestM(int[] numbers, int M, int low, int high) {
    // RIndex = index of pivot
    int RIndex = quickPartition(numbers, low, high);
    // mFound = # of the largest numbers
    int mFound = high + 1 - RIndex;
 
    List<Integer> results = new LinkedList<Integer>();
 
    if (mFound == M) { // Done!
        int i = RIndex;
        for (; i <= high; ++i)
            <span class="skimlinks-unlinked">results.add(numbers</span>[i]);
        return results;
 
    } else if (mFound > M) { // Keep looking
        // check if those mFound elements are actually the same
        boolean duplicates = true;
        for (int i = RIndex; i <= high; ++i) {
            if (numbers[i] != numbers[RIndex])
                duplicates = false;
        }
 
        if (!duplicates)
            return largestM(numbers, M, RIndex, high);
        else {
            // if they are the same, just return M duplicates of them
            for (int k = 0; k < M; ++k)
                <span class="skimlinks-unlinked">results.add(numbers</span>[RIndex]);
            return results;
        }
    } else { // Has found some, keep looking for the rest
        int i = RIndex;
        for (; i < numbers.length; ++i)
            <span class="skimlinks-unlinked">results.add(numbers</span>[i]);
 
        results.addAll(largestM(numbers, M - mFound, low, RIndex - 1));
        return results;
    }
 
}

Method 3 - Using heap
Run them all through a max-heap of size 100: for each input number k, replace the current min m with max(k, m). Afterwards the heap holds the 100 largest inputs.
A search engine like Lucene can use this method, with refinements, to choose the most-relevant search answers.
1) Build a Max Heap tree in O(n)
2) Use Extract Max k times to get k maximum elements from the Max Heap O(klogn)
Time complexity: O(n + klogn)

Thanks
References

• http://tianrunhe.wordpress.com/2012/06/09/find-largest-1m-numbers-in-1b-numbers/

Read More

Shortest distances between two words in a file

Problem

You have a large text file containing words. Given any two words, find the shortest distance (in terms of number of words) between them in the file. Can you make the searching operation in O(1) time? What about the space complexity for your solution?

OR

Find the minimum distance between 2 numbers in the array?

Example

File contains:

as was is the as the yahoo you me was the and

Example 1
Input words: the, was
Output distance : 0 
( as was is the as the yahoo you me was the and)
 
Example 2
Input words : you, the
Output distance: 2
(as was is the as the yahoo you me was the and)

Solution

Method 1 - Use 2 indices and current min
We have already solved this example here for array of integers, same logic has to be applied on array of words.

static int getMinDistance(String[] words, String word1, String word2) {
 int pos = 0;
 int min = Integer.MAX_VALUE / 2;
 int word1_pos = -min;
 int word2_pos = -min;
 for (int i = 0; i < words.length; i++) {
  String current_word = words[i];
  if (current_word.equals(word1)) {
   word1_pos = pos;  
   int distance = word1_pos - word2_pos;
   if (min > distance)
   min = distance;
  } else if (current_word.equals(word2)) {
   word2_pos = pos;
   int distance = word2_pos - word1_pos;
   if (min > distance) min = distance;
  }
  ++pos;
 }
 return min;
}

Time Complexity O(n)
Space Complexity O(1)

Method 2 - Using hashtable
To solve this problem in less time (but more space), we can create a hash table with each word and the locations where it occurs. We then just need to find the minimum (arithmetic) difference in the locations (e.g., abs(word0.loc[1] - word1.loc[5])).

1. Pre-processing: Store the locations for different words in a hashtable. One scan of the text: O(n) time complexity. Approximately O(n) space complexity.
2. Query: Modified binary search. For example, query is (hello, world). Lookup in the hashtable we have "hello" -> [1,2] and "world" -> [5,8,9]. We search 1 in [5,8,9] to find the nearest, which is 5. So the distance is 4. We search 2 in [5,8,9] to find the nearest, which is 5 again, yielding distance 3, less than 4. So the shortest distance between "hello" and "world" is 3. In practice, number of locations for a word is relatively small comparing to the size of the text, hence the cost of query/search is nearly constant.

So, if 2 numbers have to be changed again and again, method 1 is not that good, but method 2 will be better. Here is the code:

private static Map<String, ArrayList<Integer>> locations = new HashMap<String, ArrayList<Integer>>();
 
private static void storeLocations(String[] text) {
    for (int i = 0; i < text.length; ++i) {
        String word = text[i];
        if (locations.keySet().contains(word)) {
            ArrayList<Integer> location = locations.get(word);
            location.add(i);
            Collections.sort(location);
            locations.put(word, location);
        } else {
            ArrayList<Integer> location = new ArrayList<Integer>();
            location.add(i);
            locations.put(word, location);
        }
    }
}
 
private static int modified_binary_search(ArrayList<Integer> array,
        int target) {
    int low = 0;
    int high = array.size();
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (target == array.get(mid))
            return target;
        if (target < array.get(mid))
            high = mid;
        else
            low = mid + 1;
    }
    if (low >= 0 && low < array.size())
        return array.get(low);
    else
        return array.get(array.size() - 1);
}
 
private static int shortest_distance(String a, String b) {
    int min = Integer.MAX_VALUE;
    for (int index_a : locations.get(a)) {
        ArrayList<Integer> array = locations.get(b);
        int nearest_index_b = modified_binary_search(array, index_a);
        int distance = Math.abs(nearest_index_b - index_a);
        if (distance < min)
            min = distance;
    }
    return min;
}

Time Complexity O(n)
Space Complexity O(n)


References

• http://tianrunhe.wordpress.com/2012/06/04/shortest-distances-between-two-words-in-a-file/

Read More

Count the number of 2s between 0 and n

Problem

Write a method to count the number of 2s between 0 and n.

Example

Input Range : between 0-20, 
Output : 3 (i.e 2, 12 , 20))

Solution

We need recursion. The number n can be broken down into a couple of ranges. The number of 2’s of numbers in each range is independent of each other. For example, 3345 can be broken into [0, 3000] and (3000, 3345]. We can easily get the formula for the number of 2’s of k⋅10^m. Example for numbers 200 to 299, we will have 100 2's.

For the extra at the tail, we observe that n2(3000,3345]=n2(0,345]. (0, 345] can then be broken down in the same way. The only catch is, say,  if the range is (2000, 2345], we need to add 345 more 2’s, i.e., n2(2000,2345]=n2(0,345]+345. In general, the total number of added tail is the number of 2’s at the higher bits.

Algorithm

We need to first count 2’s in the range between 0 and 10^m.

• For the lowest digit, 1 out of every 10 numbers has a 2. 
• For the 10’s digit, 10 out of every 100 numbers have a 2. 
• In general, for a digit x, 1 out of every 10 numbers will have a 2. So the total number of 2’s depends on how many digits we have. Define the number of 2’s in the range X as N(X). We have

N((0,10])=1×10⁰=1,
N((0,100])=2×10¹=20,
N((0,1000])=3×10²=300,⋯
N((0,10^x=x×10^x−1


for k =1 no extra 2 in leading digit, for k=2, it’s one extra 2, for k>2, there are 10x leading 2s.
For a number, we split it into two parts: the MSB and the reminder. For example, 319 has MSB of 3 and reminder of 19.

1. Count the number of 2s for MSB:
   1. If MSB > 2: We will have 1 or 10 or 100 or 1000, etc 2s. In this case of 319, we have 100 2s (occurring at MSB from 200 to 299).
   2. If MSB == 2: We will have reminder+1 2s. For example if we have n = 219, we have 20 2s (occurring at MSB from 200 to 219).
2. Count the number of 2s for reminder, two parts:
   1. Recursively count the number of 2s for the tens. For example of n = 319, we’d like to recursively count number of 2s from 1 to 100. We then know we have 3 times that number of 2s. This is like: we know number 12 has a 2, so we know number 12, 112 and 212 have three 2s.
   2. Count the number of 2s causing from the reminder. For example of n = 319, we’d like to recursively count number of 2s from 1 to 19. That counts for the number of 2s appearing from 301 to 319.

Process from low to high, accumulate counts in each step with N(0,digit∗10^m). In processing from low to high, we can also keep track of the number to the right so that when we encounter a digit>=2, we can add the number to the right to the count.

// Take n = 319 as example
public static int numberOf2s(int n) {
    if (n < 2)
        return 0;
 
    int result = 0;
    int power10 = 1;
    while (power10 * 10 < n) {
        power10 *= 10;
    }
    // power10 = 100
    int msb = n / power10; // 3
    int reminder = n % power10; // 19
 
    // Count # of 2s from MSB
    if (msb > 2)
        // This counts the first 2 from 200 to 299
        result += power10;
    if (msb == 2)
        // If n = 219, this counts the first 2
        // from 200 to 219 (20 of 2s).
        result += reminder + 1;
 
    // Count # of 2s from reminder
    // This (recursively) counts for # of 2s from 1 to 100
    // msb = 3, so we need to multiply by that.
    result += msb * numberOf2s(power10);
    // This (recursively) counts for # of 2s from 1 to reminder
    result += numberOf2s(reminder);
 
    return result;
}

Reference

• http://tianrunhe.wordpress.com/2012/06/04/count-the-number-of-2s-between-0-and-n/
• http://www.delbertbao.net/2012/07/01/counting-2s/ 

Read More

Randomly generate m integers from an array of size n

Problem

Write a method to randomly generate a set of m integers from an array of size n Each element must have equal probability of being chosen.

Solution

This question depends on 2 things:

• how random number generation works?
• Fisher yates algorithm or Knuth Shuffle?

Now that we have fisher yates algorithm in our quiver, we can solve this problem :

let m be the number of elements to select
for i = 1; i <= m; i++
   pick a random number from 1 to n, call it j
   swap array[j] and array [n] (assuming 1 indexed arrays)
   n-- 

public static int[] chooseNFromM(int[] array, int m) {
    if (m > array.length)
        return null;
    int[] results = new int[m];
    for (int i = 0; i < m; ++i) {
        int index, temp;
        do {
            index = new Random().nextInt(array.length);
        } while (index < i);
        temp = array[index];
        array[index] = array[i];
        array[i] = temp;
    }
    for (int i = 0; i < m; ++i) {
        results[i] = array[i];
    }
    return results;
}

We don't need to keep generating random numbers. We just need to label which ones are 'dead' (in this case, 0 to i) and generate random index in the valid range (i+1 to n).
We should first make an copy of the original array as we don't want to modify it.

References

• http://tianrunhe.wordpress.com/2012/06/04/randomly-generate-m-integers-from-an-array-of-size-n/
• http://stackoverflow.com/questions/6251626/choosing-a-subset-in-uniformly-random-manner 

Read More

Add two numbers without using arithmetic operators

Problem

Write a function Add() that returns sum of two integers. The function should not use any of the arithmetic operators (+, ++, –, -, .. etc).

Solution
We can get carry by &(and) operator and bit by ^ (xor) operator. We have already seen, how we can use bit-wise operators to replace arithmetic operators i.e. implement arithmetic operators using bitwise operators.


Method 1 - Iterative method

int Add(int x, int y)
{
    // Iterate till there is no carry 
    while (y != 0)
    {
        // carry now contains common set bits of x and y
        int carry = x & y; 
 
        // Sum of bits of x and y where at least one of the bits is not set
        x = x ^ y;
 
        // Carry is shifted by one so that adding it to x gives the required sum
        y = carry << 1;
    }
    return x;
}

Method 2 - Recursive approach

int Add(int x, int y)
{
    if (y == 0)
        return x;
    else
        return Add( x ^ y, (x & y) << 1);
}

Thanks.

Read More

Maximum Area Rectangle in Histogram

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 the histogram below:

Max area of the rectangle:

Max area = 4 * 3 = 12

 

Note that the area of the largest rectangle may exceed the largest 32-bit integer. Due to the large numbers of rectangles, the naive O(n²) solution is too slow. Even though O(n*log(n)) or O(n) is required, there are several kinds of solutions to this problem. In the following, we will identify a histogram with the sequence of the heights of its rectangles.

1. Divide-and-conquer using order-statistic trees.
   Initially, build a binary, node- and leaf-labeled tree that contains the histogram as its frontier, i.e., as its leaves from left to right. Mark each inner node with the minimum of the labels of its subtree. Note that such a tree is most efficiently stored in an array using the heap data structure, where the children of node i are located at positions i*2 and i*2+1, respectively. With such an order-statistic tree, the minimum element in a subhistogram (i.e., a subsegment of the sequence of heights) can be found in O(log(n)) steps by using the additional information in the inner nodes to avoid searching all leaves.
   To calculate the maximum rectangle unter a subhistogram, we thus find the minimum height in that subhistogram, and divide it at just that place into two smaller histograms. The maximum rectangle is either completely in the left part, or completely in the right part, or it contains the rectangle with minimum height. The first two cases are solved recursively, while in the third case we know that the width of the maximum rectangle is the width of the whole subhistogram, since we chose the minimum height. Because every element serves exactly once as a place to divide, and we spend O(log(n)) for every division, the complexity of this algorithm is O(n*log(n)).
2. Linear search using order-statistic trees.
   Initially, construct an order-statistic tree as just described. For every element, we find the largest rectangle that includes that element. The height of the rectangle is, of course, the value of the element. Use the order-statistic tree to efficiently find the nearest elements that have smaller heights, both to the left and to the right. The width, and therefore the area of the rectangle can thus be calculated in O(log(n)) steps, giving a total runtime of O(n*log(n)).
3. Sweeping line maintaining intervals.
   Initially, sort the heights so they can be processed in non-increasing order. We sweep a horizontal line downwards through the histogram, maintaining a list of those intervals, where the line intersects the histogram. Actually, the intervals are maintained in an array with one entry for every element of the histogram in the following manner. At the element corresponding to the left end of an interval we store a pointer to the right end, and vice versa.
   As a new element arrives during the sweeping process, this element forms a new interval, and, if there are adjacent intervals, these can be merged in constant time using our representation. The largest rectangle including this element, just as described in the previous algorithm, is available without further expense, since we can read its width from our representation. Actually, it is not quite the largest rectangle, because there may be further elements with equal heights adjacent to the current interval. Performing the sweep in a non-increasing order, however, guarantees that the largest rectangle will have been considered by the time the last element of a group having equal heights is examined. The complexity is dominated by the sorting phase, thus O(n*log(n)), although a radix sort is possible if the heights are bounded.
4. Linear search using a stack of incomplete subproblems
   We process the elements in left-to-right order and maintain a stack of information about started but yet unfinished subhistograms. Whenever a new element arrives it is subjected to the following rules. If the stack is empty we open a new subproblem by pushing the element onto the stack. Otherwise we compare it to the element on top of the stack. If the new one is greater we again push it. If the new one is equal we skip it. In all these cases, we continue with the next new element.
   If the new one is less, we finish the topmost subproblem by updating the maximum area w.r.t. the element at the top of the stack. Then, we discard the element at the top, and repeat the procedure keeping the current new element. This way, all subproblems are finished until the stack becomes empty, or its top element is less than or equal to the new element, leading to the actions described above. If all elements have been processed, and the stack is not yet empty, we finish the remaining subproblems by updating the maximum area w.r.t. to the elements at the top.
   For the update w.r.t. an element, we find the largest rectangle that includes that element. Observe that an update of the maximum area is carried out for all elements except for those skipped. If an element is skipped, however, it has the same largest rectangle as the element on top of the stack at that time that will be updated later.
   The height of the largest rectangle is, of course, the value of the element. At the time of the update, we know how far the largest rectangle extends to the right of the element, because then, for the first time, a new element with smaller height arrived. The information, how far the largest rectangle extends to the left of the element, is available if we store it on the stack, too.
   We therefore revise the procedure described above. If a new element is pushed immediately, either because the stack is empty or it is greater than the top element of the stack, the largest rectangle containing it extends to the left no farther than the current element. If it is pushed after several elements have been popped off the stack, because it is less than these elements, the largest rectangle containing it extends to the left as far as that of the most recently popped element.
   Every element is pushed and popped at most once and in every step of the procedure at least one element is pushed or popped. Since the amount of work for the decisions and the update is constant, the complexity of the algorithm is O(n) by amortized analysis.
   Solution
5. Recursive search
   For a recursive version of the algorithm just described, see the reference below. Indeed, if the recursion is eliminated the necessary stack is analogous to the explicit stack in the iterative version.
6. Rewrite System
   The problem may be generalized by allowing histograms to be composed of rectangles with varying widths. Then, the stack used in the just described algorithms can be concatenated with the yet unprocessed part of the histogram into one list.
   A three element window is moved over this list, starting at the left end. In every step, different actions are performed according to the relative heights of the three elements under inspection. The actions include updating the maximum, merging two of the three elements by taking the minimum of their heights and the sum of their widths, and sliding the window one element to the left or to the right. Rules are provided that specify the actions for each configuration.
   Actually, the behaviour of the stack-based algorithm is simulated. The correctness of the rewrite system can be shown by proving an invariant about the maximum area of the histogram, observing that every configuration is matched by some rule, and giving a termination proof using a variant expression. Additionally, it can be proved that O(n) rewrite steps (each with a constant amount of work) are performed.

Source - 1 , 2,

Read More

Find the median in a continous stream of numbers

Problem

Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated.

OR

You are given a stream of numbers which can be positive or negative. You are required to provide an operation FIND MEDIAN..which when invoked should be able return the median of the numbers in stream(in say O(1) time)

OR 

Find the rolling median?

Example

0 1 2 3 4
Right FIND MEDIAN returns 2 as median

Now input is -2 -4
So Stream = 0 1 2 3 -2 -2 -4
Sorted Stream would be -4 -2 0 1 2 3 4 and FIND MEDIAN returns 1

Solution

Method 1 - Using heap
We maintain two heaps: minHeap and maxHeap. If we represent these two heaps in terms of list, minHeap is in descending order whereas maxHeap is in ascending order. If we manage to maintain these two heaps while getting new numbers, the median is either in the first place of minHeap or in the first place of maxHeap (or the average of these two).

Pseudocode

Step 1: Add next item to one of the heaps

   if next item is smaller than maxHeap root add it to maxHeap,
   else add it to minHeap

Step 2: Balance the heaps (after this step heaps will be either balanced or
   one of them will contain 1 more item)

   if number of elements in one of the heaps is greater than the other by
   more than 1, remove the root element from the one containing more elements and
   add to the other one

if some one calls getMedian...then
   If the heaps contain equal elements;
     median = (root of maxHeap + root of minHeap)/2
   Else
     median = root of the heap with more elements

Consider the example of sequence of numbers: 1, 2, 3, 4 and 5. The maintainence of minHeap, maxHeap are shown below:

After 1 coming:
minHeap: 1
maxHeap:
median : 1

After 2 coming:
minHeap: 1
maxHeap: 2
median : 1.5

After 3 coming:
minHeap: 1
maxHeap: 2 3
median : 2

After 4 coming:
minHeap: 1 2
maxHeap: 3 4
median : 2.5

After 5 coming:
minHeap: 1 2
maxHeap: 3 4 5
median : 3

Java code

public static class maxComparator implements Comparator<Double> {
    public int compare(Double o1, Double o2) {
        return -o1.compareTo(o2);
    }
}
 
static PriorityQueue<Double> minHeap = new PriorityQueue<Double>(11,
        new maxComparator());
static PriorityQueue<Double> maxHeap = new PriorityQueue<Double>();
 
public static void addToHeap(double number) {
    if (minHeap.size() == maxHeap.size()) {
        if (minHeap.isEmpty())
            minHeap.add(number);
        else if (number > minHeap.peek())
            maxHeap.add(number);
        else { // number < minHeap.peek()
            maxHeap.add(minHeap.poll());
            minHeap.add(number);
        }
    } else if (minHeap.size() > maxHeap.size()) {
        if (number > minHeap.peek())
            maxHeap.add(number);
        else { // number <= minHeap.peek()
            maxHeap.add(minHeap.poll());
            minHeap.add(number);
        }
    } else { // minHeap.size() < maxHeap.size()
        if (number < maxHeap.peek())
            minHeap.add(number);
        else { // number >= maxHeap.peek()
            minHeap.add(maxHeap.poll());
            maxHeap.add(number);
        }
    }
}
 
public static double getMedian() {
    if (minHeap.size() == maxHeap.size())
        return (minHeap.peek() + maxHeap.peek()) / 2;
    else if (minHeap.size() > maxHeap.size())
        return minHeap.peek();
    else
        return maxHeap.peek();
}

Method 2 - Using counting sort for integers
We can use counting sort for integers, which will give us A[n/2] as median. But of course this will not work for

Method 3 - Using Balanced Binary Search Trees

At every node of BST, maintain number of elements in the subtree rooted at that node. We can use a node as root of simple binary tree, whose left child is self balancing BST with elements less than root and right child is self balancing BST with elements greater than root. The root element always holds effective median.
If left and right subtrees contain same number of elements, root node holds average of left and right subtree root data. Otherwise, root contains same data as the root of subtree which is having more elements. After processing an incoming element, the left and right subtrees (BST) are differed utmost by 1.
Self balancing BST is costly in managing balancing factor of BST. However, they provide sorted data which we don’t need. We need median only. The next method make use of Heaps to trace median.

1. Data Structure providing sorted order is a Binary Search Tree. However worst case it can be linear list.
2. Store the numbers in a BST..if the tree is not fully balanced i.e. it's left or right skewed use tree rotations across the root in O(1) to make the height of left and right subtree same.
3. Now root node would be at the median. This can be found in O(1) time.

Now the height of left and right subtrees across the root is same and we stop.

Finding height of a binary search tree can be done in O(log h) where h is the height of tree

Method 4 - Using skiplist and queue
See the answer here.

Method 5 - P² algorithm
See the answer here.

Thanks. Please share if you have some other ways.

References

• http://stackoverflow.com/questions/10657503/find-running-median-from-a-stream-of-integers
• http://tianrunhe.wordpress.com/2012/06/10/online-median-finding-and-maintainence/

Read More