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

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active"]

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;
}

[/restab]
[restab title="Java"]

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

		@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;
}

[/restab]
[/restabs]

6.Test

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active" ]

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));
	}
}

[/restab]
[restab title="Java"]

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() {

			@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));
	}
}

[/restab]
[/restabs]