The O(n) Club: Longest Increasing Subsequence: Why Non-Contiguous Is Suddenly Cool

The O(n) Club: Longest Increasing Subsequence — Why Non-Contiguous Is Suddenly Cool

⚡ TL;DR

You want the longest strictly increasing subsequence in an array, not a subarray (fancy coder-speak for: you can skip as many items as you want, as long as you never go backwards). Brute force will short-circuit your brain, so use DP for O(n²) or be a speed demon and use binary search for O(n log n). Here’s the DP in Java:

// Java DP
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 0; i < n; i++) {
  for (int j = 0; j < i; j++) {
    if (nums[j] < nums[i]) {
      dp[i] = Math.max(dp[i], dp[j] + 1);
    }
  }
}
int lis = Arrays.stream(dp).max().getAsInt();

🧠 How Devs Usually Mess This Up

Step 1: Assume ‘increasing’ means ‘contiguous.’ Step 2: Wonder why [2,3,7] is accepted but [3,7,101] from scattered spots is too.
Other honorable mentions:

• Confusing subarray (must be stuck together) versus subsequence (skip until you drop).
• Going full greedy: “I’ll pick every next bigger number!” (Spoiler: Try that on [10,9,2,5,3,7,101,18] and enjoy your 2.)
• Thinking the problem wants the sequence, not just its length. That’s a crueler interview for another day.

🔍 What’s Actually Going On

This problem is less about loyalty and more about hoping you can upgrade later. Imagine you’re stacking clean coffee mugs in order of shininess—sometimes skipping a less shiny mug to get an even shiner one. At every step, either extend a previous best or launch a new, hopeful sequence sulking off from the first coffee spill.
Dynamic Programming (the classic): For each mug (number), figure out if you can join any shine-ier stack ending with a smaller mug. It’s like company promotions, but fair.
Binary Search/Patience Sorting: Maintain a skyline of the best possible endings for each sequence length so far. Replace as soon as you can—like Tinder for arrays.

🛠️ PseudoCode

• Classic DP Approach:
  • Start by creating a dp array of 1s (because one number is, technically, a sequence).
  • Loop through all indices i. For every earlier index j < i:
    • if nums[i] > nums[j], consider extending that sequence (dp[i] = Math.max(dp[i], dp[j]+1))
  • Answer: The biggest dp value you find at the end.

  // Java
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

💻 The Code

// O(n log n) LIS in Java
public int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;
    for (int x : nums) {
        int i = Arrays.binarySearch(tails, 0, size, x);
        if (i < 0) i = -(i + 1);
        tails[i] = x;
        if (i == size) size++;
    }
    return size;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Duplicates? Still strictly increasing. [2,2]: That second 2 gets ghosted.
• Empty state? If nums is empty, just return zero and call it a day.
• Subsequence not subarray! You can—and often should—skip numbers for a bigger chain.
• Time Complexity Drama: DP is O(n²), binary search is O(n log n). Know both, wield one.

🧠 Interviewer Brain-Tattoo

“If you can skip ahead and your answer gets longer, you’ve found a subsequence. If not, it’s probably a subarray—and you’re probably stuck.”