Beggars Outside Temple

Problem

There are N (N > 0) 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 his faith and ability) to some K beggars sitting next to each other.

Given the amount donated by each devotee to the beggars ranging from i to j index, where 1 <= i <= j <= N, 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.

Example

Input:
N = 5, D = [[1, 2, 10], [2, 3, 20], [2, 5, 25]]

Return: [10, 55, 45, 25, 25]

Explanation:
=> 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] 

Solution

Devotees can denote some K beggars a fixed amount. Devotees can denote money from range l to r index beggars and we have to find the total amount each beggars pot have at the end of the day.

Solution 1: Brute Force 

In Brute Force approach, We just update the beggars pot value from range l to r index with the money the devotees gives to the beggars at each query. Here is the solution looks like:

public class Solution {
    public ArrayList<Integer> solve(int A, ArrayList<ArrayList<Integer>> B) {
        ArrayList<Integer> res = new ArrayList<>();
        for(int i=0;i<=A;i++){
            res.add(0);
        }
        
        for(int i=0;i<B.size();i++){
            int l = B.get(i).get(0);
            int r = B.get(i).get(1);
            int val = B.get(i).get(2);
            
            for(int j=l;j<=r;j++){
                res.set(j,res.get(j)+val);
            }
        }
        res.remove(0);// query is 1 based index.
        return res;
    }
}

Complexity Analysis

• Time Complexity: O(n^2)
• Space Complexity: O(n)
  

Solution 1: Optimal Solution

Our task is to update the value from range l to r for different query in an optimal solution. To update the value for different range in different query we can use the concept of range update query . Using this method we will able to update the range from l to r in O(1). 

We create a Difference Array (D) of size A+1 considering 1 based indexing. Difference array can be used to range update queries "l r val" where l is left index, r is right index and val is value to be added and after all queries you can return original array. 

To update the Difference Array D: Add val to D[l] and subtract it from D[r+1] i.e. we do D[l] += val, D[r+1] -= val. 

After that we sum and update the index value of the whole array. Here is the code looks like:

public class Solution {
    public ArrayList<Integer> solve(int A, ArrayList<ArrayList<Integer>> B) {
        ArrayList<Integer> result = new ArrayList<>();
        for(int i=0;i<=A+1;i++)
        result.add(0);
        for(int i=0;i<B.size();i++){
            int l = B.get(i).get(0);
            int r = B.get(i).get(1);
            int val = B.get(i).get(2);
            result.set(l,result.get(l)+val);
            result.set(r+1,result.get(r+1)-val);
        }
        int sum=0;
        for(int i=0;i<result.size();i++){
            sum+=result.get(i);
            result.set(i,sum);
        }
        result.remove(0);
        result.remove(result.size()-1);
        return result;
    }
}

Complexity Analysis

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