1. Runtime Distribution

2. Submission Details

3. Description

You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.

What is the maximum number of envelopes can you Russian doll? (put one inside other)

4. Example

Given envelopes = [[5,4],[6,4],[6,7],[2,3]], the maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

5. Code

private static int[][] sort(int[][] envelopes, int minValue, int range, int sortBy) {
    int[] count = new int[range + 1];
    for (int[] envelope : envelopes) {
        count[envelope[sortBy] - minValue + 1]++;
    }
    for (int i = 0; i < count.length - 1; i++) {
        count[i + 1] += count[i];
    }
    int[][] sortedEnvelopes = new int[envelopes.length][envelopes[0].length];
    for (int[] envelope : envelopes) {
        sortedEnvelopes[count[envelope[sortBy] - minValue]][0] = envelope[0];
        sortedEnvelopes[count[envelope[sortBy] - minValue]++][1] = envelope[1];
    }
    if (sortBy == 0) {
        return sortedEnvelopes;
    }
    int[] tmp;
    int j = sortedEnvelopes.length - 1;
    for (int i = 0; i < (sortedEnvelopes.length >> 1); i++, j--) {
        tmp = sortedEnvelopes[i];
        sortedEnvelopes[i] = sortedEnvelopes[j];
        sortedEnvelopes[j] = tmp;
    }
    return sortedEnvelopes;
}

public static int[][] radixSort(int[][] envelopes) {
    int minW = Integer.MAX_VALUE, maxW = Integer.MIN_VALUE;
    int minH = Integer.MAX_VALUE, maxH = Integer.MIN_VALUE;
    for (int[] envelope : envelopes) {
        minW = minW < envelope[0] ? minW : envelope[0];
        maxW = maxW > envelope[0] ? maxW : envelope[0];
        minH = minH < envelope[1] ? minH : envelope[1];
        maxH = maxH > envelope[1] ? maxH : envelope[1];
    }
    envelopes = sort(envelopes, minH, maxH - minH + 1, 1);
    envelopes = sort(envelopes, minW, maxW - minW + 1, 0);
    return envelopes;
}

public int maxEnvelopes(int[][] envelopes) {
    if (envelopes == null || envelopes.length < 1) {
        return 0;
    }

    envelopes = radixSort(envelopes);

    int length = 0;
    int[] dp = new int[envelopes.length];
    for (int[] envelope : envelopes) {
        int index = Arrays.binarySearch(dp, 0, length, envelope[1]);
        if (index < 0) {
            index = -(index + 1);
        }
        dp[index] = envelope[1];
        if (index == length) {
            length++;
        }
    }
    return length;
}

public int maxEnvelopes(int[][] envelopes) {
    Arrays.sort(envelopes, new Comparator<int[]>() {

        @Override
        public int compare(int[] arg0, int[] arg1) {

            if (arg0[0] != arg1[0]) {
                return arg0[0] - arg1[0];
            } else {
                return arg1[1] - arg0[1];
            }
        }
    });

    int dp[] = new int[envelopes.length];
    int length = 0;
    for (int[] envelope : envelopes) {
        int index = Arrays.binarySearch(dp, 0, length, envelope[1]);
        if (index < 0) {
            index = -index - 1;
        }
        dp[index] = envelope[1];
        if (index == length) {
            length++;
        }
    }
    return length;
}

6.Test

import java.util.Arrays;
import org.junit.Test;

public class LeetCode0354 {

    private static int[][] sort(int[][] envelopes, int minValue, int range, int sortBy) {
        int[] count = new int[range + 1];
        for (int[] envelope : envelopes) {
            count[envelope[sortBy] - minValue + 1]++;
        }
        for (int i = 0; i < count.length - 1; i++) {
            count[i + 1] += count[i];
        }
        int[][] sortedEnvelopes = new int[envelopes.length][envelopes[0].length];
        for (int[] envelope : envelopes) {
            sortedEnvelopes[count[envelope[sortBy] - minValue]][0] = envelope[0];
            sortedEnvelopes[count[envelope[sortBy] - minValue]++][1] = envelope[1];
        }
        if (sortBy == 0) {
            return sortedEnvelopes;
        }
        int[] tmp;
        int j = sortedEnvelopes.length - 1;
        for (int i = 0; i < (sortedEnvelopes.length >> 1); i++, j--) {
            tmp = sortedEnvelopes[i];
            sortedEnvelopes[i] = sortedEnvelopes[j];
            sortedEnvelopes[j] = tmp;
        }
        return sortedEnvelopes;
    }

    public static int[][] radixSort(int[][] envelopes) {
        int minW = Integer.MAX_VALUE, maxW = Integer.MIN_VALUE;
        int minH = Integer.MAX_VALUE, maxH = Integer.MIN_VALUE;
        for (int[] envelope : envelopes) {
            minW = minW < envelope[0] ? minW : envelope[0];
            maxW = maxW > envelope[0] ? maxW : envelope[0];
            minH = minH < envelope[1] ? minH : envelope[1];
            maxH = maxH > envelope[1] ? maxH : envelope[1];
        }
        envelopes = sort(envelopes, minH, maxH - minH + 1, 1);
        envelopes = sort(envelopes, minW, maxW - minW + 1, 0);
        return envelopes;
    }

    public int maxEnvelopes(int[][] envelopes) {
        if (envelopes == null || envelopes.length < 1) {
            return 0;
        }

        envelopes = radixSort(envelopes);

        int length = 0;
        int[] dp = new int[envelopes.length];
        for (int[] envelope : envelopes) {
            int index = Arrays.binarySearch(dp, 0, length, envelope[1]);
            if (index < 0) {
                index = -(index + 1);
            }
            dp[index] = envelope[1];
            if (index == length) {
                length++;
            }
        }
        return length;
    }

    @Test
    public void test() {
        int[][] envelopes = { { 5, 4 }, { 6, 4 }, { 6, 7 }, { 2, 3 } };
        System.out.println(maxEnvelopes(envelopes));
    }
}

import java.util.Arrays;
import java.util.Comparator;

import org.junit.Test;

public class LeetCode0354 {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, new Comparator<int[]>() {

            @Override
            public int compare(int[] arg0, int[] arg1) {

                if (arg0[0] != arg1[0]) {
                    return arg0[0] - arg1[0];
                } else {
                    return arg1[1] - arg0[1];
                }
            }
        });

        int dp[] = new int[envelopes.length];
        int length = 0;
        for (int[] envelope : envelopes) {
            int index = Arrays.binarySearch(dp, 0, length, envelope[1]);
            if (index < 0) {
                index = -index - 1;
            }
            dp[index] = envelope[1];
            if (index == length) {
                length++;
            }
        }
        return length;
    }

    @Test
    public void test() {
        int[][] envelopes = { { 5, 4 }, { 6, 4 }, { 6, 7 }, { 2, 3 } };
        System.out.println(maxEnvelopes(envelopes));
    }
}