Order Statistics: Minimum, Maximum, Median and k-th element

In this article, we are going to do some small researches about Order Statistics. Given a unsorted array, we need to find an elements that is k-th when that array is sorted. When k=0, we have the minimum element. If k=array.length-1, we have the maximum. We may also need to find the median of the array.
In part 1, we will examine the case of minimum and maximum with some little interesting problems.
If you think that this is easy for you, you can skip to part 2 where we discuss solving the general problem in linear time.

Part 1: Special Cases
I. Finding Minimum or Maximum
This is pretty easy problem. Below is the code for finding minimum. For finding maximum, it is similar. To solve this problem, we need to use n-1 comparisons where n is the length of the array.

public int findMinimum(int[] a){

    //We assume the array has at least 1 element        
    int min = a[0];
    for(int i=1; i<a.length; i++){
        if(a[i] < min)
            min = a[i];
    }
    return min;
}

II. Finding Minimum and Maximum
There are cases that we need to find both minimum and maximum of an unsorted array. We can easily find them by using the above algorithm. However, it requires 2 * (n-1) comparisons. We can do better in terms of number of comparisons! Pause yourself for a few seconds to think about it.

In order to solve this, we pick 2 elements at a time. We compare the smaller element with the current min, and the bigger element with the current max, and update min and max accordingly. The number of comparisons is around 3/2 * n.

public int[] findMinAndMax(int[] a){
    //we assume that the array has at least 2 elements
    int min = a[0]>a[1]?a[1]:a[0];
    int max = a[0]>a[1]?a[0]:a[1];
    
    int l = a.length % 2 == 0? a.length:a.length-1;
    int smaller, bigger;
    for(int i = 2; i<l;i+= 2){
        if(a[i] > a[i+1]){
            smaller = a[i+1]; bigger = a[i];
        }else{
            smaller = a[i]; bigger = a[i+1];
        }
        if (min > smaller) min = smaller;
        if (max < bigger) max = bigger;
    }
    
    if(a.length % 2 == 1){
        if(a[a.length-1] > max) max = a[a.length-1];
        else if (a[a.length-1] < min) min = a[a.length-1] ;
    }
    int result[] = new int[]{min, max};
    return result;
}

III. Finding the Second Smallest
To find the second smallest we can easily do it with 2 * n comparisons. And again, we can do better with only (roughly) n + lgn comparisons.
We solve this using divide and conquer approach. First, we find the smallest and second smallest of the first half of the array, then find the smallest of second smallest of the second half of the array. Then we can combine the results of the 2 halves. Below is the java code.

public int findSecondSmallest(int[] a){

    //We assume that the array has at least 2 elements
    return findMinAnd2ndSmallest(a, 0, a.length-1)[1];
} 

//find min & second smallest
private int[] findMinAnd2ndSmallest(int[] a, int start, int end){
    if(start == end) return new int[]{a[start], Integer.MAX_VALUE};
    int[] left = findMinAnd2ndSmallest(a, start, (start+end) / 2);
    int[] right = findMinAnd2ndSmallest(a,(start+end) / 2+1, end);
    int smallest = 0, secondSmallest = 0;
    if(left[0] < right[0]) { 
        smallest = left[0]; secondSmallest = right[0];
        if(right[0] > left[1]) secondSmallest = left[1];
    }else {
        smallest = right[0]; secondSmallest = left[0];
        if(left[0] > right[1]) secondSmallest = right[1];
    }
    return new int[]{smallest, secondSmallest};
}

Part 2: General Cases

Longest Palindromic Substring : From simple to complex solutions

Problem Description
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
Solution
I. Simple solution with expansion from an Index

For each index, we can try to expand as much as possible so that the substring is still palindromic. However, this is O(N^2) time complexity.

public class Solution {
    public String longestPalindrome(String s) {
        if(s.length() <= 1) return s;
        int start = 0, maxLength = 1;
        for(int i = 0; i<s.length();){
            if(s.length() - i <= maxLength/2) break;
            int j = i, k = i;
            while(k < s.length() - 1 && s.charAt(k+1) == s.charAt(k)) ++k;
            i = k + 1;
            while(k < s.length() - 1 && j > 0 && s.charAt(k+1) == s.charAt(j-1)) {++k; --j; }
            int l = k-j+1;
            if(l > maxLength) {maxLength = l; start = j;}
        }
        return s.substring(start, start + maxLength);
    }
}

