This content originally appeared on DEV Community and was authored by DEV Community
Intro: I am a former accountant turned software engineer graduated from coding bootcamp in January 2022. Algorithms and Data Structure is an unavoidable part of interviews for most of the tech companies now. And one of my friends told me that you need to solve a medium leetcode problem under 60 seconds in order to get into the top tech companies.So I thought I'd start learning how to do it while job searching.
Since I have no clue on how to solve any of the problems (even the easy ones), I thought there is no point for me to waste hours and can't get it figured out. Here is my approach:
- Pick a leetcode problem randomly or Online Assessment from targeted companies.
- Study 1-2 solutions from Youtube or LeetCode discussion section. One brute force solution, another one more optimal.
- Write a blog post with detailed explanation and do a verbal walk through to help understand the solutions better.
- Code out the solution in LeetCode without looking at the solutions
- Combat the forgetting curve: Re-do the question for the next three days. And come back regularly to revisit the problem.
740. Delete and Earn
Difficulty: Medium Language: JavaScript
You are given an integer array nums. You want to maximize the number of points you get by performing the following operation any number of times:
Pick any nums[i] and delete it to earn nums[i] points. Afterwards, you must delete every element equal to nums[i] - 1 and every element equal to nums[i] + 1.
Return the maximum number of points you can earn by applying the above operation some number of times.
Example 1:
Input: nums = [3,4,2]
Output: 6
Explanation: You can perform the following operations:
- Delete 4 to earn 4 points. Consequently, 3 is also deleted.
nums = [2].
- Delete 2 to earn 2 points. nums = [].
You earn a total of 6 points.
Example 2:
Input: nums = [2,2,3,3,3,4]
Output: 9
Explanation: You can perform the following operations:
- Delete a 3 to earn 3 points. All 2's and 4's are also deleted.
nums = [3,3].
- Delete a 3 again to earn 3 points. nums = [3].
- Delete a 3 once more to earn 3 points. nums = [].
You earn a total of 9 points.
Constraints:
1 <= nums.length <= 2 * 1041 <= nums[i] <= 104
Solution (Dynamic Programming DP):
Key to solve this problem with dynamic programming is to store in DP the maximum points earned at a position. Make element in the array in ascending order so that last element in the DP is the max points earned.
var deleteAndEarn = function(nums) {
const n = Math.max(...nums) + 1;
//find the greatest number in 'nums' (note 1)
const counts = new Array(n).fill(0);
//create a 'counts' array filled with 0 (note 2). An index of a
//element represents a number in array 'nums'. Each value of the
//element indicates the count for number that appears in 'nums'
//array. For example, if 'counts' array is [0,4,2,5], that means
//there are four '1' and two '2' and five '3' in 'nums' array.
for (const num of nums) counts[num]++;
//Loop (note 4) though array 'nums', increase value of element in
//'counts' by 1 at index 'num'.
const dp = new Array(n).fill(0);
//create a 'dp' array filled with 0 (note 2). This will be used to
//store the max points earned at index i
dp[1] = counts[1];
for (let i = 2; i < n; i++) {
//Loop through (note 5) 'counts' array
const points = counts[i] * i;
//calculate the poins earned by multiplying the index that
//represent the number and the count of that number.
dp[i] = Math.max(dp[i - 2] + points, dp[i - 1]);
//Max is either the [i - 1] or [i] + [i - 2] since we have to
//delete the immediate number before/after the number we took
}
return dp[n - 1];
//since dp is used to store max points earned in ascending order,
//the last element of dp is the max point can be earned in array
//'nums'.
}
Solution Submission detail as of 3/1/2022
(Data below could vary since there are new tests/submissions daily)
- Runtime: 72 ms
- Memory Usage: 44.5 mb
References:
LeetCode Problem Link
LeetCode Discussion: quadcoders
LeetCode Discussion: Deadication
Note 1: Math.max()
Note 2: Array.prototype.fill()
Note 3: Increasement(++)
Note 4: for...of loop
Note 5; for loop
Blog Cover Image Credit
This content originally appeared on DEV Community and was authored by DEV Community
DEV Community | Sciencx (2022-03-02T01:35:36+00:00) Day 18 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#740. Delete and Earn(Medium/JavaScript). Retrieved from https://www.scien.cx/2022/03/02/day-18-of-studying-leetcode-solution-until-i-can-solve-one-on-my-own-problem740-delete-and-earnmedium-javascript/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.