LeetCode — Get Maximum in Generated Array

Problem Link: https://leetcode.com/problems/get-maximum-in-generated-array/

Photo by Clément Hélardot on Unsplash

Problem Description: You are given an integer n. An 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 3.

Approach Used: Dynamic Programming

Explanation: In this question, we simply need to find the value at each index and check if it is the maximum value in an array or not. Since value at the current index depends on values at some previous index/indexes. We can calculate those values whenever needed. But the problem with that is since some indexes will be overlapping, we will end up calculating them multiple times. For e.g. in the above example nums[2] is being used in both nums[3] and nums[4] so it will calculated multiple times. To avoid this we can store these values so that they can be directly accessed whenever needed. Since the size of n can only go up to 100, the size of the array will not cause any space problems.

Code: (Java)

public int getMaximumGeneratedDp(int n){
        //base case
        if(n==0 || n==1)
            return n;
        
        //initializing answer (to a value which will always be minimum)
        int ans=-1;
        
        //nth number will come at nth position (so starting from 0 we need n+1 memory) 
        int[] dp = new int[n+1];
        //base case values
        dp[0]=0;
        dp[1]=1;
        
        for(int i=2; i<=n; i++){
            //case 1
            if(i%2==0)
                dp[i] = dp[i/2];
            //case 2
            else
                dp[i] = dp[(i+1)/2]+dp[(i-1)/2];
            
            //updating ans
            ans = Math.max(ans,dp[i]);
        }
        //returning maximum value
        return ans;
    }
    public int getMaximumGenerated(int n) {
        return getMaximumGeneratedDp(n);        
    }

Complexity:
Space Complexity: O(n). Since we store values in an array of size n.
Time Complexity: O(n). Since we loop through all numbers till n exactly once to calculate their values.
Here n is the input provided to us.