II. Manacher Algorithm in Linear time

If you are not familiar with Manacher algorithm, you can read more on this wiki article .

import java.util.Arrays;

public class Solution {
    
    public static String longestPalindrome(String s) {
        if (s==null || s.length()==0)
            return "";
        
        char[] s2 = addBoundaries(s.toCharArray());
        int[] p = new int[s2.length]; 
        int c = 0, r = 0; // Here the first element in s2 has been processed.
        int m = 0, n = 0; // The walking indices to compare if two elements are the same
        for (int i = 1; i<s2.length; i++) {
            if (i>r) {
                p[i] = 0; m = i-1; n = i+1;
            } else {
                int i2 = c*2-i;
                if (p[i2]<(r-i)) {
                    p[i] = p[i2];
                    m = -1; // This signals bypassing the while loop below. 
                } else {
                    p[i] = r-i;
                    n = r+1; m = i*2-n;
                }
            }
            while (m>=0 && n<s2.length && s2[m]==s2[n]) {
                p[i]++; m--; n++;
            }
            if ((i+p[i])>r) {
                c = i; r = i+p[i];
            }
        }
        int len = 0; c = 0;
        for (int i = 1; i<s2.length; i++) {
            if (len<p[i]) {
                len = p[i]; c = i;
            }
        }
        char[] ss = Arrays.copyOfRange(s2, c-len, c+len+1);
        return String.valueOf(removeBoundaries(ss));
    }
 
    private static char[] addBoundaries(char[] cs) {
        if (cs==null || cs.length==0)
            return "||".toCharArray();

        char[] cs2 = new char[cs.length*2+1];
        for (int i = 0; i<(cs2.length-1); i = i+2) {
            cs2[i] = '|';
            cs2[i+1] = cs[i/2];
        }
        cs2[cs2.length-1] = '|';
        return cs2;
    }

    private static char[] removeBoundaries(char[] cs) {
        if (cs==null || cs.length<3)
            return "".toCharArray();

        char[] cs2 = new char[(cs.length-1)/2];
        for (int i = 0; i<cs2.length; i++) {
            cs2[i] = cs[i*2+1];
        }
        return cs2;
    }    
}

III. Gusfield's Algorithm

This is an algorithm by Gusfield. If you want to learn more about string algorithm, take a look at Gusfield's course here.

public class Solution {
    char[] temp; 
    public int match(int a, int b,int len){ 
        int i = 0; 
        while (a-i>=0 && b+i<len && temp[a-i] == temp[b+i]) i++; 
        return i; 
    }
    
    public String longestPalindrome(String s) {
        
        //This makes use of the assumption that the string has not more than 1000 characters.
        temp=new char[1001*2];
        int[] z=new int[1001 * 2];
        int L=0, R=0;
        int len=s.length();
    
        for(int i=0;i<len*2+1;i++){
            temp[i]='.';
        }
    
        for(int i=0;i<len;++i){
            temp[i*2+1] = s.charAt(i);
        }
    
        z[0]=1;
        len=len*2+1;
    
        for(int i=0;i<len;i++){
            int ii = L - (i - L);   
            int n = R + 1 - i;
            if (i > R)
            {
                z[i] = match(i, i,len);
                L = i;
                R = i + z[i] - 1;
            }
            else if (z[ii] == n)
            {
                z[i] = n + match(i-n, i+n,len);
                L = i;
                R = i + z[i] - 1;
            }
            else
            {
                z[i] = (z[ii]<= n)? z[ii]:n;
            } 
        }
    
        int n = 0, p = 0;
        for (int i=0; i<len; ++i)
            if (z[i] > n)
                n = z[p = i];
    
        StringBuilder result=new StringBuilder();
        for (int i=p-z[p]+1; i<=p+z[p]-1; ++i)
            if(temp[i]!='.')
                result.append(String.valueOf(temp[i]));
    
        return result.toString();
    }
}

Longest Consecutive Sequence: Some different approaches.

Problem Description

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

Solutions
I. Intuitive Solution

For each element e we check that if e is visited . If not, we check the length of the sequence ends at e-1, and length of the sequence starts at e+1, then combine these 2 sequence. (Note that we only update the 2 ends of the sequence). The following solution using 3 HashMap !!! To see why the "visited" HashMap needed, you can check on the following test case:
[-6,8,-5,7,-9,-1,-7,-6,-9,-7,5,7,-1,-8,-8,-2,0]
Take your time! ^_^

public class Solution {
    public int longestConsecutive(int[] nums) {
        int maxLength = 0;
        Map<Integer, Integer> map1 = new HashMap<Integer, Integer>();
        Map<Integer, Integer> map2 = new HashMap<Integer, Integer>();
        Map<Integer, Boolean> visited = new HashMap<Integer, Boolean>();
        int left, right, l;
        for(int i = 0; i < nums.length; i++){
            if(visited.containsKey(nums[i])) continue;
            visited.put(nums[i], true);
            left = right = nums[i];
            if(map1.containsKey(nums[i]-1)) 
                left -= map1.get(nums[i]-1);
            if(map2.containsKey(nums[i] + 1))
                right += map2.get(nums[i]+1);
            l = right - left + 1;
            if(maxLength < l) maxLength = l;
            
            map1.put(right, l);
            map2.put(left, l);
        }
        return maxLength;
    }
}

II. Improvement on the code

With the above code, we can reduce the space to only 1 HashMap.

public class Solution {
    public int longestConsecutive(int[] num) {
        int longest = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0;i < num.length;i++){
            // if there is no duplicates, these two lines can be commented
            if(map.containsKey(num[i])) continue;
            map.put(num[i],1);

            int end = num[i];
            int begin = num[i];
            if(map.containsKey(num[i]+1))
                end = num[i] + map.get(num[i]+1);
            if(map.containsKey(num[i]-1))
                begin = num[i] - map.get(num[i]-1);
            longest = Math.max(longest, end-begin+1);
            map.put(end, end-begin+1);
            map.put(begin, end-begin+1);
        }
        return longest;
    }
}

III. The same idea as the II) approach can be expressed as the following code:

public class Solution {
    public int longestConsecutive(int[] num) {
        int res = 0;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int n : num) {
            if (!map.containsKey(n)) {
                int left = (map.containsKey(n - 1)) ? map.get(n - 1) : 0;
                int right = (map.containsKey(n + 1)) ? map.get(n + 1) : 0;
                // sum: length of the sequence n is in
                int sum = left + right + 1;
                map.put(n, sum);
    
                // keep track of the max length 
                res = Math.max(res, sum);
    
                // extend the length to the boundary(s)
                // of the sequence
                // will do nothing if n has no neighbors
                map.put(n - left, sum);
                map.put(n + right, sum);
            }
            else {
                // duplicates
                continue;
            }
        }
        return res;
    }
}

IV. Better solution

public class Solution {
    public int longestConsecutive(int[] num) {
        int longest = 0;
        Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();
        for(int i = 0; i< num.length; i++){
            map.put(num[i], false);
        }
        
        int l, k;
        for(int i = 0;i < num.length;i++){
            
            if(map.containsKey(num[i]-1) || map.get(num[i])) continue;
            map.put(num[i], true);
            l = 0; k = num[i];
            while (map.containsKey(k)){
                l++;
                k++;
            }
            if(longest < l) longest = l;
            
        }
        return longest;
    }
}

Copy List With Random Pointers

Problem Description

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Note that, the RandomListNode is defined as below;

class RandomListNode {
    int label;
    RandomListNode next, random;
    RandomListNode(int x) { this.label = x; }
}

Solution 1: Using recursion

public class Solution {

    public HashMap<RandomListNode, RandomListNode> createdNode; 
    public RandomListNode copyRandomList(RandomListNode head) {
        createdNode = new HashMap<RandomListNode, RandomListNode>();
        return cc(head);
    }
    
    private RandomListNode cc(RandomListNode node) {
        if(node == null)
        {
            return null;
        }
    
        RandomListNode newNode = new RandomListNode(node.label);
    
        createdNode.put(node, newNode);        
        newNode.next = cc(node.next);
       
        //now assign the random pointer
        RandomListNode newRandom = null;
        if(node.random != null)
        {
            newRandom = createdNode.get(node.random);
        }
        newNode.random = newRandom;
    
        return newNode;    
    }
}

Solution 2: Using O(n) space

public class Solution{
    
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head == null) return null;
        java.util.HashMap<RandomListNode, RandomListNode> map = new java.util.HashMap<RandomListNode, RandomListNode>();
        RandomListNode copiedHead = new RandomListNode(head.label);
        map.put(head, copiedHead);
        
        for(RandomListNode cur = head.next, cpLst = copiedHead; cur != null; cur = cur.next, cpLst = cpLst.next){
            cpLst.next = new RandomListNode(cur.label);
            map.put(cur, cpLst.next);
        }
        for(RandomListNode cur = head, cpCur = copiedHead; cur != null; cur = cur.next, cpCur = cpCur.next)
            cpCur.random = cur.random == null ? null : map.get(cur.random);
        return copiedHead;
    }
} 

Solution 3: Using O(1) space

In this solution, we don't use the HashMap in the Solution 2.
Suppose that initially we have this RandomList

Without the random pointers, we can copy the list easily. With the random pointers, we don't want to use the hash map, so there must be a way to keep track of information when make a new list. Let's see in the following image

After making such changes, we iterate through the copied list again, assign random pointers, then recover the pointers in the initiali RandomList! And here is the code.

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head == null) return null;
        
        RandomListNode i = head, n, t;
        
        while (i != null) {
            n = i.next;
            RandomListNode copy = new RandomListNode(i.label);
            
            i.next = copy;
            copy.next = n;
            i = n;
        }
    
        //now assign random pointers
        i = head; 
        while(i!=null){
            if(i.random!=null)
                i.next.random = i.random.next;
            i = i.next.next;
        }
        
        //now recover the original structure
        i = head; n = i.next;
        RandomListNode foo = n;
        while(i!=null){
            i.next = n.next;
            i = i.next;
            n.next = i==null?null:i.next;
            n = n.next;
        }
        return foo;
    }
}

Objective C on Windows

As part of my long journey of study, I decided to learn new things every day. Today, I chose to learn Objective C. And let's learn it on Windows!

I. Installation
To start with Objective C on Windows, you will need GNUstep - a open sourced version of Cocoa framework. You can download it from GNUstep.org's downloading page under Download section, or you can download dedicated installers . If you choose dedicated installers, install each of the following packages in order (Basically you should install GNUstep MSYS System, GNUstep Core and GNUstep Cairo)

Package	Required?	Stable	Unstable	Notes
GNUstep MSYS System	Required	0.30.0	-	MSYS/MinGW System
GNUstep Core	Required	0.34.0	-	GNUstep Core
GNUstep Devel	Optional	1.4.0	-	Developer Tools
GNUstep Cairo	Optional	0.34.0	-	Cairo Backend
ProjectCenter	Optional	0.6.1-2	-	IDE (Like Xcode, but not as complex)
Gorm	Optional	1.2.20-2	-	Interface Builder (Like Xcode NIB builder)

Another choice is to install MinGW with options to include GNUstep core packages.

II. Hello World Program

Create a GNUmakefile as below and save it as a [.mak] file:

include $(GNUSTEP_MAKEFILES)/common.make
# make a simple program in Objective-C, call it HelloWorld
TOOL_NAME = HelloWorld
# The implementation Objective-C file which is going to be compiled
HelloWorld_OBJC_FILES = hello.m
# Header files of your project
#HelloWorld_HEADER_FILES = xxx.h //here goes all header files (.h). For the moment, on n'en a pas.
# Define compilation flags
ADDITIONAL_CPPFLAGS = -Wall -Wno-import
# Include rules for creating a command line tool for Objective-C
include $(GNUSTEP_MAKEFILES)/tool.make

Then create a file named hello.m with the following content:

#import <Foundation/Foundation.h>
 
int main (int argc, const char * argv[]) {
 
    NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];
    NSLog(@"***Hello World!***");//This will output Hello World!
 
    [pool release];
    return 0;
}

Now open a command line window of GNUsetup Environment. You can choose Start / GNUstep / Shell
After the window opened, cd to folder that you have saved the code and make file, for example:

cd C:\objectiveC\HelloWorld

Next, type the command make
There will be a new folder with name "obj" added to the current folder. Now cd to obj folder, and run the compiled program with the following command

HelloWorld

Voila! You've got Objective C in Windows. Let's learn more about Objective C from RyPress or any other site!!!
Enjoy Objective C ^_^.
Some day, I will continue studying Swift, although most developers should avoid Swift

LeetCode: The Skyline Problem

Problem Description

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

 

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .

The output is a list of "key points" (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:

• The number of buildings in any input list is guaranteed to be in the range [0, 10000].
• The input list is already sorted in ascending order by the left x position Li.
• The output list must be sorted by the x position.
• There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]

Solution:

LeetCode: Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
Solution: 
Below is a simple solution in Python:

# Definition for an interval.
# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution:

    def insert(self, intervals, newInterval):
        l = []
        count = 0
        while(count < len(intervals)):
            if(newInterval.start <= intervals[count].end):
                if(newInterval.end >= intervals[count].start):
                    newInterval.start = min(intervals[count].start, newInterval.start)
                break
            l.append(intervals[count])
            count += 1
        l.append(newInterval)
        while(count < len(intervals)):
            if(newInterval.end < intervals[count].start):
                break
            l[-1].end = max(intervals[count].end, l[-1].end)
            count += 1
        while(count < len(intervals)):
            l.append(intervals[count])
            count += 1
        return l

And here is a faster solution using binary search:

class Solution:  
  
    def insert(self, intervals, newInterval):  
        if len(intervals) == 0:  
            return [newInterval]  
              
        v1 = self.search(intervals, newInterval.start,0, len(intervals)-1, 0)  
        v2 = self.search(intervals, newInterval.end,(v1)>>1, len(intervals)-1, 1)  
   
        if (v1 & 1):  
            newInterval.start = intervals[v1>>1].start   
        if (v2 & 1):  
            newInterval.end = intervals[(v2)>>1].end 
                  
        return intervals[:(v1>>1)] + [newInterval] + intervals[(v2+1)>>1:] 
          
    def search(self, intervals, index, start=0, end=0, isStart=0):  
        while(start <= end):  
            middle = (end+start)>>1 
            if intervals[middle].start <= index and intervals[middle].end >= index:  
                return (middle << 1)+1 
            if intervals[middle].start > index:  
                end = middle - 1
            else:
                start = middle + 1       
        return start << 1

Third solution:

class Solution: 
  
    def insert(self, intervals, newInterval):
        s, e = newInterval.start, newInterval.end
        left = [i for i in intervals if i.end < s]
        right = [i for i in intervals if i.start > e]
        if left + right != intervals:
            s = min(s, intervals[len(left)].start)
            e = max(e, intervals[~len(right)].end)
        return left + [Interval(s, e)] + right

If you want to train the code reading skills, here is another approach in Java:

/**
 * Definition for an interval.
 **/
class Interval {
    int start;
    int end;
    Interval() { start = 0; end = 0; }
    Interval(int s, int e) { start = s; end = e; }
}

public class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval){
        List<Interval> is = new ArrayList<Interval>();
        if(intervals == null || newInterval == null) return is;

        int status = 0;
        Interval open = null;
        for(Interval i: intervals){

            //if not found a interval containing the newInterval
            if(status==0){
                if(i.start > newInterval.end){
                    is.add(newInterval);
                    is.add(i);
                    status = 2;
                }else if(i.end < newInterval.start){
                    is.add(i);
                }else if(i.start<= newInterval.start && i.end < newInterval.end){
                    open = new Interval(i.start, newInterval.end);
                    status = 1;
                }else if(i.start > newInterval.start && i.end < newInterval.end){
                    status = 1;
                    open = new Interval(newInterval.start, newInterval.end);
                }else {
                    is.add(new Interval(Math.min(newInterval.start, i.start), i.end));
                    status = 2;
                }
            }else if(status == 1){
                if(i.start <= newInterval.end && i.end>= newInterval.end){
                    status = 2;
                    open.end = i.end;
                    is.add(open);
                }else if(i.start > newInterval.end){
                    status = 2;
                    open.end = newInterval.end;
                    is.add(open);
                    is.add(i);
                }                
            }else {   //status = 2
                is.add(i);
            }
        }

        if(status == 0) is.add(newInterval);
        if(status == 1){
            open.end = newInterval.end;
            is.add(open);
        }
        return is;
    }
}