Maximum Number of Points with Cost | Detailed Explanation | Leetcode 1937 | codestorywithMIK
595Whatsapp Community Link : https://www.whatsapp.com/channel/0029...
This is the 98th Video of our Playlist "Dynamic Programming : Popular Interview Problems" by codestorywithMIK
Minimum Falling Path Sum - • Minimum Falling Path Sum | Recursion ...
In this video we will try to solve a very good 2D - DP problem : Maximum Number of Points with Cost | Detailed Explanation | Leetcode 1937 | codestorywithMIK
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 : Maximum Number of Points with Cost | Detailed Explanation | Leetcode 1937 | codestorywithMIK
Company Tags : will update soon
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Intervie...
Leetcode Link : https://leetcode.com/problems/maximum...
My DP Concepts Playlist : • Roadmap for DP | How to Start DP ? | ...
My Graph Concepts Playlist : • Graph Concepts & Qns - 1 : Graph will...
My Recursion Concepts Playlist : • Introduction | Recursion Concepts And...
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Intervie...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
Approach 1:
Concept: This approach is inspired by the problem "Minimum Falling Path Sum" (LeetCode 931), where we compute the maximum points achievable in a grid by adding values from the previous row with certain constraints.
Time Complexity: O(m×n×n), where m is the number of rows and n is the number of columns.
Space Complexity: O(n), which is used to store the previous row's maximum values.
Details:
For each row, the algorithm checks every possible column from the previous row to calculate the maximum points for the current cell.
This involves iterating through all pairs of columns, leading to a time complexity that is quadratic with respect to the number of columns, resulting in a time limit exceeded (TLE) error for large inputs.
Approach 2:
Concept: This approach optimizes the first approach by calculating the best possible previous column values more efficiently, thus reducing the time complexity.
Time Complexity: O(m×n).
Space Complexity: O(n).
Details:
Instead of iterating over all previous columns to find the maximum value for the current cell, the algorithm uses two auxiliary arrays (left and right) to keep track of the best possible values from the left and right directions in the previous row.
These arrays allow the algorithm to quickly determine the maximum points that can be achieved for each cell by considering the best previous column values without needing a nested loop.
This optimization brings the time complexity down to linear with respect to the number of columns, making it efficient enough to avoid a TLE.
✨ 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 #newyear2024