Maximize Consecutive Elements in an Array After Modification

Maximize Consecutive Elements in an Array After Modification - Problem

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.

Input & Output

Example 1 — Basic Consecutive Sequence

$ Input: nums = [2,1,3]

› Output: 3

💡 Note: We can modify the array to [2,2,3] or [3,2,3], giving us the consecutive sequence [1,2,3] which has length 3.

Example 2 — Optimal Selection

$ Input: nums = [1,4,7]

› Output: 2

💡 Note: We can modify to get [2,4,7], [1,5,7], or [1,4,8]. Best consecutive sequence we can form is length 2, like [4,5] from [1,5,7].

Example 3 — All Same Values

$ Input: nums = [3,3,3,3]

› Output: 4

💡 Note: We can keep all as [3,3,3,3] or modify some to [3,3,4,4], giving consecutive sequences like [3,4] but optimal is all same value.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Array

Original array where each element can be increased by at most 1

Possible Values

Each element x can become either x or x+1, creating frequency map

Find Consecutive

Find longest consecutive sequence we can form within element limit

Key Takeaway

🎯 Key Insight: Each element can become x or x+1, so count all possible values and find the longest consecutive sequence achievable within the total element count limit.

Asked in

G Google 25 f Meta 20 a Amazon 15 M Microsoft 12

The key insight is that each element can become either x or x+1, so we count frequencies of all possible values and find the longest consecutive sequence we can form. Best approach uses frequency counting with sliding window in O(n log n) time and O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming	O(n log n)	O(n)	Use DP to track maximum consecutive sequence ending at each value
Frequency Count with Sliding Window	O(n log n)	O(n)	Count possible values and use sliding window to find longest consecutive sequence
Brute Force - Try All Modifications	O(n × 2ⁿ)	O(n)	Generate all possible arrays after modifications and find longest consecutive sequence

Dynamic Programming — Algorithm Steps

Generate all possible values (x and x+1)
Sort unique values with frequencies
Use DP: dp[i] = max consecutive length ending at value[i]
Handle transitions and frequency constraints

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set dp[0] with first value's frequency

Extend or Start

For each value, either extend previous sequence or start new

Track Maximum

Keep track of maximum valid sequence length

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_VAL 100001

int solution(int* nums, int numsSize) {
    int freq[MAX_VAL * 2] = {0};
    int offset = MAX_VAL;
    
    // Count frequencies of possible values
    for (int i = 0; i < numsSize; i++) {
        freq[nums[i] + offset]++;
        freq[nums[i] + 1 + offset]++;
    }
    
    // Get unique values
    int values[MAX_VAL * 2];
    int valueCount = 0;
    for (int i = 0; i < MAX_VAL * 2; i++) {
        if (freq[i] > 0) {
            values[valueCount++] = i - offset;
        }
    }
    
    if (valueCount == 0) return 0;
    
    // dp[i] = {max_length, elements_used} ending at values[i]
    int dp_length[MAX_VAL * 2];
    int dp_used[MAX_VAL * 2];
    
    dp_length[0] = 1;
    dp_used[0] = freq[values[0] + offset];
    
    int maxLength = 1;
    
    for (int i = 1; i < valueCount; i++) {
        // Start new sequence at values[i]
        dp_length[i] = 1;
        dp_used[i] = freq[values[i] + offset];
        
        // Try extending from previous value if consecutive
        if (values[i] == values[i-1] + 1) {
            int prevLength = dp_length[i-1];
            int prevUsed = dp_used[i-1];
            int newUsed = prevUsed + freq[values[i] + offset];
            if (newUsed <= numsSize) { // Check if we can use this many elements
                if (prevLength + 1 > dp_length[i]) {
                    dp_length[i] = prevLength + 1;
                    dp_used[i] = newUsed;
                }
            }
        }
        
        // Update global maximum
        if (dp_used[i] <= numsSize) { // Valid if doesn't exceed total elements
            if (dp_length[i] > maxLength) {
                maxLength = dp_length[i];
            }
        }
    }
    
    return maxLength;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[1000];
    int size = 0;
    char* token = strtok(line, "[],\n ");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    printf("%d\n", solution(nums, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting unique values dominates, DP scan is O(n)

⚡ Linearithmic

Space Complexity

O(n)

DP array and frequency map store up to O(n) unique values

⚡ Linearithmic Space

23.0K Views

Medium Frequency

~25 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler