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.
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:
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.
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.
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:
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.
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.
| Approach | Complexity |
|---|---|
| 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. |
| 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. |
| 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 |
3041. Maximize Consecutive Elements in an Array After Modification | DP | Hard ❌ - Easy ✅ • Aryan Mittal • 3,262 views views
Watch 7 more video solutions →Practice Maximize Consecutive Elements in an Array After Modification with our built-in code editor and test cases.
Practice on FleetCode