Find the Maximum Length of Valid Subsequence | Part I | Part II | Leetcode 3201 | 3202 | MIK
588Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
Hi Everyone, this is the 115th video of our Playlist "Dynamic Programming : Popular Interview Problems".
Now we will be solving a very good DP Problem based on grid DP - Find the Maximum Length of Valid Subsequence | Part I | Part II | Detailed | Leetcode 3201 | 3202 | codestorywithMIK
I will explain it in full detail so that it becomes easy to understand. Each line will be explained and you will know the WHY behind everything.
We will solve using Recursion, then we will memoize it, then we will do bottom up and ultimately optimize bottom up.
Problem Name : Find the Maximum Length of Valid Subsequence | Part I | Part II | Detailed | Leetcode 3201 | 3202 | codestorywithMIK
Company Tags : will update later
Code Github(C++ & JAVA) -
Code of Leetcode 3201 - https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/DP/LIS & Variants/Find the Maximum Length of Valid Subsequence I.cpp
Code of Leetcode 3202 - https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/DP/LIS & Variants/Find the Maximum Length of Valid Subsequence II.cpp
Leetcode Link of Leetcode 3201 - https://leetcode.com/problems/find-the-maximum-length-of-valid-subsequence-i
Leetcode Link of Leetcode 3202 - https://leetcode.com/problems/find-the-maximum-length-of-valid-subsequence-ii
My DP Concepts Playlist : • Roadmap for DP | How to Start DP ? | Topic...
My Graph Concepts Playlist : • Graph Concepts & Qns - 1 : Graph will no m...
My Segment Tree Concepts Playlist : • Segment Tree | Introduction | Basics | Bui...
My Recursion Concepts Playlist : • Introduction | Recursion Concepts And Ques...
Trie Playlist - • Word Search II (Google, Amazon, Meta, Micr...
Difference Array Technique: Concepts & Qns : • Introduction | What | How | Difference Arr...
Monotonic Data Structure Concepts & Qns : • Monotonic Data Structures Concepts & Qns
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Interview_DS_Algo
Instagram : https://www.instagram.com/codestorywithmik/
Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/
Twitter : https://twitter.com/CSwithMIK
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Video Summary :
First approach (Recursive):
This approach uses a recursive function LIS to explore including or excluding elements while forming a subsequence. It tracks the previous chosen index and ensures that the sum of the previous and current element modulo 2 matches the desired parity (mod). By trying both parity cases (mod 0 and 1), it returns the length of the longest valid subsequence. Although simple to understand, this approach may have exponential time complexity without memoization.
Second approach (Bottom-up DP):
This method uses a dynamic programming table dp with two rows, each representing subsequences where sums modulo 2 equal 0 or 1 respectively. It iteratively builds the longest subsequence by comparing current and previous elements, updating the dp values accordingly. This bottom-up solution efficiently computes the longest subsequence length with a time complexity of O(n²), improving over the recursive method by avoiding repeated computations.
✨ Timelines✨
00:00 Introduction
00:22 Motivation
01:04 Problem Explanation Leetcode 3201
02:16 Thought Process - Why LIS Variant?
04:33 Tree Diagram for Recursion
14:51 Coding Recursion Approach
19:27 Recap LIS Bottom Up
22:28 Bottom Up Dry Run of this problem
29:25 Story To Code from LIS to This Problem
33:30 Coding Bottom Up
37:10 Improving Bottom Up Code
42:30 Leetcode 3202 using same LIS code
#MIK #mik #Mik
#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 #coding #programming #100daysofcode #developers #techjobs #datastructures #algorithms #webdevelopment #softwareengineering #computerscience #pythoncoding #codinglife #coderlife #javascript #datascience #leetcode #leetcodesolutions #leetcodedailychallenge #codinginterview #interviewprep #technicalinterview #interviewtips #interviewquestions #codingchallenges #interviewready