Russian Doll Envelopes Problem in Java
The Russian Doll Envelopes Problem is a classic computer science problem that can be framed as a variation of the Longest Increasing Subsequence (LIS) problem. The problem statement involves a collection of envelopes, each represented by a pair of integers (width, height). An envelope A can fit into another envelope B if and only if both the width and height of A are strictly smaller than the width and height of B. The task is to find the maximum number of envelopes you can put one inside the other.
Approach 1: Longest Increasing Subsequence (LIS)
The approach using Longest Increasing Subsequence (LIS) is a common and efficient strategy for solving the Russian Doll Envelopes Problem. The key idea is to sort the envelopes based on one dimension (width or height) and then find the LIS based on the other dimension.
Algorithm
Step 1: A class Envelope is defined to represent an envelope, with two attributes: width and height. The class implements the Comparable interface to allow sorting based on the width.
Step 2: The maxEnvelopes function takes a 2D array envelopes as input, where each row represents an envelope [width, height]. It first checks if the input is valid, and if not, returns 0.
Step 3: Convert the 2D array of envelopes into an array of Envelope objects. Sort the array of envelopes based on the width in ascending order using Arrays.sort(envelopeObjects).
Step 4: Initialize an array dp of length n (number of envelopes) to store the length of the LIS ending at each index. Initialize maxEnvelopes to 1 (minimum possible value).
Step 5: Iterate over each envelope i from 1 to n-1. For each i, iterate over envelopes j from 0 to i-1. If the height of envelope i is greater than the height of envelope j, update dp[i] = max(dp[i], dp[j] + 1).
Step 6: Update maxEnvelopes with the maximum value in the dp array. The final result is stored in maxEnvelopes. In the main method, an example 2D array of envelopes is created. The maxEnvelopes function is called with this array, and the result is printed.
Filename: RussianDollEnvelopes.java
import java.util.Arrays;
class Envelope implements Comparable<Envelope> {
int width;
int height;
public Envelope(int width, int height) {
this.width = width;
this.height = height;
}
public int compareTo(Envelope other) {
return Integer.compare(this.width, other.width);
}
}
public class RussianDollEnvelopes {
public static int maxEnvelopes(int[][] envelopes) {
if (envelopes == null || envelopes.length == 0) {
return 0;
}
int n = envelopes.length;
Envelope[] envelopeObjects = new Envelope[n];
for (int i = 0; i < n; i++) {
envelopeObjects[i] = new Envelope(envelopes[i][0], envelopes[i][1]);
}
// Sort envelopes based on width in ascending order
Arrays.sort(envelopeObjects);
// Use LIS approach to find the maximum number of envelopes
int[] dp = new int[n];
Arrays.fill(dp, 1);
int maxEnvelopes = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (envelopeObjects[i].height > envelopeObjects[j].height) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxEnvelopes = Math.max(maxEnvelopes, dp[i]);
}
return maxEnvelopes;
}
public static void main(String[] args) {
int[][] envelopes = {{5, 4}, {6, 4}, {6, 7}, {2, 3}};
System.out.println("Maximum number of envelopes: " + maxEnvelopes(envelopes));
}
}
Output:
Maximum number of envelopes: 3
Time Complexity
Sorting the array of envelopes takes O(n log n) time, where 'n' is the number of envelopes. The dynamic programming step involves two nested loops, contributing O(n^2) time complexity. The overall time complexity is O(n log n) + O(n^2), which simplifies to O(n^2) dominated by the dynamic programming step.
Space Complexity
The space complexity is O(n) due to the additional arrays used are: the envelopeObjects array of Envelope objects is O(n). The dp array used for dynamic programming is O(n). The sorting process may be considered as in-place, so it doesn't contribute to additional space complexity. The overall space complexity is O(n).
Approach 2: Binary Search
The approach of using Binary Search to solve the Russian Doll Envelopes Problem is an optimization over the LIS (Longest Increasing Subsequence) approach. The key idea is to sort the envelopes based on one dimension (usually width) and then apply a binary search to find the correct position for the current envelope in a temporary array, simulating the LIS calculation.
Algorithm
Step 1: A class Envelope is defined to represent an envelope, with two attributes: width and height. The class implements the Comparable interface to allow sorting based on the width.
Step 2: The maxEnvelopes function takes a 2D array envelopes as input, where each row represents an envelope [width, height]. It first checks if the input is valid, and if not, returns 0.
Step 3: Convert the 2D array of envelopes into an array of Envelope objects. Sort the array of envelopes based on the width in ascending order using Arrays.sort(envelopeObjects).
Step 4: Binary Search Simulation: Initialize an array tails to simulate the Longest Increasing Subsequence (LIS). Initialize a variable len to 0 to keep track of the current length of the LIS.
Step 5: Iterate over each envelope in the sorted array. Use binary search to find the position where the current envelope can be placed in the tails array.
Step 6: If there is an existing tail element greater than or equal to the current envelope's height, update that tail. Otherwise, append the current envelope to the tails array and increment len.
Step 7: The final value of len represents the length of the LIS and, hence, the maximum number of nested envelopes.
Step 8: The final result is stored in len. In the main method, an example 2D array of envelopes is created. The maxEnvelopes function is called with this array, and the result is printed.
Filename: RussianDollEnvelopes1.java
import java.util.Arrays;
class Envelope implements Comparable<Envelope> {
int width;
int height;
public Envelope(int width, int height) {
this.width = width;
this.height = height;
}
public int compareTo(Envelope other) {
return Integer.compare(this.width, other.width);
}
}
public class RussianDollEnvelopes {
public static int maxEnvelopes(int[][] envelopes) {
if (envelopes == null || envelopes.length == 0) {
return 0;
}
int n = envelopes.length;
Envelope[] envelopeObjects = new Envelope[n];
for (int i = 0; i < n; i++) {
envelopeObjects[i] = new Envelope(envelopes[i][0], envelopes[i][1]);
}
// Sort envelopes based on width in ascending order
Arrays.sort(envelopeObjects);
// Use Binary Search approach to find the maximum number of envelopes
int[] tails = new int[n];
int len = 0;
for (Envelope envelope : envelopeObjects) {
int index = Arrays.binarySearch(tails, 0, len, envelope.height);
if (index < 0) {
index = -(index + 1);
}
tails[index] = envelope.height;
if (index == len) {
len++;
}
}
return len;
}
public static void main(String[] args) {
int[][] envelopes = {{5, 4}, {6, 4}, {6, 7}, {2, 3}};
System.out.println("Maximum number of envelopes: " + maxEnvelopes(envelopes));
}
}
Output:
Maximum number of envelopes: 3
Time Complexity
The sorting step takes O(n log n) time, where 'n' is the number of envelopes. The binary search simulation step takes O(n log n) time. The overall time complexity is dominated by the sorting step and is O(n log n).
Space Complexity
The space complexity is O(n) due to the additional arrays used: The envelopeObjects array of Envelope objects is O(n). The tails array used for binary search simulation is O(n). The sorting process may be considered as in-place, so it doesn't contribute to additional space complexity. The overall space complexity is O(n).
Approach 3: Using TreeMap
The approach using TreeMap for solving the Russian Doll Envelopes problem is based on leveraging the TreeMap data structure to efficiently track the heights encountered during traversal of the sorted envelopes. TreeMap is a Red-Black tree-based implementation of the NavigableMap interface in Java, providing sorted key-value mappings.
Algorithm
Step 1: Sort the envelopes based on width in ascending order. If two envelopes have the same width, sort them in descending order of height. This sorting step is essential for ensuring that envelopes are processed in the correct order.
Step 2: Initialize a TreeMap named heightMap to keep track of heights encountered during traversal. The TreeMap should use integers as keys (representing heights) and integers as values (representing the count of envelopes with that height).
Step 3: Traverse Sorted Envelopes: Iterate through the sorted envelopes array. For each envelope at index i, get the height of the current envelope (envelopes[i][1]).
Step 4: Use lowerKey(currentHeight) to find the greatest height strictly less than the current envelope's height in heightMap.
Step 5: If a lower height is found, update the count of the current envelope's height in heightMap. The updated count should be the maximum of the current count and the count of the lower height plus one.
Step 6: If no lower height is found, add an entry for the current envelope's height to heightMap with a count of 1.
Step 7: The size of the heightMap at the end represents the maximum number of envelopes that can be nested. Return this maximum count as the result.
Filename: RussianDollEnvelopes2.java
import java.util.Arrays;
import java.util.TreeMap;
public class RussianDollEnvelopes {
public static int maxEnvelopes(int[][] envelopes) {
if (envelopes == null || envelopes.length == 0) {
return 0;
}
int n = envelopes.length;
Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
TreeMap<Integer, Integer> heightMap = new TreeMap<>();
heightMap.put(envelopes[0][1], 1);
for (int i = 1; i < n; i++) {
int currentHeight = envelopes[i][1];
Integer lowerHeight = heightMap.lowerKey(currentHeight);
if (lowerHeight != null) {
int currentCount = heightMap.getOrDefault(currentHeight, 0);
int lowerCount = heightMap.get(lowerHeight);
heightMap.put(currentHeight, Math.max(currentCount, lowerCount + 1));
} else {
heightMap.put(currentHeight, heightMap.getOrDefault(currentHeight, 0) + 1);
}
}
return heightMap.values().stream().mapToInt(Integer::intValue).max().orElse(0);
}
public static void main(String[] args) {
int[][] envelopes = {{5, 4}, {6, 4}, {6, 7}, {2, 3}};
System.out.println("Maximum number of envelopes: " + maxEnvelopes(envelopes));
}
}
Output:
Maximum number of envelopes: 3
Time Complexity
The sorting step takes O(n log n) time, where 'n' is the number of envelopes. The TreeMap operations inside the loop take O(log n) time for each envelope, and there are 'n' envelopes. The overall time complexity is dominated by the sorting step, and the TreeMap operations contribute O(n log n). Therefore, the overall time complexity is O(n log n).
Space Complexity
The space complexity is O(n) due to the additional TreeMap used. The sorting process may be considered as in-place, so it doesn't contribute to additional space complexity. The overall space complexity is O(n).
Approach 4: Using Recursion
A recursive approach to solving the Russian Doll Envelopes problem involves finding the Longest Increasing Subsequence (LIS) using recursion. The idea is to try different envelopes as the starting point and recursively find the LIS for each possible starting envelope.
Algorithm
Step 1: Sort the envelopes based on width in ascending order. If two envelopes have the same width, sort them in descending order of height.
Step 2: Extract the heights from the sorted envelopes and store them in a separate array, say heights.
Step 3: Define a recursive function, say findLIS, that takes an index as a parameter and returns the length of the LIS starting from that index.
Step 4: If the current index is the last index, return 1, as the LIS starting from the last element has a length of 1.
Step 5: Recursive Case: For the current index i, iterate over all indices j from i+1 to the end of the array. If heights[i] < heights[j], recursively call findLIS(j) to find the LIS starting from index j.
Step 6: Update the result to be the maximum of the current result and 1 + findLIS(j). The maximum result obtained by trying different starting indices represents the length of the overall LIS.
Filename: RussianDollEnvelopes3.java
import java.util.Arrays;
public class RussianDollEnvelopes {
public static int maxEnvelopes(int[][] envelopes) {
if (envelopes == null || envelopes.length == 0) {
return 0;
}
int n = envelopes.length;
Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
int[] heights = new int[n];
for (int i = 0; i < n; i++) {
heights[i] = envelopes[i][1];
}
int maxLength = 0;
for (int i = 0; i < n; i++) {
maxLength = Math.max(maxLength, findLIS(heights, i));
}
return maxLength;
}
private static int findLIS(int[] heights, int index) {
if (index == heights.length - 1) {
return 1;
}
int result = 1;
for (int j = index + 1; j < heights.length; j++) {
if (heights[index] < heights[j]) {
result = Math.max(result, 1 + findLIS(heights, j));
}
}
return result;
}
public static void main(String[] args) {
int[][] envelopes = {{5, 4}, {6, 4}, {6, 7}, {2, 3}};
System.out.println("Maximum number of envelopes: " + maxEnvelopes(envelopes));
}
}
Output:
Maximum number of envelopes: 3
Time Complexity
The sorting step takes O(n log n) time. The recursive function has an exponential time complexity of O(2^n), where 'n' is the number of envelopes. The overall time complexity is dominated by the sorting step and is O(n log n) in practice.
Space Complexity
The space complexity is O(n) due to the additional arrays used (heights array). The sorting process may be considered as in-place, so it does not contribute to additional space complexity. The overall space complexity is O(n).