Skip to main content
Talentd

Get Maximum in Generated Array - Solution & Explanation

EasyArraySimulation12 min readAsked at: Amazon, Verizon, Google
Practice this problem

Problem Statement

You are given an integer n. A 0-indexed integer array nums of length n + 1 is generated in the following way:

  • nums[0] = 0
  • nums[1] = 1
  • nums[2 * i] = nums[i] when 2 <= 2 * i <= n
  • nums[2 * i + 1] = nums[i] + nums[i + 1] when 2 <= 2 * i + 1 <= n

Return 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 <= 100

Approach Overview

Problem 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.

Approach 1: Iterative Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) because we iterate through the array once.
Space Complexity: O(n) for storing the array.

Try this approach in the editor ā†’

Approach 2: Space-Optimized Iterative Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) - Single traversal of the sequence.
Space Complexity: O(1) - Constant space for integer variables.

Try this approach in the editor ā†’

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Iterative Approach

Time Complexity: O(n) because we iterate through the array once.
Space Complexity: O(n) for storing the array.

Space-Optimized Iterative Approach

Time Complexity: O(n) - Single traversal of the sequence.
Space Complexity: O(1) - Constant space for integer variables.

Default Approachā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative SimulationO(n)O(n)Standard approach when directly implementing the recurrence definition
Space-Optimized Iterative (Track Max Inline)O(n)O(n) with O(1) extraWhen you want a single pass and minimal additional memory beyond the array

Video Solution

Get Maximum in Generated Array | LeetCode 1646 | Array ā€¢ Naresh Gupta ā€¢ 1,882 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

Is Get Maximum in Generated Array easy or hard?
Get Maximum in Generated Array is classified as an Easy problem on LeetCode. The main challenge is correctly translating the recurrence definition into code while handling even and odd indices.
Get Maximum in Generated Array Python/Java solution
Both Python and Java implementations follow the same logic: create an array of size n + 1, apply the even and odd recurrence rules for each index, and track the maximum value during iteration. The algorithm runs in O(n) time and uses O(n) space.
How to solve Get Maximum in Generated Array in O(n)?
Initialize an array of size n + 1 with nums[0] = 0 and nums[1] = 1. Iterate from i = 2 to n: if i is even, set nums[i] = nums[i/2]; if i is odd, set nums[i] = nums[i/2] + nums[i/2 + 1]. Track the maximum value while filling the array to keep the overall runtime O(n).
What is the best approach for Get Maximum in Generated Array?
The best approach is iterative array simulation. Build the array from index 2 to n using the recurrence rules and track the maximum value during construction. This runs in O(n) time and uses O(n) space, which is optimal because every element must be generated.
Is Get Maximum in Generated Array asked at Google/Amazon/Meta?
This problem is categorized as an easy array simulation problem and is commonly used in coding practice platforms to test understanding of recurrence-based array construction. Variations of similar dynamic or generated array questions have appeared in interviews at large tech companies.
What data structure is used in Get Maximum in Generated Array?
The solution primarily uses a simple array to store generated values. Each index depends on previously computed indices, making an array the most natural and efficient structure for constant-time lookups.
What is the time complexity of Get Maximum in Generated Array?
The time complexity is O(n). Each index from 2 to n is processed exactly once, and computing each value involves constant-time operations such as division, addition, and array access.

Ready to solve this problem?

Practice Get Maximum in Generated Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Largest Element in an Array after Merge Operations