algoadvance

Leetcode 1646. Get Maximum in Generated Array

Problem Statement

Given an integer n, you need to create an array named nums where nums[0] = 0 and nums[1] = 1. For each subsequent index i (where 2 <= i <= n), the value of nums[i] is defined as follows:

The task is to return the maximum integer in the array nums generated based on the rules mentioned above.

Clarifying Questions

  1. What should be returned if n is 0?
    • Per the problem, nums[0] = 0, so the maximum value is 0.
  2. What is the upper limit of n?
    • Typically, the constraints are provided, for example, 0 <= n <= 100. We’ll assume the typical constraints unless specified otherwise.

Strategy

  1. Create an array nums of size n+1.
  2. Initialize the first two elements: nums[0] = 0 and nums[1] = 1.
  3. Iterate from 2 through n and fill the array based on whether the index is even or odd:
    • If i is even, set nums[i] = nums[i / 2].
    • If i is odd, set nums[i] = nums[i // 2] + nums[(i // 2) + 1].
  4. Track the maximum value while generating the array.
  5. Return the maximum value found.

Time Complexity

The time complexity of this solution is O(n), since we only need to iterate through the array once to generate it and find the maximum value. The space complexity is also O(n) due to the storage required for the nums array.

Code

Here is the C++ code implementing the above strategy:

#include <vector>
#include <algorithm>  // for std::max

class Solution {
public:
    int getMaximumGenerated(int n) {
        if (n == 0)
            return 0;
        if (n == 1)
            return 1;
        
        std::vector<int> nums(n + 1);
        nums[0] = 0;
        nums[1] = 1;
        int maxVal = 1;  // since nums[1] is maximum at the start
        
        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];
            }
            maxVal = std::max(maxVal, nums[i]);
        }
        
        return maxVal;
    }
};

This solution follows the problem constraints and efficiently computes the desired result using a simple iterative approach.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI