We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximize Consecutive Elements in an Array After Modification

Number: 3298

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

You are given a 0-indexed array nums consisting of positive integers. You may “modify” any element at most once by increasing its value by 1. After performing zero or more such modifications (each element modified at most once), you must select a non‐empty subset of numbers from the final array such that when sorted the selected numbers form a sequence of consecutive integers (i.e. no gaps and no duplicates). Return the maximum number of elements you can select.

For example, if nums = [2,1,5,1,1] one optimal solution is to increase the elements at indices 0 and 3 so that the array becomes [3,1,5,2,1]. Then selecting the three values 3,1,2 (which sort to [1,2,3]) yields a consecutiveness of 3. It can be shown that you cannot select more than 3 consecutive values.

Key Insights

  • Each element a in the original array can “cover” one of two numbers: either a itself (if left unchanged) or a+1 (if increased).
  • In any valid consecutive chain (say L, L+1, …, R), each number must be produced by a distinct element. Importantly, no element can “serve” two consecutive slots.
  • One may view each element as a “resource” available on an interval [a, a+1]. Because a resource can be used only once, the overlapping potential (elements originally a can serve slot a or slot a+1) forces a careful, “flow‐like” assignment.
  • The optimal strategy is to “match” consecutive target numbers with elements. If an element is “spent” on one slot, it cannot be reused on its later neighboring slot.
  • A dynamic–programming formulation is natural when one recalls that when selecting a resource for a target x there is an intrinsic decision: if an element originally equal to x is used “in place” then—if there was an extra copy—the extra copy may “carry over” (serve as the modified value for x+1). In contrast, if no spare exists, then you must “spend” an element from the x–bucket to cover x.
  • In our DP formulation the state is binary: it matters only whether at the beginning of a slot (target value) we have a “spare” from the previous number (meaning we did not “spend” it in the previous slot) or not.

Space and Time Complexity

Time Complexity: O(M) where M = (max(nums)+1). (We build a frequency array and then run a DP over numbers 1..max(nums)+1.) Space Complexity: O(M) for the frequency and DP arrays.

Solution

The idea is to “simulate” a matching of consecutive target numbers using the observation that every element with value a can supply either a or a+1 (but not both). We do the following:

  1. Build a frequency array freq[] over the possible numbers (recall all numbers are positive; we will “simulate” numbers from 1 up to max(nums)+1).

  2. Think of covering a consecutive segment [L, L+1, …, R]. When covering a target x:

    • If we enter x “with a spare” (i.e. we already have an element from the previous bucket available because that bucket contained at least 2 copies) then we may use that spare to cover x without “using up” an element of the current bucket. Then, if freq[x] ≥ 1 we can “refresh” the spare for the next slot.
    • If we come to x without a spare then we must use one from freq[x]. If freq[x] ≥ 2 then after spending one copy the bucket still has an extra copy available which we “carry” as a spare to x+1; otherwise (if freq[x] is exactly 1) we end up with no spare for the next target.

  3. Define two functions:

    • Let h(x) be the maximum chain length starting at target x when you do NOT have a spare carried over.
    • Let g(x) be the maximum chain length starting at target x when you DO have a spare.

    Then the recurrences are:

    • If you do not have a spare (state h) then you can cover x only if freq[x] ≥ 1; when using an element from group x you “spend” one copy. In particular:

   h(x) = { 0, if freq[x] == 0;        = 1 + [if freq[x] ≥ 2 then g(x+1) else h(x+1)], if freq[x] ≥ 1. }

• If you come with a spare (state g), then target x is “automatically” covered by that spare, and you then have the option to “refresh” the spare using the current bucket if possible:

   g(x) = 1 + [if freq[x] ≥ 1 then g(x+1) else h(x+1)].

The “base” will be that for any x > M (where M = max(nums)+1) we have h(x) = g(x) = 0.

  1. Finally, note that for any starting target T the possibility to cover T depends on whether a spare is available from “T – 1”. Since an element coming from value T–1 can be increased to T (even if T–1 is not selected) we define the “initial state” for target T as:   if freq[T – 1] ≥ 1 then the state is g(T) (spare available), otherwise it is h(T).   We then take the maximum over all possible starting T.

This formulation “captures” the fact that if a bucket has at least 2 copies then you have extra material (spare) to “bridge” to the next number. In our explanation we assume that all numbers in the “chain” come from distinct indices and the DP recurrences enforce that.

Code Solutions

# Python solution with detailed comments
def maximize_consecutive(nums):
    # Build frequency array.
    max_val = max(nums)
    M = max_val + 1  # we consider numbers 1..M (M = max(nums)+1)
    freq = [0] * (M + 2)  # 1-indexed up to M+1 (we also reference freq[M+1] safely)
    for num in nums:
        # num is positive so index is num; note that modification may create num+1 up to M+1.
        if num <= M+1:
            freq[num] += 1

    # We'll use DP arrays of size M+2; dp_h[x] = h(x), dp_g[x] = g(x)
    dp_h = [0] * (M + 3)
    dp_g = [0] * (M + 3)
    # Base: for x = M+1, dp_h and dp_g are 0 (already by initialization)
    
    # Process x from M+1 down to 1 (target numbers)
    for x in range(M, 0, -1):
        if freq[x] >= 1:
            # When no spare is carried, we must use one from freq[x].
            # If we used one and freq[x] >= 2 then one extra can be carried as spare;
            # otherwise no spare is available.
            if freq[x] >= 2:
                dp_h[x] = 1 + dp_g[x+1]
            else:
                dp_h[x] = 1 + dp_h[x+1]
        else:
            dp_h[x] = 0  # cannot cover target x if no elements in group x

        # If we have a spare coming in, target x is already covered.
        # Now we can "refresh" using current bucket if available.
        if freq[x] >= 1:
            dp_g[x] = 1 + dp_g[x+1]
        else:
            dp_g[x] = 1 + dp_h[x+1]
    
    # Try all possible starting target T.
    # For a starting target T, the initial state depends on whether
    # there is a spare from bucket T-1 available (i.e. freq[T-1]>=1).
    best = 0
    # We consider T in range 1 to M+1
    for T in range(1, M+2):
        # Determine initial state for target T:
        if T-1 >= 1 and freq[T-1] >= 1:
            chain = dp_g[T]
        else:
            chain = dp_h[T]
        best = max(best, chain)
    return best

# Example usage:
if __name__ == '__main__':
    print(maximize_consecutive([2,1,5,1,1]))  # Expected output: 3
    print(maximize_consecutive([1,4,7,10]))   # Expected output: 1
← Back to All Questions