Maximize Consecutive Elements in an Array After Modification

Hard
1649.

Maximize Consecutive Elements in an Array After Modification

Maximize Consecutive Elements in an Array After Modification is a hard coding problem on arrays, dynamic programming and sorting, asked in Google interviews.

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^5
  • 1 <= nums[i] <= 10^6
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSelectedElements = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • 1 <= nums[i] <= 10^6

Hints for Maximize Consecutive Elements in an Array After Modification

  1. Hint 1

    After sorting, every element can play one of two values: x or x + 1.

  2. Hint 2

    Let dp[v] be the longest consecutive run that ends exactly at value v using the elements seen so far.

  3. Hint 3

    Process elements in sorted order. For each x, first set dp[x + 1] = dp[x] + 1 (use it as x + 1), then dp[x] = dp[x - 1] + 1 (use it as x). 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

  1. Sort nums.
  2. Keep a map dp (missing keys are 0). For each x in sorted order: dp[x + 1] = dp[x] + 1, then dp[x] = dp[x - 1] + 1.
  3. 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] before dp[x + 1] lets one element be used both as x and x + 1.
  • Duplicate values are common — a sorted run of equal elements can supply both x and x + 1, but never more than that.
  • An array indexed up to 10^6 + 2 works 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 best

Java

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