Skip to main content
Talentd

Maximize Consecutive Elements in an Array After Modification - Solution & Explanation

HardArrayDynamic ProgrammingSorting7 min readAsked at: Google
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given an integer array where each element can be increased by at most 1. The goal is to modify some elements so the array contains the longest possible sequence of consecutive integers. Return the maximum length of such a sequence.

Approach 1: Sorting and Counting Consecutive Elements (O(n log n) time, O(n) space)

Sort the array first so numbers are processed in increasing order. After sorting, dynamic programming tracks the longest valid chain ending at each value depending on whether the element is used as-is or incremented by +1. When two adjacent numbers differ by 0 or 1, the chain can extend directly; when the difference is 2, you can extend the chain only if the current element is incremented. Maintain a map or DP state that records the best chain length ending at each value. Sorting simplifies the transition logic because consecutive candidates appear next to each other. Time complexity is O(n log n) due to sorting, and space complexity is O(n) for DP storage.

Approach 2: HashMap for Frequency Count (O(n) time, O(n) space)

Instead of relying on sorted order, count the frequency of each value using a hash map. For every number x, you can contribute to either x or x+1 after modification. The key idea is to greedily extend consecutive sequences by checking if the next required value exists in the frequency map. Hash lookups allow constant-time checks when building sequences like x, x+1, x+2. By decrementing counts as elements are used, you avoid reusing the same element twice. This approach removes sorting and relies entirely on hash-based lookups, achieving O(n) time and O(n) space.

Both methods rely on recognizing that each element has two possible final states: its original value or the value incremented by one. Tracking these states correctly is the core dynamic programming transition.

Recommended for interviews: The sorting + DP strategy is typically expected because it clearly demonstrates reasoning about consecutive differences and controlled state transitions. It is easier to reason about edge cases after sorting. The hash map solution shows deeper optimization thinking and can reach O(n) time, but interviewers usually prioritize the sorted DP approach first. This problem combines patterns from Array, Sorting, and Dynamic Programming.

Approach 1: Sorting and Counting Consecutive Elements

The strategy here is to sort the array first. For each element in the sorted array, check how far you can extend the sequence such that the difference between the maximum and minimum elements in the sequence is at most 1. Keep track of the maximum length of such a sequence.

Steps:

  1. Sort the array.
  2. Iterate through the array and, for each element, extend to find the maximum length of consecutive elements where each can be increased by at most 1.
  3. Update the maximum sequence length found.

This solution sorts the input array first. Then for each element, it iterates over the subsequent elements to see how many of them can form a consecutive sequence (allowing one element to be incremented). It keeps track of the maximum sequence length found.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(n^2), where n is the length of nums due to the nested loop for counting consecutive elements.
Space Complexity: O(1) for storing variables and calculations.

Try this approach in the editor →

Approach 2: Using HashMap for Frequency Count

This approach utilizes a hash map to count the frequency of each number in the array. This information is then used to find the longest streak of consecutive numbers after increment.

Steps:

  1. Count the frequency of each number in the array using a hash map.
  2. Iterate through the distinct numbers. For each number, check how long a streak you can form with it by utilizing the frequency information, considering you can increment an adjacent number by 1.

This Java solution utilizes a hash map to count the occurrences of each number in the array. Then it searches for the maximum consecutive sequence by checking each number and possibly including its successor by using the frequency information.

Code

JavaC#

Java

C#

Complexity

Time Complexity: O(n), where n is the number of elements in nums because of counting and hash map operations.
Space Complexity: O(n) due to the space needed to store the frequencies.

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sorting and Counting Consecutive Elements

Time Complexity: O(n^2), where n is the length of nums due to the nested loop for counting consecutive elements.
Space Complexity: O(1) for storing variables and calculations.

Using HashMap for Frequency Count

Time Complexity: O(n), where n is the number of elements in nums because of counting and hash map operations.
Space Complexity: O(n) due to the space needed to store the frequencies.

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting + Dynamic ProgrammingO(n log n)O(n)Best general solution; easy to reason about consecutive differences after sorting
HashMap Frequency CountingO(n)O(n)When avoiding sorting and building sequences with constant-time hash lookups

Video Solution

3041. Maximize Consecutive Elements in an Array After Modification | DP | Hard ❌ - Easy ✅ • Aryan Mittal • 3,337 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Maximize Consecutive Elements in an Array After Modification easy or hard?
The problem is rated Hard because each element can transition into two possible values, which creates multiple state possibilities when forming consecutive sequences. Correctly handling duplicates and gap differences requires careful dynamic programming or frequency tracking.
Maximize Consecutive Elements in an Array After Modification Python/Java solution
Python and C++ implementations usually follow the sorting plus dynamic programming strategy. Java and C# versions often use a HashMap to track frequencies and greedily extend sequences. Both implementations maintain counts of possible values after allowing a +1 modification.
How to solve Maximize Consecutive Elements in an Array After Modification in O(n)?
Use a hash map to store frequencies of each value. Each number can represent either its original value or value +1 after modification, so you attempt to extend sequences using constant-time hash lookups. By consuming frequencies while extending x, x+1, x+2 chains, the algorithm processes each element once, achieving O(n) time and O(n) space.
What is the best approach for Maximize Consecutive Elements in an Array After Modification?
The most common solution sorts the array and uses dynamic programming to track the longest consecutive chain when each number can optionally be increased by 1. Sorting makes it easy to evaluate gaps between adjacent values and decide whether the sequence can extend. This approach runs in O(n log n) time and O(n) space and is typically the expected interview solution.
Is Maximize Consecutive Elements in an Array After Modification asked at Google/Amazon/Meta?
Problems involving consecutive sequences with limited modifications frequently appear in interviews at companies like Google, Amazon, and Meta. They test understanding of sorting, greedy reasoning, and dynamic programming transitions. Variants also appear in competitive programming and advanced array interview rounds.
What data structure is used in Maximize Consecutive Elements in an Array After Modification?
Typical solutions rely on arrays combined with sorting, dynamic programming state tracking, and hash maps for frequency counting. Sorting helps analyze gaps between numbers, while hash maps allow constant-time checks when extending sequences.
What is the time complexity of Maximize Consecutive Elements in an Array After Modification?
The standard approach runs in O(n log n) time due to sorting the array before building the consecutive sequence. The dynamic programming or counting logic afterward is linear. A hash map based method can reduce the complexity to O(n) time with O(n) extra space.

Ready to solve this problem?

Practice Maximize Consecutive Elements in an Array After Modification with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays