Maximize Consecutive Elements in an Array After Modification

For Maximize Consecutive Elements in an Array After Modification, the key is to sort first, then track the best chain ending at each value. Each number can stay as x or become x + 1, so the DP transition must update both endpoints without reusing the same element twice. This turns a messy subset problem into a clean longest consecutive chain over reachable values.

Problem Statement

You receive a 0-indexed array of positive integers. For each element, you may leave it unchanged or increase it by exactly 1 at most once. After all choices are made, pick a non-empty subset whose sorted values form a strict consecutive run with no gaps and no duplicates, such as 4, 5, 6.

The goal is to return the maximum possible size of that run. In nums = [2,1,5,1,1], the best result is 3 because modifications can create values that fit into a chain like 1, 2, 3. In nums = [1,4,7,10], every number stays isolated even after the optional plus-one move, so the answer is 1.

Examples

Example 1

Input: nums = [2,1,5,1,1]

Output: 3

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

The maximum consecutive elements that we can select is 1.

Constraints

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

Solution Approach

Sort to expose consecutive transitions

Sorting groups equal numbers together and puts possible predecessors right before possible successors. Once sorted, each value x only needs to connect to chains ending at x - 1 or x, because this element can contribute as x or x + 1. That removes the need to test arbitrary subsets.

Use DP states for chain endings

Maintain the best length of a consecutive chain ending at a specific final value. When processing number x, update the state for ending at x using the previous chain ending at x - 1, and update the state for ending at x + 1 using the previous chain ending at x. The critical detail is to snapshot old values before writing new ones, so one element does not extend both states through freshly updated data.

Take the maximum over all reachable endings

As you scan the sorted array, every element either starts a new chain of length 1 or extends an existing chain by matching the next required value after modification. The answer is the largest DP value ever written. This handles dense duplicates well, which is exactly where greedy local choices often fail on this problem.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting costs O(n log n), and the DP scan is O(n) with O(n) or O(u) extra space depending on whether you store states for all processed values or only active map entries, where u is the number of distinct reachable endings.

What Interviewers Usually Probe

• They mention sorting first because the valid transitions depend only on nearby values after ordering.
• They push on how to model one element contributing as either x or x + 1 without double counting.
• They ask why greedy merging duplicates fails, which points toward state transition DP instead of interval picking.

Common Pitfalls or Variants

Common pitfalls

• Updating the DP state for x and then using that fresh value to compute x + 1 in the same step, which illegally reuses one number twice.
• Treating duplicates as automatically helpful even when repeated equal values break a strict consecutive run unless some are shifted by 1.
• Building chains on original indices instead of final values, which misses that order does not matter after selecting and sorting the subset.

Follow-up variants

• Allow decreasing by 1 as well, which expands each number into three reachable endpoints and widens the DP transition graph.
• Ask for the actual selected subset, which requires parent tracking on the same end-value DP states.
• Limit the number of modified elements, which adds a second DP dimension for used operations.

FAQ

What is the main pattern in Maximize Consecutive Elements in an Array After Modification?

The main pattern is state transition dynamic programming after sorting. Each number can finish as x or x + 1, so you track the best consecutive chain ending at those final values.

Why is sorting necessary for problem 3041?

Sorting makes the only useful predecessors local in value space. After that, a number only needs to extend chains ending at x - 1 or x, instead of checking many unordered subset combinations.

Why does a greedy approach often fail here?

A greedy choice can spend a duplicate on x + 1 too early and block a longer chain later. The DP keeps both possibilities alive, which is crucial when many equal values compete for adjacent endpoints.

Can this be solved in linear time without sorting?

Not in the standard comparison model for arbitrary input order. The transition depends on consecutive values, so sorting is the clean way to align candidates and keep the DP logic correct.

What is the most common bug in the state transition DP?

The biggest bug is overwriting the state for x before computing the update for x + 1 from the old state. You need temporary variables or careful ordering so one array element contributes only once.