Maximize Consecutive Elements in an Array After Modification Solution
Maximize Consecutive Elements in an Array After Modification solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximize Consecutive Elements in an Array After Modification is a hard coding problem on arrays, dynamic programming and sorting, asked in Google interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Sorting
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array nums of positive integers. First, you may increase the value of any element by at most 1 (each element independently: by 0 or by 1).
Then select one or more elements from the modified array such that, once sorted, they are consecutive — each one exactly one more than the previous. For example [3, 4, 5] is consecutive, while [3, 4, 6] and [1, 1, 2, 3] are not.
Return the maximum number of elements you can select.
Example 1
Input: nums = [2,1,5,1,1]
Output: 3
Explanation: Bump index 0 to 3 and index 3 to 2: [3,1,5,2,1]. Select 1, 2 and 3.
Example 2
Input: nums = [1,4,7,10]
Output: 1
Explanation: The values are too far apart; any single element works.
Example 3
Input: nums = [3,3,3]
Output: 2
Explanation: Keep one 3 and bump another to 4. The third copy cannot help — a value cannot be selected twice.
Constraints
1 <= nums.length <= 10^51 <= nums[i] <= 10^6
Hints for Maximize Consecutive Elements in an Array After Modification
Hint 1
After sorting, every element can play one of two values:
xorx + 1.Hint 2
Let
dp[v]be the longest consecutive run that ends exactly at valuevusing the elements seen so far.Hint 3
Process elements in sorted order. For each
x, first setdp[x + 1] = dp[x] + 1(use it asx + 1), thendp[x] = dp[x - 1] + 1(use it asx). The order matters: the second update must not feed the first.
How to solve Maximize Consecutive Elements in an Array After Modification
Sort the array; then a run of consecutive values can be built by scanning elements in order, each element extending a run either as itself or as itself plus one. A hash map from the run's last value to its best length captures every choice.
Approach
- Sort
nums. - Keep a map
dp(missing keys are 0). For eachxin sorted order:dp[x + 1] = dp[x] + 1, thendp[x] = dp[x - 1] + 1. - Track the maximum value written; that is the answer.
Why it works
In a chosen run, sort the selected elements by value; their original values are non-decreasing too, because each final value is the original or one more and finals are strictly increasing by one. So processing elements in sorted order sees every run's elements in run order, and each element can only extend a run ending at x - 1 (as x) or at x (as x + 1). Updating x + 1 first uses the value of dp[x] from earlier elements, so one element never counts twice.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Updating
dp[x]beforedp[x + 1]lets one element be used both asxandx + 1. - Duplicate values are common — a sorted run of equal elements can supply both
xandx + 1, but never more than that. - An array indexed up to
10^6 + 2works too, but a hash map avoids allocating it per test.
Reference solution
Python
from typing import List
def maxSelectedElements(nums: List[int]) -> int:
dp = {}
best = 0
for x in sorted(nums):
dp[x + 1] = dp.get(x, 0) + 1
dp[x] = dp.get(x - 1, 0) + 1
best = max(best, dp[x], dp[x + 1])
return bestJava
public static int maxSelectedElements(int[] nums) {
int[] a = nums.clone();
Arrays.sort(a);
HashMap<Integer, Integer> dp = new HashMap<>();
int best = 0;
for (int x : a) {
int up = dp.getOrDefault(x, 0) + 1;
dp.put(x + 1, up);
int here = dp.getOrDefault(x - 1, 0) + 1;
dp.put(x, here);
best = Math.max(best, Math.max(up, here));
}
return best;
}C++
int maxSelectedElements(vector<int>& nums) {
vector<int> a = nums;
sort(a.begin(), a.end());
unordered_map<int, int> dp;
int best = 0;
for (int x : a) {
int up = (dp.count(x) ? dp[x] : 0) + 1;
dp[x + 1] = up;
int here = (dp.count(x - 1) ? dp[x - 1] : 0) + 1;
dp[x] = here;
best = max(best, max(up, here));
}
return best;
}JavaScript
var maxSelectedElements = function(nums) {
var a = nums.slice().sort(function(p, q) { return p - q; });
var dp = new Map(), best = 0;
for (var i = 0; i < a.length; i++) {
var x = a[i];
var up = (dp.get(x) || 0) + 1;
dp.set(x + 1, up);
var here = (dp.get(x - 1) || 0) + 1;
dp.set(x, here);
best = Math.max(best, up, here);
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming