LeetCode 1646 - Get Maximum in Generated Array

LeetCode Problem 1646

Difficulty: 🟢 Easy
Topics: Array, Simulation

Solution

Problem Understanding

The problem asks us to generate an array called nums using a specific set of rules, then return the maximum value that appears in that array.

The array has length n + 1, meaning its valid indices range from 0 to n. The generation rules define how each element is computed based on previously computed elements.

The rules are:

• nums[0] = 0

• nums[1] = 1

• For even indices:

• nums[2 * i] = nums[i]

• For odd indices:

• nums[2 * i + 1] = nums[i] + nums[i + 1]

The important detail is that every new value depends only on values that were already generated earlier. This means we can build the array incrementally from left to right.

The input is a single integer n, and the output is the maximum integer that appears anywhere in the generated array.

The constraints are very small:

• 0 <= n <= 100

Since n is at most 100, even relatively inefficient solutions would still run quickly. However, the problem is primarily testing whether we correctly simulate the generation process.

There are several important edge cases:

• n = 0, the array contains only [0]
• n = 1, the array is [0, 1]
• Small values where some generation rules never execute
• Odd and even indices must be handled differently
• Accessing nums[i + 1] must always remain valid

The problem guarantees that the rules always produce valid indices when their conditions are satisfied.

Approaches

Brute Force Approach

The most direct solution is to literally follow the problem statement and generate every element one by one.

We create an array of size n + 1, initialize the known base cases, then iterate through indices and apply the generation rules.

At each step:

