You are given an integer n. A 0-indexed integer array nums of length n + 1 is generated in the following way:
nums[0] = 0nums[1] = 1nums[2 * i] = nums[i] when 2 <= 2 * i <= nnums[2 * i + 1] = nums[i] + nums[i + 1] when 2 <= 2 * i + 1 <= nReturn the maximum integer in the array nums.
Example 1:
Input: n = 7 Output: 3 Explanation: 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 Explanation: According to the given rules, nums = [0,1,1]. The maximum is max(0,1,1) = 1.
Example 3:
Input: n = 3 Output: 2 Explanation: According to the given rules, nums = [0,1,1,2]. The maximum is max(0,1,1,2) = 2.
Constraints:
0 <= n <= 100Problem Overview: You build an integer array nums using a specific recurrence rule. Starting with nums[0] = 0 and nums[1] = 1, every index i from 2 to n is derived from earlier values. The task is to generate this array up to n and return the maximum value that appears in it.
Approach 1: Iterative Simulation (Time: O(n), Space: O(n))
The most direct method is to simulate the construction of the array exactly as defined. Allocate an array nums of size n + 1. For every index i from 2 to n, apply the rule: if i is even, set nums[i] = nums[i / 2]; if i is odd, set nums[i] = nums[i / 2] + nums[i / 2 + 1]. Each value depends only on previously computed indices, so a single forward pass works. After building the array, scan it to find the maximum value. This is a classic array construction problem combined with straightforward simulation. The time complexity is O(n) for building the array and scanning it, and the space complexity is O(n) for storing the generated values.
Approach 2: Space-Optimized Iterative Approach (Time: O(n), Space: O(n) with O(1) extra)
You can remove the extra pass used to compute the maximum by tracking it while generating the array. As each nums[i] is computed, update a running maxValue. The recurrence remains the same, but the algorithm performs both generation and maximum tracking in a single loop. This eliminates the need for a second traversal and keeps additional memory usage constant beyond the required array storage. The algorithm still runs in O(n) time and uses O(n) space for the generated array, but only O(1) extra variables.
Recommended for interviews: The iterative simulation is what interviewers expect. It shows you can translate a recurrence definition directly into code and reason about dependencies between indices. Tracking the maximum during construction is a small but practical optimization that demonstrates attention to efficiency while keeping the implementation simple.
This approach involves generating the array nums iteratively by applying the given rules until we reach n. We also keep track of the maximum value encountered during this generation.
We initialize an array nums with the given starting values. For each index, we check if it is even or odd and apply the appropriate rule to populate nums[i]. We track the maximum value found during this iteration.
Time Complexity: O(n) because we iterate through the array once.
Space Complexity: O(n) for storing the array.
In the space-optimized approach, we reduce the space complexity by keeping track of only the required last computed values instead of maintaining the whole array. While iterating, we directly compute the maximum value.
This approach reduces space by using only two integer variables to keep track of the necessary previous values, efficiently computing the values and the maximum value simultaneously.
Time Complexity: O(n) - Single traversal of the sequence.
Space Complexity: O(1) - Constant space for integer variables.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(n) because we iterate through the array once. |
| Space-Optimized Iterative Approach | Time Complexity: O(n) - Single traversal of the sequence. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Simulation | O(n) | O(n) | Standard approach when directly implementing the recurrence definition |
| Space-Optimized Iterative (Track Max Inline) | O(n) | O(n) with O(1) extra | When you want a single pass and minimal additional memory beyond the array |
Get Maximum in Generated Array | LeetCode 1646 | Array • Naresh Gupta • 1,851 views views
Watch 9 more video solutions →Practice Get Maximum in Generated Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor