Get Maximum in Generated Array

Easy

Asked by:

10 views

Topics:

Arrays

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum value of `n`? Is it safe to assume `n` will always be non-negative?
If `n` is 0, should I return 0, or is that an invalid input?
Can you clarify the relationship between the index `i` and the generated values `nums[2 * i]` and `nums[2 * i + 1]`? Specifically, are these assignments based on the original, un-updated `nums` array, or the `nums` array as it's being generated iteratively?
Are we optimizing for space complexity as well as time complexity?
If `n` is a large number and generating the entire array becomes memory-intensive, are there alternative approaches I should consider beyond simply building the array?

Brute Force Solution

Approach

We're building a sequence of numbers based on simple rules. The brute force method means we generate the entire sequence step-by-step and then find the largest number within it by simply checking them all.

Here's how the algorithm would work step-by-step:

First, we create an empty list to hold all the numbers we are going to generate.
We know the first two numbers are zero and one so let's add those to our list.
Now, for each spot in the list after those first two, we calculate its value based on its location. If the location is an even number, it equals the value at half its location. If it's an odd number, it equals the sum of the values at locations (its location divided by two) and ((its location divided by two) plus one).
We keep doing this calculation for each position until we have reached the specified length.
Finally, we go through our completed list of numbers and find the biggest one.

Code Implementation

def get_maximum_generated_array(list_length):
    generated_list = []

    # Initialize the first two values of the list.
    generated_list.append(0)
    if list_length > 1:
        generated_list.append(1)

    # Generate the rest of the array based on the rules.
    for i in range(2, list_length):
        # Even indices depend on the value at half the index.
        if i % 2 == 0:

            generated_list.append(generated_list[i // 2])

        # Odd indices are the sum of two previous values.
        else:
            # Calculate index for the previous numbers.
            generated_list.append(generated_list[i // 2] + generated_list[(i // 2) + 1])

    # Find the maximum value in the generated array.
    maximum_value = 0
    for number in generated_list:
        if number > maximum_value:
            maximum_value = number

    return maximum_value

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the array of size n once to generate the numbers. Within the loop, each element is calculated in constant time based on the values of other elements already calculated. After generating the array, the algorithm iterates through it again to find the maximum value, which also takes O(n) time. Therefore, the overall time complexity is O(n) + O(n), which simplifies to O(n).

Space Complexity

O(N) – The algorithm creates a list to store the generated numbers. The size of this list grows linearly with the input 'n', as it stores 'n + 1' numbers (from index 0 to n). Therefore, the auxiliary space required is proportional to 'n'. This results in a space complexity of O(N).

Optimal Solution

Approach

The trick here is to build a special sequence of numbers following specific rules, figuring out the biggest number as you build it. Instead of storing and then searching, find the largest while you generate the sequence.

Here's how the algorithm would work step-by-step:

Start with a sequence of numbers beginning with 0 and 1.
Create the next number in the sequence: if its position in the sequence is even, its value is the same as the number at half that position.
If its position in the sequence is odd, its value is the sum of the numbers at half its position (rounded down) and one position above that.
As you create each new number, keep track of the largest number you've seen so far.
Continue this process until you have generated all the numbers up to the position specified, and return the largest number you kept track of.

Code Implementation

def get_maximum_generated(number):
    if number == 0:
        return 0
    
    generated_array = [0] * (number + 1)
    generated_array[1] = 1
    maximum_value = 1

    for i in range(2, number + 1):
        if i % 2 == 0:
            # Even position: Value is same as half that position
            generated_array[i] = generated_array[i // 2]
            maximum_value = max(maximum_value, generated_array[i])

        else:
            # Odd position: Sum of values at half position and one above
            generated_array[i] = generated_array[i // 2] + generated_array[i // 2 + 1]

            maximum_value = max(maximum_value, generated_array[i])

    return maximum_value

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through a single loop from 2 to n, generating each element of the nums array based on the preceding elements. Each element nums[i] is calculated using simple arithmetic operations (division, addition) and array lookups (nums[i/2] or nums[i/2] + nums[i/2 + 1]), which take constant time, O(1). Therefore, the overall time complexity is directly proportional to n, resulting in O(n).

Space Complexity

O(N) – The algorithm generates a sequence of numbers up to position N, storing each number in an implicit array to calculate subsequent values and track the maximum. This means that auxiliary space scales directly with N, as the numbers generated need to be kept in memory until the entire sequence is processed. Therefore, the space complexity is determined by the size of this generated sequence, which is proportional to N. The auxiliary space used is O(N).

Edge Cases

Case	How to Handle
n = 0	Return 0 since the array will be empty and the maximum value is zero.
n = 1	Return 1 since the array will contain only nums[0] = 0 and nums[1] = 1, and the maximum is 1.
Large n (close to 100)	Ensure the dynamically created array can hold 'n+1' elements without memory issues.
n is an odd number	The loop condition i * 2 + 1 <= n handles odd n correctly, ensuring all necessary elements are generated.
n is an even number	The loop condition i * 2 + 2 <= n handles even n correctly, ensuring all necessary elements are generated.
Integer overflow when calculating i2 or i2+1 for larger n	The constraint n <= 100 prevents integer overflow since the largest index calculated will be 200.
Negative input n	The problem states 0 <= n <= 100, so the input must be validated to not be negative and an error returned otherwise.
When n is just under the maximum limit (n=99 or n=100)	Verify that all indices are accessed correctly and the last valid element is considered when finding the maximum.

n = 0

How to Handle:

Return 0 since the array will be empty and the maximum value is zero.

n = 1

How to Handle:

Return 1 since the array will contain only nums[0] = 0 and nums[1] = 1, and the maximum is 1.

Large n (close to 100)

How to Handle:

Ensure the dynamically created array can hold 'n+1' elements without memory issues.

n is an odd number

How to Handle:

The loop condition i * 2 + 1 <= n handles odd n correctly, ensuring all necessary elements are generated.

n is an even number

How to Handle:

The loop condition i * 2 + 2 <= n handles even n correctly, ensuring all necessary elements are generated.

Integer overflow when calculating i*2 or i*2+1 for larger n

How to Handle:

The constraint n <= 100 prevents integer overflow since the largest index calculated will be 200.

Negative input n

How to Handle:

The problem states 0 <= n <= 100, so the input must be validated to not be negative and an error returned otherwise.

When n is just under the maximum limit (n=99 or n=100)

How to Handle:

Verify that all indices are accessed correctly and the last valid element is considered when finding the maximum.