CodingModerate
Longest Increasing Subsequence (LIS)
Filed under PayPal · Also reported at OLX
Free read 1 of 3Confirm if elements need to be strictly increasing and if duplicates count.
The question
Given an integer array nums, return the length of the longest strictly increasing subsequence.
Constraints
- 1 <= nums.length <= 2500
- -10^4 <= nums[i] <= 10^4
Examples
- Input
- nums = [10,9,2,5,3,7,101,18]
- Output
- 4
- Why
- The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4.
Approach
Confirm if elements need to be strictly increasing and if duplicates count.
Generate all subsequences and check which ones are increasing. O(2^n) time complexity.
Use binary search with patience sorting (bisect) for O(n log n) time, or standard DP for O(n^2).
Array of length 1 or all identical elements.
Solution
O(n log n) time, O(n) space
import bisect
def lengthOfLIS(nums):
sub = []
for num in nums:
idx = bisect.bisect_left(sub, num)
if idx == len(sub):
sub.append(num)
else:
sub[idx] = num
return len(sub)
Tips
- What they are testing: Test with strictly decreasing arrays, all identical elements, and already sorted arrays.
- Common mistake: Confusing subsequence (not necessarily contiguous) with substring/subarray (contiguous).
Related PayPal questions
Collected from public candidate posts and coding forums. Updated Nov 2026.