Continuous Sum Query (Beggars Outside Temple Problem)

Problem Description

There are A beggars sitting in a row outside a temple. Each beggar initially has an empty pot. When the devotees come to the temple, they donate some amount of coins to these beggars. Each devotee gives a fixed amount of coin(according to their faith and ability) to some K beggars sitting next to each other.

Given the amount P donated by each devotee to the beggars ranging from L to R index, where 1 <= L <= R <= A, find out the final amount of money in each beggar's pot at the end of the day, provided they don't fill their pots by any other means. For ith devotee B[i][0] = L, B[i][1] = R, B[i][2] = P, given by the 2D array B

Problem Constraints

1 <= A <= 2 * 10^5
1 <= L <= R <= A
1 <= P <= 10^3
0 <= len(B) <= 10^5

Input Format

The first argument is a single integer A.
The second argument is a 2D integer array B.

Output Format

Return an array(0 based indexing) that stores the total number of coins in each beggars pot.

Example Input

Input 1:
A = 5
B = [[1, 2, 10], [2, 3, 20], [2, 5, 25]]

Example Output

Output 1:
10 55 45 25 25

Example Explanation

Explanation 1:
First devotee donated 10 coins to beggars ranging from 1 to 2. Final amount in each beggars pot after first devotee: [10, 10, 0, 0, 0]
Second devotee donated 20 coins to beggars ranging from 2 to 3. Final amount in each beggars pot after second devotee: [10, 30, 20, 0, 0]
Third devotee donated 25 coins to beggars ranging from 2 to 5. Final amount in each beggars pot after third devotee: [10, 55, 45, 25, 25]

Output

Java

import java.util.Arrays;
 
public class BeggarsOptimized {
    public static int[] beggars(int A, int[][] B) {
        int[] result = new int[A];
        for (int i = 0; i < B.length; i++) {
            result[B[i][0] - 1] += B[i][2];
            if (B[i][1] < A) {
                result[B[i][1]] -= B[i][2];
            }
        }
        for (int i = 1; i < A; i++) {
            result[i] += result[i - 1];
        }
        return result;
    }
 
    public static void main(String[] args) {
        int A = 5;
        int[][] B = {{1, 2, 10}, {2, 3, 20}, {2, 5, 25}};
        System.out.println(Arrays.toString(beggars(A, B))); // Output: [10, 55, 45, 25, 25]
    }
}

Python

def beggars_optimized(A, B):
    result = [0] * A
    for i in range(len(B)):
        result[B[i][0] - 1] += B[i][2]
        if B[i][1] < A:
            result[B[i][1]] -= B[i][2]
    for i in range(1, A):
        result[i] += result[i - 1]
    return result
 
# Test the function with the given example
A = 5
B = [[1, 2, 10], [2, 3, 20], [2, 5, 25]]
print(beggars_optimized(A, B))  # Output: [10, 55, 45, 25, 25]

JavaScript

function beggarsOptimized(A, B) {
    let result = new Array(A).fill(0);
    for (let i = 0; i < B.length; i++) {
        result[B[i][0] - 1] += B[i][2];
        if (B[i][1] < A) {
            result[B[i][1]] -= B[i][2];
        }
    }
    for (let i = 1; i < A; i++) {
        result[i] += result[i - 1];
    }
    return result;
}
 
// Test the function with the given example
let A = 5;
let B = [[1, 2, 10], [2, 3, 20], [2, 5, 25]];
console.log(beggarsOptimized(A, B));  // Output: [10, 55, 45, 25, 25]

Subarray Sum Equals K Max Sum Contiguous Subarray