← Back to Index

📚 Maximum Value at a Given Index in a Bounded Array – Java Cheat Sheet

📌 What Is It?

The Maximum Value at a Given Index in a Bounded Array problem involves constructing an array of size n such that the sum of its elements does not exceed maxSum, and the value at a specific index index is maximized. The array values must be positive integers, and the difference between adjacent elements must not exceed 1.

🧱 Pattern Template

class Solution {
    public int maxValue(int n, int index, int maxSum) {
        int left = 1, right = maxSum;

        while (left < right) {
            int mid = (left + right + 1) / 2;

            if (isValid(n, index, maxSum, mid)) {
                left = mid; // Try a larger value
            } else {
                right = mid - 1; // Try a smaller value
            }
        }

        return left;
    }

    private boolean isValid(int n, int index, int maxSum, int value) {
        long sum = value;

        // Calculate left side sum
        if (index > 0) {
            int leftCount = index;
            int leftSum = (value > leftCount) 
                ? (long) (value - 1 + value - leftCount) * leftCount / 2
                : (long) (value - 1 + 1) * value / 2;
            sum += leftSum;
        }

        // Calculate right side sum
        if (index < n - 1) {
            int rightCount = n - index - 1;
            int rightSum = (value > rightCount) 
                ? (long) (value - 1 + value - rightCount) * rightCount / 2
                : (long) (value - 1 + 1) * value / 2;
            sum += rightSum;
        }

        return sum <= maxSum;
    }
}

📊 Time Complexity

• Binary Search: O(log(maxSum)) – Halving the search space for the maximum value.
• Validation: O(1) – Calculating the sum for a given value.
• Overall Complexity: O(log(maxSum)).

✅ Use Cases

• Optimizing values under constraints
• Applications in resource allocation problems

📘 Common LeetCode Problems

• 1802. Maximum Value at a Given Index in a Bounded Array [Medium] Binary Search

🧪 Example: Maximum Value at a Given Index

Input: n = 4, index = 2, maxSum = 6
Output: 2

Explanation:
- The array [1, 2, 2, 1] satisfies the constraints.
- The maximum value at index 2 is 2.

▶️ View Animation

💡 Pro Tips

• Use binary search to efficiently find the maximum value at the given index.
• Edge cases: small arrays, large maxSum, or when the index is at the boundaries.
• Precompute sums for left and right sides to optimize validation.