Maximize Consecutive Elements in an Array After Modification

Maximize Consecutive Elements in an Array After Modification

What is this problem about?

In this problem, you are given an array of integers. You are allowed to perform an operation on each element at most once: you can either leave it exactly as it is, or increment its value by exactly 1. Your goal is to maximize the length of a contiguous sequence of consecutive integers present in the array after performing these optimal modifications.

Why is this asked in interviews?

This is a brilliant dynamic programming problem that tests state transitions. Interviewers ask it because the operation is highly restrictive (+1 or +0). It evaluates if a candidate can sort the data and build dynamic programming chains. It separates candidates who try to use Hash Sets to blindly guess sequences from those who can rigorously track multiple simultaneous chain possibilities in a single pass.

Algorithmic pattern used

This problem leverages Sorting followed by 1D Dynamic Programming (Hash Map tracking).

1. Sort the array.
2. Maintain a Hash Map dp where the key is the integer value and the value is the length of the longest consecutive sequence ending exactly at that integer.
3. For each number x in the sorted array, you have two choices for what it can become: x or x + 1.
   • If it becomes x, it can append to a sequence ending in x - 1. So, new_dp[x] = dp[x - 1] + 1.
   • If it becomes x + 1, it can append to a sequence ending in x. So, new_dp[x + 1] = dp[x] + 1.
4. Update the dp map and track the global maximum sequence length.

Example explanation

Array: [2, 1, 4, 3] Sort: [1, 2, 3, 4]. Map dp = {}.

• num = 1:
  • Becomes 1: dp[1] = dp[0] + 1 = 1.
  • Becomes 2: dp[2] = dp[1_old] + 1 = 1. (Note: use old state!). Map: {1: 1, 2: 1}.
• num = 2:
  • Becomes 2: dp[2] = dp[1] + 1 = 1 + 1 = 2.
  • Becomes 3: dp[3] = dp[2_old] + 1 = 1 + 1 = 2. Map: {1: 1, 2: 2, 3: 2}.
• num = 3:
  • Becomes 3: dp[3] = dp[2] + 1 = 2 + 1 = 3.
  • Becomes 4: dp[4] = dp[3_old] + 1 = 2 + 1 = 3. Map {..., 3: 3, 4: 3}.
• num = 4:
  • Becomes 4: dp[4] = dp[3] + 1 = 4.
  • Becomes 5: dp[5] = dp[4_old] + 1 = 4. Max length found is 4. (The sequence 1, 2, 3, 4).

Common mistakes candidates make

A major pitfall is updating the dp map in-place during the processing of a single number x without caching the previous state. If you update dp[x], and then immediately use that newly updated dp[x] to calculate dp[x+1], you are double-counting the current element! You must calculate both new_x and new_x_plus_1 using the previous iteration's map values before committing them to the map.

Interview preparation tip

When solving chain-building DP problems (like LIS variations), sorting is almost always the required first step to ensure you process elements chronologically. Use a dictionary/map for your DP table when the values in the array can be large and sparse, preventing massive memory allocations for arrays.