Longest Increasing Subsequence | Patience Sorting | DP Concepts & Qns-17 | Leetcode 300
203Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
This is the 17th Video on our DP Concepts & Qns Playlist.
In this video we will try to solve a very DP LIS using Patience Sorting - Longest Increasing Subsequence (Leetcode 300).
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Longest Increasing Subsequence (Using Patience Sorting)
Company Tags : Microsoft
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/DP/LIS%20%26%20Variants/Longest%20Increasing%20Subsequence.cpp
Leetcode Link : https://leetcode.com/problems/longest-increasing-subsequence/
My DP Concepts Playlist : https://youtu.be/7eLMOE1jnls
My Graph Concepts Playlist : https://youtu.be/5JGiZnr6B5w
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Interview_DS_Algo
Subscribe to my channel : https://www.youtube.com/@codestorywithMIK
Instagram : https://www.instagram.com/codestorywithmik/
Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/
Twitter : https://twitter.com/CSwithMIK
Approach Summary : The provided C++ code implements the Longest Increasing Subsequence (LIS) problem using the Patience Sorting algorithm. The algorithm maintains a vector called sorted to keep track of the increasing subsequence. It iterates through the input vector nums, and for each element, it uses the lower_bound function to find the position where the current element can be inserted into the sorted vector while maintaining the increasing order. If the iterator returned by lower_bound points to the end of the sorted vector, it means the current element is greater than all existing elements, and it is added to the end. Otherwise, the element at the iterator position is replaced with the current element. Finally, the length of the resulting LIS is returned. This approach efficiently eliminates duplicates and builds the longest increasing subsequence in a single pass through the input vector.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #2024 #newyear