• If the current index is even, copy the value from nums[index // 2]
• If the current index is odd, compute the sum of two earlier values

After constructing the entire array, we scan the array again to find the maximum value.

This approach is correct because it exactly mirrors the definition given in the problem statement.

Even though the constraints are tiny, this approach still performs unnecessary work because it requires a second pass to compute the maximum.

Optimal Approach

The key observation is that while generating the array, we already see every value exactly once.

Instead of generating the full array and then scanning it later, we can maintain a running maximum during construction.

Whenever a new value is computed:

• Compare it with the current maximum
• Update the maximum if needed

This avoids the extra traversal and keeps the logic clean and efficient.

Because every value depends only on previously computed values, dynamic programming naturally applies here. Each state is built from smaller already-known states.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Generate array, then scan again for maximum
Optimal	O(n)	O(n)	Generate array while tracking maximum simultaneously

Algorithm Walkthrough

1. Handle the smallest edge case first.

If n == 0, the array contains only [0], so the answer is immediately 0. 2. Create an array nums of size n + 1.

This array will store all generated values. We need it because future values depend on earlier entries. 3. Initialize the base cases.

Set:

• nums[0] = 0
• nums[1] = 1

Also initialize the current maximum as 1, since nums[1] is currently the largest known value. 4. Iterate from index 2 through n.

Each index must be computed according to whether it is even or odd. 5. Handle even indices.

If i is even:

nums[i] = nums[i // 2]

This directly follows the generation rule. 6. Handle odd indices.

If i is odd:

nums[i] = nums[i // 2] + nums[i // 2 + 1]

Integer division gives us the correct parent indices. 7. Update the running maximum.

After computing nums[i], compare it with the current maximum.

If the new value is larger, update the maximum. 8. Return the maximum after the loop finishes.

Why it works

The algorithm works because every value in the array is generated exactly according to the rules provided in the problem statement.

At iteration i, all smaller indices have already been computed, so any required dependencies already exist. Since we process indices in increasing order, every computation is valid.

Tracking the maximum during generation guarantees that by the end of the loop, we have seen every value exactly once, so the stored maximum must be the largest value in the array.

Python Solution

class Solution:
    def getMaximumGenerated(self, n: int) -> int:
        if n == 0:
            return 0

        nums = [0] * (n + 1)
        nums[0] = 0
        nums[1] = 1

        maximum = 1

        for i in range(2, n + 1):
            if i % 2 == 0:
                nums[i] = nums[i // 2]
            else:
                nums[i] = nums[i // 2] + nums[i // 2 + 1]

            maximum = max(maximum, nums[i])

        return maximum

The implementation begins by handling the special case where n is 0. Without this check, attempting to assign nums[1] would cause an index error because the array length would only be 1.

Next, the solution allocates an array of length n + 1 and initializes the two required base values.

The loop starts at index 2 because indices 0 and 1 are already known.

Inside the loop:

• Even indices copy a previous value
• Odd indices compute the sum of two earlier values

After generating each value, the algorithm immediately updates the running maximum. This avoids needing another traversal later.

Finally, the function returns the largest value encountered.

Go Solution

func getMaximumGenerated(n int) int {
    if n == 0 {
        return 0
    }

    nums := make([]int, n+1)
    nums[0] = 0
    nums[1] = 1

    maximum := 1

    for i := 2; i <= n; i++ {
        if i%2 == 0 {
            nums[i] = nums[i/2]
        } else {
            nums[i] = nums[i/2] + nums[i/2+1]
        }

        if nums[i] > maximum {
            maximum = nums[i]
        }
    }

    return maximum
}

The Go implementation follows the same logic as the Python solution.

A slice is created using make([]int, n+1), which automatically initializes all entries to zero.

Go does not provide a built in max function for integers, so the maximum value is updated using a simple comparison.

Integer division in Go behaves exactly as needed for this problem, so expressions like i/2 correctly produce floor division.

Since the constraints are extremely small, integer overflow is not a concern.

Worked Examples

Example 1

Input:

n = 7

Initial state:

Index	Value
0	0
1	1

Current maximum:

1

Now generate values from 2 to 7.

i	Even/Odd	Formula Used	nums[i]	nums Array	Maximum
2	Even	nums[2] = nums[1]	1	[0,1,1]	1
3	Odd	nums[3] = nums[1] + nums[2]	2	[0,1,1,2]	2
4	Even	nums[4] = nums[2]	1	[0,1,1,2,1]	2
5	Odd	nums[5] = nums[2] + nums[3]	3	[0,1,1,2,1,3]	3
6	Even	nums[6] = nums[3]	2	[0,1,1,2,1,3,2]	3
7	Odd	nums[7] = nums[3] + nums[4]	3	[0,1,1,2,1,3,2,3]	3

Final answer:

3

Example 2

Input:

n = 2

Initial array:

[0, 1]

Generate index 2:

i	Formula	nums[i]
2	nums[2] = nums[1]	1

Final array:

[0, 1, 1]

Maximum value:

1

Example 3

Input:

n = 3

Initial array:

[0, 1]

Generate remaining values:

i	Formula	nums[i]
2	nums[2] = nums[1]	1
3	nums[3] = nums[1] + nums[2]	2

Final array:

[0, 1, 1, 2]

Maximum value:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each index from 2 through n is processed exactly once
Space	O(n)	The generated array of size n + 1 is stored

The algorithm performs a constant amount of work for every array element, so the runtime grows linearly with n.

The space usage is also linear because we must store the generated values for future computations.

Test Cases

solution = Solution()

assert solution.getMaximumGenerated(0) == 0  # Smallest possible input
assert solution.getMaximumGenerated(1) == 1  # Base case with two elements
assert solution.getMaximumGenerated(2) == 1  # First even-generated value
assert solution.getMaximumGenerated(3) == 2  # First odd-generated value
assert solution.getMaximumGenerated(7) == 3  # Example from problem statement
assert solution.getMaximumGenerated(15) == 5  # Larger generated structure
assert solution.getMaximumGenerated(50) == 7  # Mid-range input
assert solution.getMaximumGenerated(100) == 21  # Maximum constraint value

Test	Why
n = 0	Verifies smallest boundary case
n = 1	Ensures base initialization works
n = 2	Tests first even index generation
n = 3	Tests first odd index generation
n = 7	Matches provided example
n = 15	Verifies repeated recursive structure
n = 50	Tests larger dynamic generation
n = 100	Verifies behavior at maximum constraint

Edge Cases

Edge Case 1: n = 0

This is the most important special case because the array contains only one element:

[0]

Without explicitly handling this case, the implementation would attempt to assign nums[1] = 1, which would cause an out-of-bounds error. The solution avoids this by immediately returning 0 when n == 0.

Edge Case 2: Small Arrays

When n is 1, 2, or 3, only a few generation rules execute.

These small cases are common sources of off-by-one mistakes, especially when loops start at index 2. The implementation handles them correctly because the loop range naturally skips invalid iterations when n is too small.

Edge Case 3: Odd Index Computation

Odd indices require accessing both:

nums[i // 2]
nums[i // 2 + 1]

A common mistake is using incorrect parent indices or accidentally accessing out-of-range values.

The problem guarantees that for every valid odd index, both required parent indices already exist. Since the algorithm processes indices in increasing order, those earlier values have already been computed before they are needed.