← PayPal questions
CodingModerate

Longest Increasing Subsequence (LIS)

Filed under PayPal · Also reported at OLX

Free read 1 of 3

Confirm 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

  1. Confirm if elements need to be strictly increasing and if duplicates count.

Solution

O(n log n) time, O(n) space

Python
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.