Flipkart SDE - 1 , Boxes within Boxes..
- Posted
- 2 Oct 2025
Summary
I encountered a 2D box nesting problem, similar to 'Russian Doll Envelopes', during my Flipkart SDE-1 interview, which required a specific sorting strategy followed by a Longest Increasing Subsequence approach.
How it went
During my interview at Flipkart for the SDE-1 role, I was presented with a problem involving N 2D boxes, each having a height (h) and a width (w). The rule was that one box could fit inside another if both its dimensions were strictly smaller (wi < wj and hi < hj). The goal was to find the longest nesting sequence of boxes. I immediately recognized this as a variation of the Longest Increasing Subsequence (LIS) problem but adapted for two dimensions. My approach involved a specific sorting strategy: first, sort all boxes by their width in ascending order. Crucially, if two boxes shared the same width, I sorted them by height in descending order. This clever trick prevents boxes of the same width from being considered for nesting when finding the LIS based on height. After this sort, the problem simplifies to finding the Longest Increasing Subsequence of the heights.
Questions asked (1)
- 01
Boxes within Boxes (2D Nesting Sequence)
Data Structures & Algorithms
Open the problemThere are N boxes which are 2D in shape. Each box has 2 dimensions, Height denoted by h and Width denoted by w. A box can fit inside another box if both the dimensions are strictly smaller. Mathematically, a box i can fit in box j if wi < wj and hi < hj. A nesting sequence of K length is defined as a sequence of indices p1, p2,….., pk for some integer k ≥ 1 such that pi denotes the element positions from the original array, and the sequence follows the following conditions: