FastPrepRussian Doll Envelopes
Problems/Russian Doll Envelopes

Russian Doll Envelopes

Airbnb logoAirbnb● HardINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in an Airbnb software engineer intern onsite coding round in India in 2022. The candidate was asked for the most envelopes that can be nested inside each other. They wrote an O(n^2) solution and had to make it pass two test cases from the interviewer. The interviewer then asked for an O(n log n) solution.

The report only names the problem. The limits follow the well-known version of this problem, and the examples are our own.

Our version is about 95% the same as the reported question.

You are given a list of envelopes. envelopes[i] = [w, h] means envelope i has width w and height h.

One envelope fits inside another only when it is strictly smaller in both width and height. You cannot turn an envelope to swap its width and height.

Return the largest number of envelopes you can put one inside another, like Russian dolls.

Function

maxEnvelopes(envelopes: int[][]) → int

Examples

Example 1

envelopes = [[3,5],[4,6],[2,8],[5,7],[6,9],[4,4]]return = 4

Sort by width: [2,8], [3,5], [4,4], [4,6], [5,7], [6,9]. The chain [3,5] inside [4,6] inside [5,7] inside [6,9] works, because both the width and the height go up at every step. That is 4 envelopes.

A chain of 5 would need five different widths, so it would have to use [2,8]. The only envelope that can hold [2,8] is [6,9], because every other one has height at most 7. So a chain with [2,8] has at most 2 envelopes, and the answer is 4.

Example 2

envelopes = [[1,1],[2,3],[2,2],[3,3],[4,1]]return = 3

[1,1] fits inside [2,2], which fits inside [3,3], so 3 envelopes work.

[2,2] and [2,3] have the same width, so neither fits inside the other. [2,3] does not fit inside [3,3] either, because the heights are equal. [4,1] is too short to hold anything. No chain of 4 exists, so the answer is 3.

Example 3

envelopes = [[4,6],[5,3]]return = 1

[4,6] is narrower than [5,3] but taller, so neither fits inside the other. Turning [5,3] into [3,5] would let it fit, but envelopes cannot be turned. Only one envelope can be used, so the answer is 1.

Constraints

  • 1 <= envelopes.length <= 105
  • envelopes[i].length == 2
  • 1 <= w, h <= 105

More Airbnb interview questions

  • Shortest Uncommon SubstringONSITE INTERVIEW · Seen Nov 2026
  • Print Sentences as TablePHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
  • Superhost EligibilityONSITE INTERVIEW · Seen Sep 2026
  • Call History ManagerONSITE INTERVIEW · Seen Sep 2022
  • All O(1) Data StructureONSITE INTERVIEW · Seen Jul 2022
  • Cheapest Flight with Its PathOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Apr 2022
  • Alien DictionaryPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2019
  • Task Management SystemOA · Seen Nov 2026
  • Recipe Management SystemOA · Seen Nov 2026
  • Progressive Banking SystemOA · Seen Nov 2026

Similar questions at other companies

  • Russian Doll EnvelopesGoogle · ONSITE INTERVIEWGoogle interview questions
  • Russian Doll EnvelopesInMobi · ONSITE INTERVIEWInMobi interview questions
  • Maximum Total Length of Non-Overlapping IntervalsBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
  • Maximum Profit in Job SchedulingAmazon · PHONE SCREEN
  • Fill a Time Window with SongsMicrosoft · OAMicrosoft interview questions
  • Maximum Taxi EarningsWells Fargo · OAWells Fargo interview questions
  • Count Later Lower ReadingsRippling · ONSITE INTERVIEWRippling interview questions
  • Minimum Total Waiting Time for One ElevatorExpedia · ONSITE INTERVIEWExpedia interview questions
  • 3Sum SmallerSalesforce · ONSITE INTERVIEWSalesforce interview questions
  • Minimum Removals for a Nice ArrayAdobe · ONSITE INTERVIEWAdobe interview questions

Interview reports that mention this question

  • Airbnb Intern OA and Onsite Rounds: 16 Experiences (Part 5 of 7)

Airbnb interview experiences

  • Airbnb SWE OA: Four-Level Banking System: 1 Experience
  • Airbnb Campus and Full-Time SWE OA / Interviews: 9 Experiences
  • Airbnb Intern Phone Interviews: 21 Experiences (Part 7 of 7)
  • Airbnb Intern OA and Phone Screens: 17 Experiences (Part 6 of 7)
  • Airbnb Intern OA, Diplomacy Game: 19 Experiences (Part 4 of 7)
All Airbnb interview questionsSee Airbnb hiring insights
Saved
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
      // Write your code here.
    }
}
Checking account…