Get Maximum in Generated Array solution and explanation
Google
9 more videos on this problem
Get Maximum in Generated Array | LeetCode 1646 | ArrayNaresh Gupta · 7:31 · 1K views
Get Maximum in Generated Array | Live Coding with Explanation | Leetcode #Algorithms Made Easy · 2:36 · 1K views
Leetcode 1646. Get Maximum in Generated ArrayFraz · 2:54 · 1K views
Leetcode - Get Maximum in Generated Array (Python)Timothy H Chang · 4:42 · 700 views
Get Maximum in Generated Array | Leetcode 1646Coding Decoded · 6:13 · 654 views
LeetCode 1646. Get Maximum in Generated Array | January Daily Challenge | C++ | ArrayCherry Coding [IIT-G] · 5:31 · 530 views
1646. Get Maximum in Generated Array (Leetcode Easy)Programming Live with Larry · 5:50 · 336 views
Get Maximum in Generated Array | Leetcode 1646 | Amazon Google Facebook interview questionSuper Lazy Coder · 7:28 · 271 views
Get Maximum in Generated Array | dynamic programming | leetcode 1646Joey'sTech · 9:50 · 256 views
1646. Get Maximum in Generated Array | Leetcode Jan/15/2021 | Coders CampCoders Camp · 8:07 · 238 views
The problem
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]when2 <= 2 * i <= nnums[2 * i + 1] = nums[i] + nums[i + 1]when2 <= 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.
def getMaximumGenerated(n):
if n == 0:
return 0
nums = [0] * (n + 1)
nums[0], nums[1] = 0, 1
max_val = 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]
max_val = max(max_val, nums[i])
return max_val
print(getMaximumGenerated(7))public class Solution {
public int getMaximumGenerated(int n) {
if (n == 0) return 0;
int[] nums = new int[n + 1];
nums[0] = 0;
nums[1] = 1;
int max_val = 1;
for (int i = 2; i <= n; i++) {
if (i % 2 == 0) {
nums[i] = nums[i / 2];
} else {
nums[i] = nums[i / 2] + nums[i / 2 + 1];
}
max_val = Math.max(max_val, nums[i]);
}
return max_val;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.getMaximumGenerated(7));
}
}#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int getMaximumGenerated(int n) {
if (n == 0) return 0;
vector<int> nums(n + 1);
nums[0] = 0;
nums[1] = 1;
int max_val = 1;
for (int i = 2; i <= n; i++) {
if (i % 2 == 0) {
nums[i] = nums[i / 2];
} else {
nums[i] = nums[i / 2] + nums[i / 2 + 1];
}
max_val = max(max_val, nums[i]);
}
return max_val;
}
int main() {
int n = 7;
cout << getMaximumGenerated(n) << endl;
return 0;
}function getMaximumGenerated(n) {
if (n === 0) return 0;
const nums = [0, 1];
let maxVal = 1;
for (let i = 2; i <= n; i++) {
if (i % 2 === 0) {
nums[i] = nums[i / 2];
} else {
nums[i] = nums[Math.floor(i / 2)] + nums[Math.floor(i / 2) + 1];
}
maxVal = Math.max(maxVal, nums[i]);
}
return maxVal;
}
console.log(getMaximumGenerated(7));#include <stdio.h>
int getMaximumGenerated(int n) {
if (n == 0) return 0;
int nums[n + 1];
nums[0] = 0;
nums[1] = 1;
int max_val = 1;
for (int 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] > max_val) {
max_val = nums[i];
}
}
return max_val;
}
int main() {
int n = 7;
printf("%d\n", getMaximumGenerated(n));
return 0;
}using System;
public class Solution {
public int GetMaximumGenerated(int n) {
if (n == 0) return 0;
int[] nums = new int[n + 1];
nums[0] = 0;
nums[1] = 1;
int max_val = 1;
for (int i = 2; i <= n; i++) {
if (i % 2 == 0) {
nums[i] = nums[i / 2];
} else {
nums[i] = nums[i / 2] + nums[i / 2 + 1];
}
max_val = Math.Max(max_val, nums[i]);
}
return max_val;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.GetMaximumGenerated(7));
}
}For Python, we initialize a list and fill it using a loop that applies the rules depending on the index. The maximum value is computed and printed in the end.
Time Complexity: O(n) - One pass through 0 to n.
Space Complexity: O(n) for the nums list.
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.
def getMaximumGenerated(n):
if n == 0:
return 0
if n == 1:
return 1
prev1, prev2, current = 1, 0, 0
max_val = 1
for i in range(2, n + 1):
if i % 2 == 0:
current = prev1
else:
current = prev1 + prev2
prev2 = prev1
prev1 = current
max_val = max(max_val, current)
return max_val
print(getMaximumGenerated(7))public class Solution {
public int getMaximumGenerated(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
int prev1 = 1, prev2 = 0, current, max_val = 1;
for (int i = 2; i <= n; i++) {
if (i % 2 == 0) {
current = prev1;
} else {
current = prev1 + prev2;
}
prev2 = prev1;
prev1 = current;
max_val = Math.max(max_val, current);
}
return max_val;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.getMaximumGenerated(7));
}
}#include <iostream>
using namespace std;
int getMaximumGenerated(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
int prev1 = 1, prev2 = 0, current, max_val = 1;
for (int i = 2; i <= n; i++) {
if (i % 2 == 0) {
current = prev1;
} else {
current = prev1 + prev2;
}
prev2 = prev1;
prev1 = current;
max_val = max(max_val, current);
}
return max_val;
}
int main() {
int n = 7;
cout << getMaximumGenerated(n) << endl;
return 0;
}function getMaximumGenerated(n) {
if (n === 0) return 0;
if (n === 1) return 1;
let prev1 = 1, prev2 = 0, current = 0, maxVal = 1;
for (let i = 2; i <= n; i++) {
if (i % 2 === 0) {
current = prev1;
} else {
current = prev1 + prev2;
}
prev2 = prev1;
prev1 = current;
maxVal = Math.max(maxVal, current);
}
return maxVal;
}
console.log(getMaximumGenerated(7));#include <stdio.h>
int getMaximumGenerated(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
int prev1 = 1, prev2 = 0, current, max_val = 1;
for (int i = 2; i <= n; i++) {
if (i % 2 == 0) {
current = prev1;
} else {
current = prev1 + prev2;
}
prev2 = prev1;
prev1 = current;
if (current > max_val) {
max_val = current;
}
}
return max_val;
}
int main() {
int n = 7;
printf("%d\n", getMaximumGenerated(n));
return 0;
}using System;
public class Solution {
public int GetMaximumGenerated(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
int prev1 = 1, prev2 = 0, current, max_val = 1;
for (int i = 2; i <= n; i++) {
if (i % 2 == 0) {
current = prev1;
} else {
current = prev1 + prev2;
}
prev2 = prev1;
prev1 = current;
max_val = Math.Max(max_val, current);
}
return max_val;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.GetMaximumGenerated(7));
}
}By using a few variables instead of an entire list, the Python solution computes each number while keeping track of only the essentials for stepwise calculations and maximum checking.
Time Complexity: O(n) - Sequential iteration.
Space Complexity: O(1) - Memory use is constant.
Approach 3: Default Approach
function getMaximumGenerated(n: number): number {
if (n === 0) {
return 0;
}
const nums: number[] = new Array(n + 1).fill(0);
nums[1] = 1;
for (let i = 2; i < n + 1; ++i) {
nums[i] = i % 2 === 0 ? nums[i >> 1] : nums[i >> 1] + nums[(i >> 1) + 1];
}
return Math.max(...nums);
}func getMaximumGenerated(n int) int {
if n < 2 {
return n
}
nums := make([]int, n+1)
nums[1] = 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]
}
}
return slices.Max(nums)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(n) - One pass through |
| Space-Optimized Iterative Approach | Time Complexity: O(n) - Sequential iteration. |
| Default Approach | – |
Complexity analysis
| 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 |
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.