We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Value at a Given Index in a Bounded Array

Number: 1929

Difficulty: Medium

Paid? No

Companies: TikTok, Apple, Adobe, Yahoo, Bloomberg, Amazon, PayPal, ByteDance, Microsoft

Problem Description

Given three positive integers n, index, and maxSum, construct an array nums of length n such that:

  • Each element in nums is a positive integer.
  • The absolute difference between adjacent elements is at most 1.
  • The sum of all elements does not exceed maxSum.
  • nums[index] is maximized. Return the value of nums[index] in an array that satisfies all the conditions.

Key Insights

  • Use binary search to efficiently determine the maximum possible value at the specified index.
  • For any candidate peak value, compute the total sum required to form the array considering the decreasing sequence from the peak toward both ends.
  • Use arithmetic series formulas to sum the decreasing sequences. When the decreases hit 1, fill the remainder with 1's.
  • Adjust the binary search boundaries based on whether the computed sum is within the maxSum constraint.

Space and Time Complexity

Time Complexity: O(log(maxSum)) due to the binary search over possible peak values.
Space Complexity: O(1) since only a constant amount of space is used.

Solution

We perform a binary search on the possible values for nums[index] (our peak value) between 1 and maxSum. For each candidate value, we determine the minimal total array sum by forming two "pyramids" (one on the left and one on the right of the peak) while ensuring the sequence does not decrease below 1. The sum for each side is computed with arithmetic series formulas; any extra elements beyond those contributing to the natural decrease from the peak are filled with 1's. If the summed value for the candidate is within maxSum, the candidate is valid, and we try a larger value; otherwise, we adjust the binary search to try a smaller peak. Finally, the largest valid peak value is returned.

Code Solutions

def maxValue(n: int, index: int, maxSum: int) -> int:
    # Helper function to calculate the minimum sum for one side (left or right) given a peak value.
    def calc_sum(peak: int, length: int) -> int:
        if peak > length:  # The descending sequence does not reach 1
            return (peak + (peak - length + 1)) * length // 2
        else:  # Part of the sequence reaches 1; fill remaining with 1's
            return (peak + 1) * peak // 2 + (length - peak)
    
    left_len = index         # Number of elements to the left of the peak
    right_len = n - index - 1  # Number of elements to the right of the peak
    
    low, high = 1, maxSum
    while low < high:
        mid = (low + high + 1) // 2  # Use upper mid for binary search
        total = calc_sum(mid, left_len) + calc_sum(mid, right_len) + mid
        if total <= maxSum:
            low = mid
        else:
            high = mid - 1
    return low

# Example usage:
print(maxValue(4, 2, 6))  # Expected output: 2
print(maxValue(6, 1, 10)) # Expected output: 3
← Back to All Questions