#1646

Easy

LeetCode Problem Workspace

Get Maximum in Generated Array

Compute the maximum value in a generated array using defined recurrence rules, leveraging array simulation techniques efficiently.

array simulation

Problem Statement

Given an integer n, generate an integer array nums of length n + 1 using these rules: nums[0] = 0, nums[1] = 1, nums[2 * i] = nums[i], and nums[2 * i + 1] = nums[i] + nums[i + 1] for 1 <= i <= n / 2. Return the maximum integer in the generated array.

For example, with n = 7, the array becomes [0,1,1,2,1,3,2,3], so the function should return 3. The array grows according to the recurrence and requires careful simulation of each index.

Examples

Example 1

Input: n = 7

Output: 3

According to the given rules: nums[0] = 0 nums[1] = 1 nums[(1 * 2) = 2] = nums[1] = 1 nums[(1 * 2) + 1 = 3] = nums[1] + nums[2] = 1 + 1 = 2 nums[(2 * 2) = 4] = nums[2] = 1 nums[(2 * 2) + 1 = 5] = nums[2] + nums[3] = 1 + 2 = 3 nums[(3 * 2) = 6] = nums[3] = 2 nums[(3 * 2) + 1 = 7] = nums[3] + nums[4] = 2 + 1 = 3 Hence, nums = [0,1,1,2,1,3,2,3], and the maximum is max(0,1,1,2,1,3,2,3) = 3.

Example 2

Input: n = 2

Output: 1

According to the given rules, nums = [0,1,1]. The maximum is max(0,1,1) = 1.

Example 3

Input: n = 3

Output: 2

According to the given rules, nums = [0,1,1,2]. The maximum is max(0,1,1,2) = 2.

Constraints

0 <= n <= 100

Solution Approach

Iterative Array Generation

Initialize nums[0] and nums[1], then iteratively compute each element up to n using the given rules. Track the maximum during iteration to avoid a second pass.

Max Tracking During Simulation

As you generate each element, maintain a variable for the current maximum. This prevents traversing the array again and directly produces the final answer.

Boundary Handling

Ensure to handle cases where n < 2 separately, since nums[1] may not exist for n = 0. Correctly simulating small arrays prevents index errors and edge-case failures.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each index from 0 to n is computed once. Space complexity is O(n) for storing the array. Tracking the maximum adds no extra asymptotic cost.

What Interviewers Usually Probe

They may ask you to explain how you handle even and odd indices differently in the recurrence.
Expect a question about why linear simulation is sufficient versus using mathematical formulas.
They might probe whether you can optimize space or track the maximum without storing the full array.

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle n = 0 or n = 1 correctly can lead to index errors.
Incorrectly applying nums[2 * i + 1] = nums[i] + nums[i + 1] may yield wrong values.
Not updating the maximum while generating the array can require an extra traversal.

Follow-up variants

Return the index of the maximum instead of the value to test tracking during simulation.
Modify the recurrence to include multipliers and track how that changes the maximum.
Generate the array recursively instead of iteratively and compare time and space efficiency.

FAQ

What is the key pattern in Get Maximum in Generated Array?

The main pattern is Array plus Simulation: generate each element based on previous elements and track the maximum during construction.

Can I optimize space usage in this problem?

Yes, for some cases you can store only the last two relevant elements and a maximum tracker instead of the full array.

What is the maximum n supported in constraints?

n can range from 0 to 100, which allows linear simulation without performance issues.

How do I handle small n values?

For n = 0 or n = 1, directly return nums[0] or nums[1] to avoid index errors.

Is it necessary to traverse the array twice?

No, you can track the maximum while generating the array, so a single pass suffices.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

class Solution:
    def getMaximumGenerated(self, n: int) -> int:
        if n < 2:
            return n
        nums = [0] * (n + 1)
        nums[1] = 1
        for i in range(2, n + 1):
            nums[i] = nums[i >> 1] if i % 2 == 0 else nums[i >> 1] + nums[(i >> 1) + 1]
        return max(nums)

Continue Practicing

#1599 maximum profit of operating a centennial wheel #1700 number of students unable to eat lunch #1701 average waiting time