Russian Doll Envelopes
Updated
Problem statement
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[][]) → intExamples
Example 1
envelopes = [[3,5],[4,6],[2,8],[5,7],[6,9],[4,4]]return = 4Sort 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 <= 105envelopes[i].length == 21 <= 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 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)