2256. Minimum Average Difference LeetCode Solution

In this guide, you will get 2256. Minimum Average Difference LeetCode Solution with the best time and space complexity. The solution to Minimum Average Difference problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum Average Difference solution in C++
Minimum Average Difference solution in Java
Minimum Average Difference solution in Python
Additional Resources

2256. Minimum Average Difference LeetCode Solution image

Problem Statement of Minimum Average Difference

You are given a 0-indexed integer array nums of length n.
The average difference of the index i is the absolute difference between the average of the first i + 1 elements of nums and the average of the last n – i – 1 elements. Both averages should be rounded down to the nearest integer.
Return the index with the minimum average difference. If there are multiple such indices, return the smallest one.
Note:

The absolute difference of two numbers is the absolute value of their difference.
The average of n elements is the sum of the n elements divided (integer division) by n.
The average of 0 elements is considered to be 0.

Example 1:

Input: nums = [2,5,3,9,5,3]
Output: 3
Explanation:
– The average difference of index 0 is: |2 / 1 – (5 + 3 + 9 + 5 + 3) / 5| = |2 / 1 – 25 / 5| = |2 – 5| = 3.
– The average difference of index 1 is: |(2 + 5) / 2 – (3 + 9 + 5 + 3) / 4| = |7 / 2 – 20 / 4| = |3 – 5| = 2.
– The average difference of index 2 is: |(2 + 5 + 3) / 3 – (9 + 5 + 3) / 3| = |10 / 3 – 17 / 3| = |3 – 5| = 2.
– The average difference of index 3 is: |(2 + 5 + 3 + 9) / 4 – (5 + 3) / 2| = |19 / 4 – 8 / 2| = |4 – 4| = 0.
– The average difference of index 4 is: |(2 + 5 + 3 + 9 + 5) / 5 – 3 / 1| = |24 / 5 – 3 / 1| = |4 – 3| = 1.
– The average difference of index 5 is: |(2 + 5 + 3 + 9 + 5 + 3) / 6 – 0| = |27 / 6 – 0| = |4 – 0| = 4.
The average difference of index 3 is the minimum average difference so return 3.

Example 2:

Input: nums = [0]
Output: 0
Explanation:
The only index is 0 so return 0.
The average difference of index 0 is: |0 / 1 – 0| = |0 – 0| = 0.

Constraints:

1 <= nums.length <= 105
0 <= nums[i] <= 105

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

2256. Minimum Average Difference LeetCode Solution in C++

class Solution {
 public:
  int minimumAverageDifference(vector<int>& nums) {
    const int n = nums.size();
    int ans = 0;
    int minDiff = INT_MAX;
    long prefix = 0;
    long suffix = accumulate(nums.begin(), nums.end(), 0L);

    for (int i = 0; i < nums.size(); ++i) {
      prefix += nums[i];
      suffix -= nums[i];
      const int prefixAvg = prefix / (i + 1);
      const int suffixAvg = (i == n - 1) ? 0 : suffix / (n - 1 - i);
      const int diff = abs(prefixAvg - suffixAvg);
      if (diff < minDiff) {
        ans = i;
        minDiff = diff;
      }
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

2256. Minimum Average Difference LeetCode Solution in Java

class Solution {
  public int minimumAverageDifference(int[] nums) {
    final int n = nums.length;
    int ans = 0;
    int minDiff = Integer.MAX_VALUE;
    long prefix = 0;
    long suffix = Arrays.stream(nums).asLongStream().sum();

    for (int i = 0; i < nums.length; ++i) {
      prefix += nums[i];
      suffix -= nums[i];
      final int prefixAvg = (int) (prefix / (i + 1));
      final int suffixAvg = (i == n - 1) ? 0 : (int) (suffix / (n - 1 - i));
      final int diff = Math.abs(prefixAvg - suffixAvg);
      if (diff < minDiff) {
        ans = i;
        minDiff = diff;
      }
    }

    return ans;
  }
}
// code provided by PROGIEZ

2256. Minimum Average Difference LeetCode Solution in Python

class Solution:
  def minimumAverageDifference(self, nums: list[int]) -> int:
    n = len(nums)
    ans = 0
    minDiff = inf
    prefix = 0
    suffix = sum(nums)

    for i, num in enumerate(nums):
      prefix += num
      suffix -= num
      prefixAvg = prefix // (i + 1)
      suffixAvg = 0 if i == n - 1 else suffix // (n - 1 - i)
      diff = abs(prefixAvg - suffixAvg)
      if diff < minDiff:
        ans = i
        minDiff = diff

    return ans
 # code by PROGIEZ