Leetcode 300 - Longest Increasing Subsequence
Advance your Tech Career to new heights with Personalized Coaching from industry Experts at top companies.
Understanding the problem
The problem statement on LeetCode reads as follows:
Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].
Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Example 2:
Input: nums = [0,1,0,3,2,3]
Output: 4
Explanation: The longest increasing subsequence is [0,1,3,5], therefore the length is 4.
Plan your solution
One way to solve this problem is to use dynamic programming. We can create a table dp
where dp[i]
represents the length of the longest increasing subsequence ending at index i
in the input array. Then, we can iterate through the input array and for each element, we can check the previous elements and update the dp
table accordingly. Specifically, for each element nums[i]
, we can set dp[i]
to be the maximum of dp[j] + 1
for all j
such that j < i
and nums[j] < nums[i]
. Finally, we can return the maximum value in the dp
table.
Implement your solution
Now that we have a plan, let’s implement it in Python.
class Solution:
def lengthOfLIS(self, nums):
# Edge case: if the array is empty, return 0
if not nums:
return 0
# Initialize the dp table with all 1s
dp = [1] * len(nums)
# Iterate through the array
for i in range(1, len(nums)):
# Iterate through the previous elements
for j in range(i):
# If the current element is greater than the previous element, update the dp table
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
# Return the maximum value in the dp table
return max(dp)
Test your solution
Testing is an important step in the software development process, as it helps ensure that your code is correct and works as intended. In the case of the “Longest Increasing Subsequence” problem, we can test our solution by running a series of test cases that cover different scenarios and edge cases.
For example, we can test our solution with an array that is sorted in increasing order, an array that is sorted in decreasing order, an array that has all the same elements, and an array that has no increasing subsequences. We can also test our solution with arrays of different lengths and with different types of elements (e.g. integers, strings, etc.). By running a variety of test cases, we can gain confidence that our solution is correct and will work for all inputs.
Advance your Tech Career to new heights with Personalized Coaching from industry Experts at top companies.
Related:
Related Posts
- Leetcode 424 - Longest Repeating Character Replacement
- Two Sum and Its Variants
- How do you guys get good at DP?
- Leetcode 1004 - Max Consecutive Ones III
- Leetcode 222 - Count Complete Tree Nodes
- Leetcode 1027 - Longest Arithmetic Subsequence
- Question 1299 on leetcode
- Leetcode 240 - Search a 2D Matrix II
- Leetcode 1351 - Count Negative Numbers in a Sorted Matrix
- Leetcode 239 - Sliding Window Maximum
- Leetcode 209 - Minimum Size Subarray Sum
- LeetCode 230 - Kth Smallest Element in a BST with Code
- advanced-applications-of-binary-search
- Leetcode 96 - Unique Binary Search Trees
- Leetcode 540 - Single Element in a Sorted Array
- Leetcode 1283 - Find the Smallest Divisor Given a Threshold
- Leetcode 74 - Search a 2D Matrix
- Leetcode 930 - Binary Subarrays With Sum
- Blazingly fast solution to LeetCode #1342 - Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold (Cross-post from r/SoftwareEngineering)
- Leetcode 704 - Binary Search
- Leetcode 643 - Maximum Average Subarray I
- LeetCode - Two Sum Solution with Code
- a-binary-search-template
- Leetcode 1358 - Number of Substrings Containing All Three Characters
- Leetcode 33 - Search in Rotated Sorted Array
- Leetcode 1151 - Minimum Swaps to Group All 1’s Together