3041. Maximize Consecutive Elements in an Array After Modification LeetCode Solution

In this guide, you will get 3041. Maximize Consecutive Elements in an Array After Modification LeetCode Solution with the best time and space complexity. The solution to Maximize Consecutive Elements in an Array After Modification problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Maximize Consecutive Elements in an Array After Modification solution in C++
4. Maximize Consecutive Elements in an Array After Modification solution in Java
5. Maximize Consecutive Elements in an Array After Modification solution in Python
6. Additional Resources

Problem Statement of Maximize Consecutive Elements in an Array After Modification

You are given a 0-indexed array nums consisting of positive integers.
Initially, you can increase the value of any element in the array by at most 1.
After that, you need to select one or more elements from the final array such that those elements are consecutive when sorted in increasing order. For example, the elements [3, 4, 5] are consecutive while [3, 4, 6] and [1, 1, 2, 3] are not.
Return the maximum number of elements that you can select.

Example 1:

Input: nums = [2,1,5,1,1]
Output: 3
Explanation: We can increase the elements at indices 0 and 3. The resulting array is nums = [3,1,5,2,1].
We select the elements [3,1,5,2,1] and we sort them to obtain [1,2,3], which are consecutive.
It can be shown that we cannot select more than 3 consecutive elements.
Example 2:

Input: nums = [1,4,7,10]
Output: 1
Explanation: The maximum consecutive elements that we can select is 1.

Constraints:

1 <= nums.length <= 105
1 <= nums[i] <= 106

Complexity Analysis

• Time Complexity: O(\texttt{sort})
• Space Complexity: O(n)

3041. Maximize Consecutive Elements in an Array After Modification LeetCode Solution in C++

class Solution {
 public:
  int maxSelectedElements(vector<int>& nums) {
    int ans = 0;
    // {num: the length of the longest consecutive elements ending in num}
    unordered_map<int, int> dp;

    ranges::sort(nums);

    for (const int num : nums) {
      dp[num + 1] = dp[num] + 1;
      dp[num] = dp[num - 1] + 1;
      ans = max({ans, dp[num], dp[num + 1]});
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

3041. Maximize Consecutive Elements in an Array After Modification LeetCode Solution in Java

class Solution {
  public int maxSelectedElements(int[] nums) {
    int ans = 0;
    // {num: the length of the longest consecutive elements ending in num}
    HashMap<Integer, Integer> dp = new HashMap<>();

    Arrays.sort(nums);

    for (final int num : nums) {
      dp.put(num + 1, dp.getOrDefault(num, 0) + 1);
      dp.put(num, dp.getOrDefault(num - 1, 0) + 1);
      ans = Math.max(ans, Math.max(dp.get(num), dp.get(num + 1)));
    }

    return ans;
  }
}
// code provided by PROGIEZ

3041. Maximize Consecutive Elements in an Array After Modification LeetCode Solution in Python

class Solution:
  def maxSelectedElements(self, nums: list[int]) -> int:
    ans = 0
    # {num: the length of the longest consecutive elements ending in num}
    dp = {}

    for num in sorted(nums):
      dp[num + 1] = dp.get(num, 0) + 1
      dp[num] = dp.get(num - 1, 0) + 1
      ans = max(ans, dp[num], dp[num + 1])

    return ans
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.