LeetCode 2256: Minimum Average Difference Solution
Master LeetCode problem 2256 (Minimum Average Difference), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
2256. Minimum Average Difference
Problem Explanation
Explanation
To solve this problem, we can iterate through each index i in the array nums. For each index i, we calculate the average of the first i+1 elements and the average of the last n-i-1 elements. We then calculate the absolute difference between these two averages and find the index with the minimum average difference.
We can optimize this process by precomputing the cumulative sums of the array nums. This allows us to calculate the sum of any subarray in constant time. With the cumulative sum array, we can calculate the sum of the first i+1 elements and the sum of the last n-i-1 elements efficiently.
The time complexity of this approach is O(n) since we iterate through the array once to compute the cumulative sum and once again to find the index with the minimum average difference. The space complexity is O(n) to store the cumulative sum array.
Solution Code
class Solution {
public int minAverage(int[] nums) {
int n = nums.length;
int[] prefixSum = new int[n];
prefixSum[0] = nums[0];
for (int i = 1; i < n; i++) {
prefixSum[i] = prefixSum[i - 1] + nums[i];
}
int minIndex = 0;
int minDiff = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
int sumLeft = prefixSum[i];
int sumRight = prefixSum[n - 1] - prefixSum[i];
int avgLeft = i == 0 ? nums[i] : sumLeft / (i + 1);
int avgRight = sumRight / (n - i - 1);
int diff = Math.abs(avgLeft - avgRight);
if (diff < minDiff || (diff == minDiff && i < minIndex)) {
minDiff = diff;
minIndex = i;
}
}
return minIndex;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 2256 (Minimum Average Difference)?
This page provides optimized solutions for LeetCode problem 2256 (Minimum Average Difference) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 2256 (Minimum Average Difference)?
The time complexity for LeetCode 2256 (Minimum Average Difference) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 2256 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2256 in Java, C++, or Python.