Mean of range in array

Intuition

Answering thousands of range-sum queries naively by re-summing the subarray each time would cost O(N) per query. Instead, precompute a prefix sum array in a single O(N) pass so that any range sum [l, r] is retrieved in O(1) as `prefixSum[r] - prefixSum[l-1]`. The mean is then the floor integer division of that sum by the number of elements `(r - l + 1)`.

Algorithm

1Build prefix sum: `sum[0] = arr[0]`. For i from 1 to N-1: `sum[i] = sum[i-1] + arr[i]`.
2For each query [l, r]: compute `total = sum[r] - (l > 0 ? sum[l-1] : 0)`.
3Compute `count = r - l + 1`.
4Append `total / count` (integer division) to the result list.
5Return the result list after processing all queries.

Example Walkthrough

Input: arr = [1, 2, 3, 4, 5], queries = [[0, 2], [1, 3], [0, 4]]

1.Build prefix sum: [1, 3, 6, 10, 15].
2.Query [0,2]: total = sum[2] = 6, count = 3 → mean = 6/3 = 2.
3.Query [1,3]: total = sum[3] - sum[0] = 10 - 1 = 9, count = 3 → mean = 9/3 = 3.
4.Query [0,4]: total = sum[4] = 15, count = 5 → mean = 15/5 = 3.

Output: [2, 3, 3]

Common Pitfalls

•When l = 0, there is no `sum[l-1]` to subtract — guard this with a conditional (use 0 instead).
•Java integer division already floors the result, so no explicit floor call is needed.
•Do not use long arithmetic unless the array values and length guarantee overflow — for typical GFG constraints int is sufficient.

Mean of range in array.java

Java


// Approach: We can solve this efficiently by precomputing the prefix sums of the array.
// This allows us to answer each range query in O(1) time. For each query [l, r], the sum
// of the elements in the range is `sum[r] - sum[l - 1]` (handling `l=0` as a special case).
// The number of elements in the range is `r - l + 1`. The mean is the floor integer division 
// of the total sum by the count of elements.
//
// Time: O(N + Q), where N is the size of the array (to build prefix sum) and Q is the number of queries.
// Space: O(N) to store the prefix sum array.

import java.util.*;

class Solution {

    public ArrayList<Integer> findMean(int[] arr, int[][] queries) {
        ArrayList<Integer> res = new ArrayList<>();
        int sum[] = new int[arr.length];
        sum[0] = arr[0];

        for (int i = 1; i < arr.length; i++) {
            sum[i] = sum[i - 1] + arr[i];
        }

        for (int[] querie : queries) {
            int l = querie[0]; //left
            int r = querie[1]; //right
            int total = sum[r] - (l > 0 ? sum[l - 1] : 0);
            int count = (r + 1) - l;
            res.add(total / count);
        }
        return res;
    }
}

Was this solution helpful?