algoadvance

Leetcode 1646. Get Maximum in Generated Array

Problem Statement

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

Return the maximum integer in the array nums.

Clarifying Questions

  1. Q: What is the range of n?
    A: 0 <= n <= 100.

  2. Q: Do we need to consider any special cases for very small n values, like 0 or 1?
    A: Yes, we should handle n = 0 and n = 1 separately since their outputs are straightforward.

  3. Q: Is there any constraint on the time complexity we should aim for?
    A: Given the constraint 0 <= n <= 100, an O(n) solution is efficient enough.

Strategy

  1. Create an array nums of size n + 1.
  2. Initialize nums[0] to 0 and nums[1] to 1.
  3. Loop through indices from 2 to n and generate nums[i] based on the rules:
    • 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. Keep track of the maximum value during the array generation.
  5. Return the maximum value.

Code

public class Solution {
    public int getMaximumGenerated(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;

        int[] nums = new int[n + 1];
        nums[0] = 0;
        nums[1] = 1;

        int maxValue = 1; // Since nums[1] is 1, we can start with this value

        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];
            }
            maxValue = Math.max(maxValue, nums[i]);
        }

        return maxValue;
    }
}

Time Complexity

The time complexity of this solution is O(n), where n is the input integer. This is because we are iterating through each index from 2 to n exactly once and performing constant-time operations for each index.

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