Watch 8 video solutions for Maximize Consecutive Elements in an Array After Modification, a hard level problem involving Array, Dynamic Programming, Sorting. This walkthrough by Aryan Mittal has 3,262 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1051 <= nums[i] <= 106Problem 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 | Time | Space | When to Use |
|---|---|---|---|
| Sorting + Dynamic Programming | O(n log n) | O(n) | Best general solution; easy to reason about consecutive differences after sorting |
| HashMap Frequency Counting | O(n) | O(n) | When avoiding sorting and building sequences with constant-time hash lookups |