What is the time complexity of Delete and Earn?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Delete and Earn?

This problem uses Array, Hash Table, Dynamic Programming. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Delete and Earn?

Insight 1: The problem can be transformed into a variation of the House Robber problem. This is because choosing a number prevents you from choosing its immediate neighbors (n-1 and n+1). Insight 2: Use a frequency map to represent the points available for each number. This allows us to represent each number's worth (number * frequency) effectively.

Which companies ask LeetCode 740. Delete and Earn in interviews?

This problem is frequently asked at Accenture, Akuna Capital, Citadel.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Delete and Earn - LeetCode 740 Solution

Delete and Earn - Complete Solution Guide

Delete and Earn is LeetCode problem 740, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 oper

Detailed Explanation

The problem asks us to find the maximum points we can earn by deleting numbers from an array. When a number `nums[i]` is deleted, you earn `nums[i]` points, but you must also delete all elements equal to `nums[i] - 1` and `nums[i] + 1`. The input is an array of integers `nums`, and the output is the maximum total points that can be earned following these rules. The constraints are that the array length is between 1 and 20,000, and each number in the array is between 1 and 10,000.

Solution Approach

The solution leverages dynamic programming to solve this problem, drawing an analogy to the House Robber problem. First, it computes the frequency of each number in the input array. Then, based on the frequency, the amount of points that each number can generate is pre-computed (number * frequency). Then a dynamic programming approach is used. At each number, we have two choices: either 'delete and earn' points of this number plus points earned up to two numbers before (as deleting the current number precludes deleting its neighbors), or don't delete the current number and just keep the maximum points earned until the previous number. This is efficiently solved using a space-optimized DP approach with just two variables to track the previous and current maximum points.

Step-by-Step Algorithm

Step 1: Create a frequency map (or array) to store the counts of each number in the input `nums`.
Step 2: Determine the maximum number in the input `nums`. This is needed to initialize an array to hold the total points for each number.
Step 3: Create an array `points` where `points[i]` stores the points earned by taking all instances of number `i`. This is equal to `i * count[i]`.
Step 4: Initialize two variables, `prev` and `curr`, to 0. These will represent the maximum points earned up to `i-2` and `i-1` respectively, during the dynamic programming stage.
Step 5: Iterate through the `points` array from the smallest to the largest number. At each index `i`, calculate the maximum points that can be earned by either taking the points at index `i` plus the points earned up to index `i-2` (`prev + points[i]`), or by not taking the points at index `i` and carrying forward the points earned up to index `i-1` (`curr`). Update `prev` and `curr` accordingly. Specifically, the new `prev` is the old `curr`, and the new `curr` is the maximum of old `curr` and `prev + points[i]`.
Step 6: After iterating through the entire `points` array, the variable `curr` will hold the maximum points that can be earned. Return `curr`.

Key Insights

Insight 1: The problem can be transformed into a variation of the House Robber problem. This is because choosing a number prevents you from choosing its immediate neighbors (n-1 and n+1).
Insight 2: Use a frequency map to represent the points available for each number. This allows us to represent each number's worth (number * frequency) effectively.
Insight 3: Dynamic programming can be efficiently applied using a bottom-up approach to determine the maximum points attainable at each number based on whether to include or exclude it.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Array, Hash Table, Dynamic Programming.

Companies

Asked at: Accenture, Akuna Capital, Citadel.

Delete and Earn | LeetCode 740

Medium

Array Hash Table Dynamic Programming

Time: O(n)Space: O(n)

Solution Code

Available in:

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int deleteAndEarn(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }

        int max_val = 0;
        for (int num : counts.keySet()) {
            max_val = Math.max(max_val, num);
        }

        int[] points = new int[max_val + 1];
        for (int num : counts.keySet()) {
            points[num] = num * counts.get(num);
        }

        // This is now the House Robber problem.
        // We use a space-optimized DP approach.
        // prev represents the max points up to i-2
        // curr represents the max points up to i-1
        int prev = 0;
        int curr = 0;

        for (int p : points) {
            // At each step, we have two choices:
            // 1. Don't take the current points (p), so the max is `curr`.
            // 2. Take the current points (p), so the max is `p + prev`.
            // We choose the maximum of these two.
            int temp = curr;
            curr = Math.max(curr, prev + p);
            prev = temp;
        }

        return curr;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 740: Delete and Earn - Detailed explanation and solution approaches.

Topics

Array Hash Table Dynamic Programming

Companies

AccentureAkuna CapitalCitadel

Stats

Difficulty:Medium

Languages:4

Companies:3

Problem #:740

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Step 1: Create a frequency map (or array) to store the counts of each number in the input `nums`.
2
Step 2: Determine the maximum number in the input `nums`. This is needed to initialize an array to hold the total points for each number.
3
Step 3: Create an array `points` where `points[i]` stores the points earned by taking all instances of number `i`. This is equal to `i * count[i]`.
4
Step 4: Initialize two variables, `prev` and `curr`, to 0. These will represent the maximum points earned up to `i-2` and `i-1` respectively, during the dynamic programming stage.
5
Step 5: Iterate through the `points` array from the smallest to the largest number. At each index `i`, calculate the maximum points that can be earned by either taking the points at index `i` plus the points earned up to index `i-2` (`prev + points[i]`), or by not taking the points at index `i` and carrying forward the points earned up to index `i-1` (`curr`). Update `prev` and `curr` accordingly. Specifically, the new `prev` is the old `curr`, and the new `curr` is the maximum of old `curr` and `prev + points[i]`.
6
Step 6: After iterating through the entire `points` array, the variable `curr` will hold the maximum points that can be earned. Return `curr`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is determined by the creation of the frequency map, and the iterations through the 'points' array. The space complexity is determined by the size of the frequency map and the 'points' array, both of which are directly proportional to the range of numbers in the input array, `nums`.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Top-Down Dynamic Programming (Memoization)

The problem can also be solved using top-down dynamic programming with memoization. A recursive function can be defined to calculate the maximum points earned starting from a given number, with a memoization table to store the results of already computed subproblems.

Time: O(n), where n is the range of the numbers.Space: O(n), where n is the range of the numbers, due to the memoization table and recursion stack.

Trade-offs: The top-down approach might be easier to understand for some, but it can sometimes be less efficient due to recursion overhead. Bottom-up is generally more efficient.

✨

Key Insights

1Insight 1: The problem can be transformed into a variation of the House Robber problem. This is because choosing a number prevents you from choosing its immediate neighbors (n-1 and n+1).
2Insight 2: Use a frequency map to represent the points available for each number. This allows us to represent each number's worth (number * frequency) effectively.
3Insight 3: Dynamic programming can be efficiently applied using a bottom-up approach to determine the maximum points attainable at each number based on whether to include or exclude it.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

Edge Cases

Edge case 1: Empty input array. The solution handles this by returning 0 at the beginning of the function.
Edge case 2: All numbers in the input are the same. The algorithm correctly sums up the total points for that number.
Edge case 3: Input array with only one distinct number. The algorithm calculates the correct result.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to handle the edge case of an empty input array. The algorithm must explicitly check for this.

✗Common mistake 2: Incorrectly translating the problem into the House Robber problem. It's important to remember that deleting `nums[i]` means deleting both `nums[i] - 1` and `nums[i] + 1`.

✗Common mistake 3: Not multiplying the number by its count when calculating points. For example, if the number 2 appears three times, then taking all of the 2's is worth 2 * 3 = 6 points.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Resource allocation. Imagine allocating resources among competing projects, where allocating to one project means you cannot allocate to projects that are very similar (neighbors) due to resource constraints. The 'delete and earn' concept is applicable here.

🏦Real-world scenario 2: Investment decisions. Consider selecting stocks or investments, where picking one stock prohibits you from picking similar stocks due to market correlations or diversification strategies. The problem relates to maximizing returns while avoiding correlated assets.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

👨‍💻 From Experience

This problem pattern appears frequently in real codebases. I've used similar logic when building production systems.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 21, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 13

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 6

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Delete and Earn"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?