beingsde
Sign In
Back to all DSA patterns
Dynamic Programming•Pattern: DP / Binary Search•Medium

Longest increasing subsequence (LIS)

Problem Intuition & Objective

Find the length of the longest strictly increasing subsequence.

Time ComplexityO(n log n)
Optimal
Space ComplexityO(n)
Memory Bounds
Optimal Algorithmic Approach

Patience sorting with binary search for O(n log n).

Core Invariants & Edge Cases

  • DP: dp[i] = max length ending at index i; O(n²)
  • Binary search + patience sorting: maintain a 'tails' array; O(n log n)
  • Tails[i] = smallest tail element of all IS of length i+1
Previous ProblemSort colors (Dutch National Flag)Next Problem Coin change — minimum coins to make amount

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.