MEDIUM NC#109 Blind #18 Dynamic Programming 1D
300. Longest Increasing Subsequence
š Problem
Given an integer array nums, return the length of the longest strictly increasing subsequence.
š§ Visual Learning Aid
1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases
JS/TS Refreshers
- ā¢Array methods (`push`, `pop`, `shift`, `slice`)
- ā¢Object/Map/Set usage patterns
- ā¢Function parameter and return typing
- ā¢Midpoint overflow-safe math
- ā¢Loop invariants
- ā¢Monotonic condition design
Logical Thinking Concepts
- ā¢Define invariants before coding
- ā¢Check edge cases first (`[]`, single element, duplicates)
- ā¢Estimate time/space before implementation
- ā¢Apply Binary Search reasoning pattern
- ā¢Apply Dynamic Programming reasoning pattern
š” Approach
- ā dp[i] = length of LIS ending at index i
- ā For each i, check all j < i where nums[j] < nums[i]
- ā dp[i] = max(dp[j] + 1) for all valid j
- ā Time: O(nĀ²), Space: O(n)
š§ Prerequisites
š ļø Hints & Pitfalls
Hints
- ā¢dp[i] = length of LIS ending at index i
- ā¢For each i, check all j < i where nums[j] < nums[i]
- ā¢dp[i] = max(dp[j] + 1) for all valid j
Common Pitfalls
- ā¢Time: O(nĀ²), Space: O(n)
š§Ŗ Test Cases
Hidden tests on submit: 1
Test Case 1
Not run Input:
lengthOfLIS([10,9,2,5,3,7,101,18]); Expected:
4 Test Case 2
Not run Input:
lengthOfLIS([0,1,0,3,2,3]); Expected:
4 Test Case 3
Not run Input:
lengthOfLIS([7,7,7,7,7,7]); Expected:
1 š Code Editor
š¤ Output