Maximum Number of Envelopes That Can be Put inside other bigger envelopes

Last Updated : 14 Mar, 2026

Given N 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 smaller 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})

Table of Content

Naive Approach - O(N²) Time and O(N) Space

The idea is to treat this problem like the Longest Increasing Subsequence (LIS) problem. First, sort envelopes by increasing width. If widths are equal, sort by decreasing height. Then, for each envelope, check how many smaller envelopes can fit inside it.

Steps:

  • Sort the array in non-decreasing order of width and if width is same, then consider height.
  • Initialize a dp[] array, where dp[i] stores the maximum number of envelopes that can be nested with envelope[i] as the largest envelope.
  • For each envelope[i], loop through all envelopes before it. If the width and height of a previous envelope are both smaller, update dp[i] = max(dp[i], dp[j] + 1).
  • The maximum value in dp[] gives the maximum number of envelopes that can be nested.
C++ 
//Driver Code Starts
using namespace std;

// Function that returns the maximum
// number of envelopes that can be
// inserted into another envelopes
//Driver Code Ends

int maxenvelopes(vector<vector<int>>& envelopes)
{
    // Number of envelopes
    int n = envelopes.size();

    if (n == 0)
        return 0;

    // Sort the envelopes in
    // non-decreasing order
    sort(envelopes.begin(), envelopes.end(),
         [](vector<int>& a, vector<int>& b) {
             if(a[0] != b[0]) return a[0] < b[0];
             return a[1] < b[1];
         });

    // Initialize dp[] array
    vector<int> dp(n, 1);

    // To store the result
    int max_envelope = 1;

    // Loop through the array
    for(int i = 1; i < n; ++i)
    {
        // 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] = max(dp[i], dp[j] + 1);
            }
        }
        max_envelope = max(max_envelope, dp[i]);
    }

    return max_envelope;
}


//Driver Code Starts
int main()
{
    // Given the envelopes
    vector<vector<int>> envelopes = {{4,3},{5,3},{5,6},{1,2}};

    // Function call
    cout << maxenvelopes(envelopes);
    return 0;
}
//Driver Code Ends
Java 
//Driver Code Starts
import java.util.Arrays;
// Function that returns the maximum
// number of envelopes that can be
// inserted into another envelopes
class GFG {

//Driver Code Ends

    static int maxenvelopes(int[][] envelopes)
    {
        // Number of envelopes
        int n = envelopes.length;

        if (n == 0)
            return 0;

        // Sort the envelopes in
        // non-decreasing order
        Arrays.sort(envelopes, (a, b) -> {
            if (a[0] != b[0])
                return a[0] - b[0];
            return a[1] - b[1];
        });

        // Initialize dp[] array
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        // To store the result
        int max_envelope = 1;

        // Loop through the array
        for (int i = 1; i < n; ++i) {
            // 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] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max_envelope = Math.max(max_envelope, dp[i]);
        }

        return max_envelope;
    }

//Driver Code Starts

    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));
    }
}
//Driver Code Ends
Python 
#Driver Code Starts
# Function that returns the maximum
# number of envelopes that can be
# inserted into another envelopes
#Driver Code Ends

def maxenvelopes(envelopes):
    # Number of envelopes
    n = len(envelopes)

    if n == 0:
        return 0

    # Sort the envelopes in
    # non-decreasing order
    envelopes.sort(key=lambda x: (x[0], x[1]))

    # Initialize dp[] array
    dp = [1] * n

    # To store the result
    max_envelope = 1

    # Loop through the array
    for i in range(1, n):
        # 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]:
                dp[i] = max(dp[i], dp[j] + 1)
        max_envelope = max(max_envelope, dp[i])

    return max_envelope


#Driver Code Starts
if __name__ == "__main__":
    # Given the envelopes
    envelopes = [[4,3],[5,3],[5,6],[1,2]]

    # Function call
    print(maxenvelopes(envelopes))
#Driver Code Ends
C# 
//Driver Code Starts
using System;
using System.Collections.Generic;

// Function that returns the maximum
// number of envelopes that can be
// inserted into another envelopes
class GFG {

//Driver Code Ends

    static int maxenvelopes(int[,] envelopes) {
        // Number of envelopes
        int n = envelopes.GetLength(0);

        if(n == 0) return 0;

        // Convert 2D array to list for sorting
        List<int[]> envList = new List<int[]>();
        for(int i = 0; i < n; i++)
            envList.Add(new int[]{envelopes[i,0], envelopes[i,1]});

        // Sort the envelopes in non-decreasing order
        envList.Sort((a,b) => {
            if(a[0] != b[0]) return a[0] - b[0];
            return a[1] - b[1];
        });

        // Initialize dp[] array
        int[] dp = new int[n];
        for(int i = 0; i < n; i++) dp[i] = 1;

        // To store the result
        int max_envelope = 1;

        // Loop through the array
        for(int i = 1; i < n; i++) {
            // Find envelopes count for each envelope
            for(int j = 0; j < i; j++) {
                if(envList[i][0] > envList[j][0] &&
                   envList[i][1] > envList[j][1]) {
                    dp[i] = Math.Max(dp[i], dp[j]+1);
                }
            }
            max_envelope = Math.Max(max_envelope, dp[i]);
        }

        return max_envelope;
    }


//Driver Code Starts
    static void Main() {
        // Given the envelopes
        int[,] envelopes = new int[,] { {4,3},{5,3},{5,6},{1,2} };

        // Function call
        Console.WriteLine(maxenvelopes(envelopes));
    }
}
//Driver Code Ends
JavaScript 
//Driver Code Starts
// Function that returns the maximum
// number of envelopes that can be
// inserted into another envelopes
//Driver Code Ends

function maxenvelopes(envelopes)
{
    // Number of envelopes
    let n = envelopes.length;

    if (n === 0)
        return 0;

    // Sort the envelopes in
    // non-decreasing order
    envelopes.sort((a, b) => {
        if (a[0] !== b[0])
            return a[0] - b[0];
        return a[1] - b[1];
    });

    // Initialize dp[] array
    let dp = new Array(n).fill(1);

    // To store the result
    let max_envelope = 1;

    // Loop through the array
    for (let i = 1; i < n; i++) {
        // Find envelopes count for
        // each envelope
        for (let j = 0; j < i; j++) {
            if (envelopes[i][0] > envelopes[j][0]
                && envelopes[i][1] > envelopes[j][1]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        max_envelope = Math.max(max_envelope, dp[i]);
    }

    return max_envelope;
}

//Driver Code Starts

const envelopes =
    [ [ 4, 3 ], [ 5, 3 ], [ 5, 6 ], [ 1, 2 ] ];

// Function call
console.log(maxenvelopes(envelopes));
//Driver Code Ends

Output
3

Efficient Approach - O(N log N) Time and O(N) Space

To optimize the naive approach the idea is to use the concept of Binary Search and Longest Increasing Subsequence. First, sort envelopes by increasing width. If widths are equal, sort by decreasing height. Then, the problem reduces to finding the longest increasing sequence of heights

C++ 
using namespace std;

// Function that returns the maximum
// number of envelopes that can be
// inserted into another envelopes
int 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 dp.size();
}

int main()
{
    // Given the envelopes
    vector<vector<int>> envelopes = {{4, 3}, {5, 3}, {5, 6}, {1, 2}};

    // Function Call
    cout << maxEnvelopes(envelopes);
    return 0;
}
Java 
//Driver Code Starts
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

class GFG {

    // Function that returns the maximum
    // number of envelopes that can be
    // inserted into another envelopes
//Driver Code Ends

    static int maxEnvelopes(int[][] envelopes) {

        // Number of envelopes
        int N = envelopes.length;
        if (N == 0)
            return 0;

        // Sort the envelopes in increasing
        // order of width and decreasing order
        // of height if 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<>();

        // Finding LIS of the heights
        // of the envelopes
        for (int i = 0; i < N; i++) {
            int idx = Collections.binarySearch(dp, envelopes[i][1]);
            if (idx < 0)
                idx = -idx - 1;

            if (idx == dp.size())
                dp.add(envelopes[i][1]);
            else
                dp.set(idx, envelopes[i][1]);
        }

        return dp.size();
    }


//Driver Code Starts
    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));
    }
}

// Output: 3
//Driver Code Ends
Python 
#Driver Code Starts
from bisect import bisect_left

# Function that returns the maximum
# number of envelopes that can be
# inserted into another envelope
#Driver Code Ends

def max_envelopes(envelopes):
    # Number of envelopes
    n = len(envelopes)
    if n == 0:
        return 0

    # Sort envelopes by increasing width
    # and decreasing height if widths are same
    envelopes.sort(key=lambda x: (x[0], -x[1]))

    # To store the longest increasing sequence of heights
    dp = []

    # Finding LIS of the heights of the envelopes
    for _, height in envelopes:
        idx = bisect_left(dp, height)
        if idx == len(dp):
            dp.append(height)
        else:
            dp[idx] = height

    return len(dp)

#Driver Code Starts

if __name__ == "__main__":
    # Given the envelopes
    envelopes = [[4, 3], [5, 3], [5, 6], [1, 2]]

    # Function Call
    print(max_envelopes(envelopes))

#Driver Code Ends
C# 
//Driver Code Starts
using System;
using System.Collections.Generic;

class GFG {
    // Function that returns the maximum
    // number of envelopes that can be
    // inserted into another envelopes
//Driver Code Ends

    static int maxEnvelopes(int[][] envelopes)
    {
        // Number of envelopes
        int n = envelopes.Length;

        if (n == 0)
            return 0;

        // Sort the envelopes in increasing
        // order of width and decreasing order
        // of height if width is same
        Array.Sort(envelopes, (a, b) = > {
            if (a[0] != b[0])
                return a[0] - b[0];
            return b[1] - a[1];
        });

        // 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 height = envelopes[i][1];
            int idx = dp.BinarySearch(height);

            if (idx < 0)
                idx = ~idx;

            if (idx == dp.Count)
                dp.Add(height);
            else
                dp[idx] = height;
        }

        return dp.Count;
    }


//Driver Code Starts
    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));
    }
}
//Driver Code Ends
JavaScript 
//Driver Code Starts
// Function that returns the maximum
// number of envelopes that can be
// inserted into another envelopes
//Driver Code Ends

function 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 dp.length;
}


//Driver Code Starts
// Driver Code
let envelopes = [[4, 3], [5, 3], [5, 6], [1, 2]];

// Function Call
console.log(maxEnvelopes(envelopes));
// this contributed by devendra
//Driver Code Ends

Output
3
Comment

Explore