Given N number of envelopes, as {W, H} pair, where W as the width and H as the height. 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. Find the maximum number of envelopes that can be put inside another envelope and so on. Rotation of envelope is not allowed.
Examples:
Input: envelope[] = {{4, 3}, {5, 3}, {5, 6}, {1, 2}}
Output: 3
Explanation:
The maximum number of envelopes that can be put into another envelope
is 3.
({1, 2}, {4, 3}, {5, 6})Input: envelope[] = {{3, 6}, {5, 4}, {4, 8}, {6, 9}, {10, 7}, {12, 12}}
Output: 4
Explanation:
The maximum number of envelopes that can be put into another envelope is 4.
({3, 6}, {4, 8}, {6, 9}, {12, 12})
Naive Approach: This problem is similar to the Longest Increasing Subsequence problem of Dynamic Programming. The idea is to sort the envelopes in non-decreasing order and for each envelope check the number of envelopes that can be put inside that envelope. Follow the steps below to solve the problem:
- Sort the array in the non-decreasing order of width and height.
- Initialize a dp[] array, where dp[i] stores the number of envelopes that can be put inside with envelope[i] as the largest envelope.
- For each envelope[i], loop through the envelopes smaller than itself and check if the width and the height of the smaller envelope is strictly less than that of envelope[i]. If it is less, than the smaller envelope can be put inside envelope[i].
- The maximum of the dp[] array gives the maximum number of envelopes that can be put inside one another.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function that returns the maximum// number of envelopes that can be// inserted into another envelopesint maxEnvelopes(vector<vector<int> > envelopes){ // Number of envelopes int N = envelopes.size(); if (N == 0) return N; // Sort the envelopes in // non-decreasing order sort(envelopes.begin(), envelopes.end()); // Initialize dp[] array int dp[N]; // To store the result int max_envelope = 1; dp[0] = 1; // Loop through the array for (int i = 1; i < N; ++i) { dp[i] = 1; // Find envelopes count for // each envelope for (int j = 0; j < i; ++j) { if (envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1] && dp[i] < dp[j] + 1) dp[i] = dp[j] + 1; } // Store maximum envelopes count max_envelope = max(max_envelope, dp[i]); } // Return the result return max_envelope;}// Driver Codeint main(){ // Given the envelopes vector<vector<int> > envelopes = { { 4, 3 }, { 5, 3 }, { 5, 6 }, { 1, 2 } }; // Function Call cout << maxEnvelopes(envelopes); return 0;} |
Java
// Java program for the above approachimport java.util.*;import java.lang.*;class GFG{ // Function that returns the maximum// number of envelopes that can be// inserted into another envelopesstatic int maxEnvelopes(int[][] envelopes){ // Number of envelopes int N = envelopes.length; if (N == 0) return N; // Sort the envelopes in // non-decreasing order Arrays.sort(envelopes, (a, b) -> (a[0] != b[0]) ? a[0] - b[0] : a[1] - b[1]); // Initialize dp[] array int[] dp = new int[N]; // To store the result int max_envelope = 1; dp[0] = 1; // Loop through the array for(int i = 1; i < N; ++i) { dp[i] = 1; // Find envelopes count for // each envelope for(int j = 0; j < i; ++j) { if (envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1] && dp[i] < dp[j] + 1) dp[i] = dp[j] + 1; } // Store maximum envelopes count max_envelope = Math.max(max_envelope, dp[i]); } // Return the result return max_envelope;}// Driver Codepublic static void main (String[] args){ // Given the envelopes int[][] envelopes = { { 4, 3 }, { 5, 3 }, { 5, 6 }, { 1, 2 } }; // Function call System.out.println(maxEnvelopes(envelopes));}}// This code is contributed by offbeat |
Python3
# Python3 program for the above approach# Function that returns the maximum# number of envelopes that can be# inserted into another envelopesdef maxEnvelopes(envelopes): # Number of envelopes N = len(envelopes) if (N == 0): return N # Sort the envelopes in # non-decreasing order envelopes = sorted(envelopes) # Initialize dp[] array dp = [0] * N # To store the result max_envelope = 1 dp[0] = 1 # Loop through the array for i in range(1, N): dp[i] = 1 # Find envelopes count for # each envelope for j in range(i): if (envelopes[i][0] > envelopes[j][0] and envelopes[i][1] > envelopes[j][1] and dp[i] < dp[j] + 1): dp[i] = dp[j] + 1 # Store maximum envelopes count max_envelope = max(max_envelope, dp[i]) # Return the result return max_envelope# Driver Codeif __name__ == '__main__': # Given the envelopes envelopes = [ [ 4, 3 ], [ 5, 3 ], [ 5, 6 ], [ 1, 2 ] ] # Function Call print(maxEnvelopes(envelopes))# This code is contributed by Mohit Kumar |
C#
// C# program to implement above approachusing System;using System.Collections;using System.Collections.Generic;class GFG{ // Function that returns the maximum // number of envelopes that can be // inserted into another envelopes static int maxEnvelopes(int[][] envelopes) { // Number of envelopes int N = envelopes.Length; if (N == 0){ return N; } // Sort the envelopes in // non-decreasing order Array.Sort(envelopes, new comp()); // Initialize dp[] array int[] dp = new int[N]; // To store the result int max_envelope = 1; dp[0] = 1; // Loop through the array for(int i = 1 ; i < N ; ++i) { dp[i] = 1; // Find envelopes count for // each envelope for(int j = 0 ; j < i ; ++j) { if (envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1] && dp[i] < dp[j] + 1){ dp[i] = dp[j] + 1; } } // Store maximum envelopes count max_envelope = Math.Max(max_envelope, dp[i]); } // Return the result return max_envelope; } // Driver code public static void Main(string[] args){ // Given the envelopes int[][] envelopes = new int[][]{ new int[]{ 4, 3 }, new int[]{ 5, 3 }, new int[]{ 5, 6 }, new int[]{ 1, 2 } }; // Function call Console.WriteLine(maxEnvelopes(envelopes)); }}class comp : IComparer<int[]>{ public int Compare(int[] a, int[] b) { if(a[0] != b[0]) return a[0] - b[0]; return a[1] - b[1]; }}// This code is contributed by entertain2022. |
Javascript
<script>// JavaScript program for the above approach// Function that returns the maximum// number of envelopes that can be// inserted into another envelopesfunction maxEnvelopes(envelopes){ // Number of envelopes var N = envelopes.length; if (N == 0) return N; // Sort the envelopes in // non-decreasing order envelopes.sort(); // Initialize dp[] array var dp = Array(N); // To store the result var max_envelope = 1; dp[0] = 1; // Loop through the array for (var i = 1; i < N; ++i) { dp[i] = 1; // Find envelopes count for // each envelope for (var j = 0; j < i; ++j) { if (envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1] && dp[i] < dp[j] + 1) dp[i] = dp[j] + 1; } // Store maximum envelopes count max_envelope = Math.max(max_envelope, dp[i]); } // Return the result return max_envelope;}// Driver Code// Given the envelopesvar envelopes = [ [ 4, 3 ], [ 5, 3 ], [ 5, 6 ], [ 1, 2 ] ]; // Function Calldocument.write( maxEnvelopes(envelopes));</script> |
Output:
3
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach:To optimize the naive approach the idea is to use the concept of Binary Search and Longest Increasing Subsequence. Sorting the envelopes in the increasing order of width and the decreasing order of height if width is same, reduces the problem to finding the longest increasing sequence of height of the envelope. This approach works as width is already sorted in increasing order and only maximum increasing sequence of height is sufficient to find the maximum number of envelopes. The efficient way to find the Longest Increasing Sequence in N×log(N) approach is discussed in this article.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function that returns the maximum// number of envelopes that can be// inserted into another envelopesint maxEnvelopes(vector<vector<int> >& envelopes){ // Number of envelopes int N = envelopes.size(); if (N == 0) return N; // Sort the envelopes in increasing // order of width and decreasing order // of height is width is same sort(envelopes.begin(), envelopes.end(), [](vector<int>& a, vector<int>& b) { return a[0] < b[0] or (a[0] == b[0] and a[1] > b[1]); }); // To store the longest increasing // sequence of height vector<int> dp; // Finding LIS of the heights // of the envelopes for (int i = 0; i < N; ++i) { auto iter = lower_bound(dp.begin(), dp.end(), envelopes[i][1]); if (iter == dp.end()) dp.push_back(envelopes[i][1]); else if (envelopes[i][1] < *iter) *iter = envelopes[i][1]; } // Return the result return dp.size();}// Driver Codeint main(){ // Given the envelopes vector<vector<int> > envelopes = { { 4, 3 }, { 5, 3 }, { 5, 6 }, { 1, 2 } }; // Function Call cout << maxEnvelopes(envelopes); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;import java.util.Arrays;import java.util.Collections;class GFG{ // Function that returns the maximum // number of envelopes that can be // inserted into another envelopes static int maxEnvelopes(int[][] envelopes) { // Number of envelopes int N = envelopes.length; if (N == 0) return N; // Sort the envelopes in increasing // order of width and decreasing order // of height is width is same Arrays.sort(envelopes,new Comparator<int[]>() { @Override public int compare(int[] a, int[] b) { return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];; } }); // To store the longest increasing // sequence of height ArrayList<Integer> dp = new ArrayList<Integer>(); // Finding LIS of the heights // of the envelopes for (int i = 0; i < N; ++i) { int iter = Collections.binarySearch(dp, envelopes[i][1]); if (iter < 0) iter=Math.abs(iter)-1; if(iter == dp.size()) dp.add(envelopes[i][1]); else if (envelopes[i][1] < dp.get(iter)) dp.set(iter,envelopes[i][1]); } // Return the result return dp.size(); } // Driver Code public static void main (String[] args) { // Given the envelopes int[][] envelopes = { { 4, 3 }, { 5, 3 }, { 5, 6 }, { 1, 2 } }; // Function Call System.out.println(maxEnvelopes(envelopes)); }}// This code is contributed by Aman Kumar |
Python3
# Python program for the above approachfrom bisect import bisect_left as lower_bound# Function that returns the maximum# number of envelopes that can be# inserted into another envelopesdef maxEnvelopes(envelopes): # Number of envelopes N = len(envelopes) if(N == 0): return N # Sort the envelopes in increasing # order of width and decreasing order # of height is width is same envelopes.sort() # To store the longest increasing # sequence of height dp = [] # Finding LIS of the heights # of the envelopes for i in range(N): iter = lower_bound(dp,envelopes[i][1]) if(iter == len(dp)): dp.append(envelopes[i][1]) elif(envelopes[i][1] < dp[iter]): dp[iter] = envelopes[i][1] # Return the result return len(dp)# Driver Code# Given the envelopesenvelopes = [[4, 3], [5, 3], [5, 6], [1, 2]]# Function Callprint(maxEnvelopes(envelopes))# This code is contributed by Pushpesh Raj |
C#
using System;using System.Linq;using System.Collections.Generic;class GFG{ // Function that returns the maximum // number of envelopes that can be // inserted into another envelopes static int maxEnvelopes(int[][] envelopes) { // Number of envelopes int N = envelopes.Length; if (N == 0) return N; // Sort the envelopes in increasing // order of width and decreasing order // of height is width is same Array.Sort(envelopes, (a, b) = > a[0] - b[0]); // To store the longest increasing // sequence of height List<int> dp = new List<int>(); // Finding LIS of the heights // of the envelopes for (int i = 0; i < N; ++i) { int iter = dp.BinarySearch(envelopes[i][1]); if (iter < 0) iter = ~iter; if (iter == dp.Count) dp.Add(envelopes[i][1]); else if (envelopes[i][1] < dp[iter]) dp[iter] = envelopes[i][1]; } // Return the result return dp.Count; } // Driver Code static void Main(string[] args) { // Given the envelopes int[][] envelopes = new int[4][]; envelopes[0] = new int[] { 4, 3 }; envelopes[1] = new int[] { 5, 3 }; envelopes[2] = new int[] { 5, 6 }; envelopes[3] = new int[] { 1, 2 }; // Function Call Console.WriteLine(maxEnvelopes(envelopes)); }}// This code is contributed by lokeshpotta20. |
Javascript
// JavaScript program for the above approach// Function that returns the maximum// number of envelopes that can be// inserted into another envelopesfunction maxEnvelopes(envelopes) { // Number of envelopes let N = envelopes.length; if (N === 0) return N; // Sort the envelopes in increasing // order of width and decreasing order // of height is width is same envelopes.sort((a, b) => { if (a[0] === b[0]) { return b[1] - a[1]; } else { return a[0] - b[0]; } }); // To store the longest increasing // sequence of height let dp = []; // Finding LIS of the heights // of the envelopes for (let i = 0; i < N; i++) { let iter = dp.findIndex(x => x >= envelopes[i][1]); if (iter === -1) { dp.push(envelopes[i][1]); } else if (envelopes[i][1] < dp[iter]) { dp[iter] = envelopes[i][1]; } } // Return the result return dp.length;}// Driver Codelet envelopes = [[4, 3], [5, 3], [5, 6], [1, 2]];// Function Callconsole.log(maxEnvelopes(envelopes));// this contributed by devendra |
Output:
3
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
