Introduction

In this blog post, we will explore how to solve the LeetCode problem "740" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

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 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 * 104 1 <= nums[i] <= 104

Explanation

Here's the solution to the problem, incorporating dynamic programming for optimal efficiency:

• High-Level Approach:

  • Use a Counter to efficiently count the occurrences of each number in nums.
  • Convert the problem into a variant of the house robber problem. Instead of houses, we have numbers, and instead of robbing adjacent houses, we cannot pick adjacent numbers.
  • Apply dynamic programming to compute the maximum points achievable by either picking a number or skipping it.

• Complexity:

  • Runtime Complexity: O(N), where N is the range of numbers (1 to 10000).
  • Storage Complexity: O(N)

Code

    from collections import Counter

def deleteAndEarn(nums):
    """
    Calculates the maximum points obtainable by deleting numbers and their adjacent numbers.

    Args:
        nums: A list of integers.

    Returns:
        The maximum number of points that can be earned.
    """

    counts = Counter(nums)
    max_num = max(nums)

    points = [0] * (max_num + 1)
    for num, count in counts.items():
        points[num] = num * count

    dp = [0] * (max_num + 1)
    dp[1] = points[1]

    for i in range(2, max_num + 1):
        dp[i] = max(dp[i-1], dp[i-2] + points[i])

    return dp[max_num]