3041. Maximize Consecutive Elements in an Array After Modification
HardView on LeetCode
Time: O(n log n)
Space: O(n)
Problem Overview
Each value may stay the same or rise by one, then you want the longest set of distinct consecutive integers you can form.
Intuition
Each value may stay the same or rise by one, then you want the longest set of distinct consecutive integers you can form. Sorting puts possible predecessors next to their successors. Process values left to right and keep the best consecutive chain length ending at each reachable key. The current number can become num and extend a chain ending at num minus 1, or become num plus 1 and extend a chain ending at num. Updating the num plus 1 state first avoids using the same element twice through a freshly written num entry.
Algorithm
- 1Sort the array in nondecreasing order.
- 2Maintain a map from ending value to the longest consecutive chain length that ends there.
- 3For each num, set the length ending at num plus 1 to one more than the length ending at num.
- 4Then set the length ending at num to one more than the length ending at num minus 1.
- 5Track the maximum length written into the map and return it.
Example Walkthrough
Input: nums = [2, 1, 5, 1, 1]
- 1.After sorting the values are 1, 1, 1, 2, 5.
- 2.The three ones and the two can be shaped into the chain 1, 2, 3 of length 3.
- 3.Five stays isolated, so the best answer remains 3.
Output: 3
Common Pitfalls
- •Write the num plus 1 transition before the num transition. The reverse order reuses one element.
- •Selected values must be strictly consecutive with no duplicates in the final set.
- •Distant values cannot join one chain even after a single plus one, so isolated numbers contribute only 1.
- •Sorting is required so that chains ending at nearby values already exist when a later number arrives.
3041.cs
C#
// Approach: Sort, then process each value once. For num you may keep it as num
// (extend a chain ending at num - 1) or raise it to num + 1 (extend a chain
// ending at num). Store the best length ending at each key in a map, and update
// the num + 1 entry before the num entry so the same element is not reused.
// Time: O(n log n) Space: O(n)
public class Solution
{
public int MaxSelectedElements(int[] nums)
{
int ans = 0;
var dp = new Dictionary<int, int>();
Array.Sort(nums);
foreach (int num in nums)
{
dp[num + 1] = dp.GetValueOrDefault(num, 0) + 1;
dp[num] = dp.GetValueOrDefault(num - 1, 0) + 1;
ans = Math.Max(ans, Math.Max(dp[num], dp[num + 1]));
}
return ans;
}
}
Was this solution helpful?