The O(n) Club: Russian Doll Envelopes—How to Stuff Smarter, Not Harder

The O(n) Club: Russian Doll Envelopes—How to Stuff Smarter, Not Harder

⚡ TL;DR

Goal: Nest as many envelopes (each: width, height) as possible so each is strictly smaller in both dimensions. Don’t let the sorting fool you—if you mess up the order, your stack turns into a pancake pile. Get the sort right, then treat it like a Longest Increasing Subsequence (LIS) problem on heights. Here’s your quick Java cheat sheet:

// Make sure you sorted heights *descending* for ties!
int maxEnvelopes(int[][] env) {
    Arrays.sort(env, (a,b) -> a[0]==b[0] ? b[1]-a[1] : a[0]-b[0]);
    int[] h = Arrays.stream(env).mapToInt(e->e[1]).toArray();
    return lengthOfLIS(h);
}

🧠 How Devs Usually Mess This Up

Classic flubs: Sorting both width and height ascending—sure, if you want to accidentally stack envelopes of the same width because the sort lets them slip through. Or thinking you can rotate the envelopes—nope, not unless HR lets you rotate your chair 360° in a meeting and still get a raise. Also: forgetting to require BOTH width and height to be strictly increasing. One is not enough, folks.

🔍 What’s Actually Going On

This is like warehouse Tetris for people who skipped spatial reasoning day. Sorting width ascending and height descending for ties ensures you don’t get two envelopes with the same width sneaking into your perfect stack. After that, it’s just plain old LIS—find the biggest sequence of increasing heights. Visualize envelope stacking, but you’re only allowed to touch each once (and no, you can’t rotate them or use a shrink ray).

🛠️ PseudoCode

• Sort: width ASC, height DESC for equal widths:
  

  Arrays.sort(env, (a, b) -> {
    if (a[0] == b[0]) return b[1] - a[1];
    return a[0] - b[0];
  });

  Prevents same-width envelopes from forming a conga line in your answer.
• Extract heights:
  

  int[] hts = Arrays.stream(env).mapToInt(e -> e[1]).toArray();

  Now you’ve reduced your pain to a 1D problem: LIS.
• Find LIS: patience sorting variant with binary search:
  

  List<Integer> piles = new ArrayList<>();
  for (int h : hts) {
      int idx = Collections.binarySearch(piles, h);
      if (idx < 0) idx = -(idx + 1);
      if (idx == piles.size()) piles.add(h);
      else piles.set(idx, h);
  }

  The length of piles is your answer.

💻 The Code

// LeetCode 354 Java solution
import java.util.*;
 public class RussianDollEnvelopes {
    public int maxEnvelopes(int[][] envelopes) {
        if (envelopes == null || envelopes.length == 0) return 0;
        Arrays.sort(envelopes, (a, b) -> a[0]==b[0] ? b[1]-a[1] : a[0]-b[0]);
        int[] heights = new int[envelopes.length];
        for (int i = 0; i < envelopes.length; i++) heights[i] = envelopes[i][1];
        List
<integer> piles = new ArrayList<>();
        for (int h : heights) {
            int idx = Collections.binarySearch(piles, h);
            if (idx < 0) idx = -(idx + 1);
            if (idx == piles.size()) piles.add(h);
            else piles.set(idx, h);
        }
        return piles.size();
    }
}
</integer>

⚠️ Pitfalls, Traps & Runtime Smacks

• Sorting both height and width ascending = 💥 logic bomb if widths match
• Rotations = instant fail (no spinning for extra points)
• Edge checks: Empty input = 0, single envelope = 1, clones = 1 (not a nesting party!)
• Both width & height MUST strictly increase. No awkward side-by-side fits.
• DP brute force: Works for tiny tests, but will fry your CPU when n gets big (O(n^2)). Use LIS O(n log n) for a cool, calm stack trace.

🧠 Interviewer Brain-Tattoo

If your envelopes form a never-ending stack, check your sort: in the real world, only matryoshka dolls are allowed to break physics.