Brute Force To 2D Difference Array Tecnique
IntuitionIn this question we are asked to some range updates to the queries given to us.
Brute Force (Accepted)✅.
Optimal Solution (Accepted)✅.
Approach 01 (Bru
# Intuition
In this question we are asked to some range updates to the queries given to us.
- Brute Force (Accepted)✅.
- Optimal Solution (Accepted)✅.

# Approach 01 (Brute Force Approach)
Iterate over the rows and cols for each queries and update the values.


# Code
```java []
class Solution {
    public static void fillans(int[][] ans,int row1,int col1,int row2,int col2){
        for(int i=row1;i<=row2;i++){
            for(int j=col1;j<=col2;j++){
                ans[i][j]+=1;
            }
        }
    }
    public int[][] rangeAddQueries(int n, int[][] queries){
        int[][] ans=new int[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                ans[i][j]=0;
            }
        }        
        for(int i=0;i<queries.length;i++){
            int row1=queries[i][0];
            int col1=queries[i][1];
            int row2=queries[i][2];
            int col2=queries[i][3];
            fillans(ans,row1,col1,row2,col2);
        }
        return ans;
    }
}
```
# Complexity Analysis
- Time complexity: $$O(q*n*n)$$***, where q is queries size and n is matrix size.*** 

- Space complexity: $$O(n*n)$$

# Approach 02 (Optimal Approach)
This is simply a 2-Dimensional Difference Array Problem.

# Code
```java []
class Solution {
    public static void printarr(int[][] arr){
        for(int i=0;i<arr.length;i++){
            for(int j=0;j<arr[i].length;j++){
                System.out.print(arr[i][j]+" ");
            }
            System.out.println("");
        }
    }
    public static void initarr(int[][] arr){
        for(int i=0;i<arr.length;i++){
            for(int j=0;j<arr[i].length;j++){
                arr[i][j]=0;
            }
        }
    }
    public static void updatearr(int[][] queries,int[][] arr){
        int n=arr.length;
        int[][] diff=new int[n+1][n+1];
        initarr(diff);
        for(int i=0;i<queries.length;i++){
            int row1=queries[i][0];
            int col1=queries[i][1];
            int row2=queries[i][2];
            int col2=queries[i][3];
            int val=1;//Change this value if anytime there is a extension of this problem i.e val=queries[i][4] -->if given (here it is 1).
            diff[row1][col1]+=val;
            diff[row1][col2+1]-=val;
            diff[row2+1][col1]-=val;
            diff[row2+1][col2+1]+=val;
        }
        for(int i=0;i<diff.length;i++){
            for(int j=0;j<diff[i].length;j++){
                if(i>0){
                    diff[i][j]+=diff[i-1][j];
                }
                if(j>0){
                    diff[i][j]+=diff[i][j-1];
                }
                if(i>0 && j>0){
                    diff[i][j]-=diff[i-1][j-1];
                }
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                arr[i][j]=diff[i][j];
            }
        }
    }
    public int[][] rangeAddQueries(int n, int[][] queries){
        int[][] arr=new int[n][n];
        initarr(arr);
        updatearr(queries,arr);
        //Just for Debugging Purpose
        //printarr(arr);
        return arr;
    }
}
```
# Complexity Analysis
- Time complexity: $$O(q+n*n)$$***, where q is queries size and n is matrix size.*** 

- Space complexity: $$O(n*n)$$

# Do Upvote⬆️⬆️⬆️.
# Keep Hustling,Keep Coding!!!
['Array', 'Matrix', 'Prefix Sum', 'Java']