PREFIX SUM APPROACH || BEATS 100% SUBMISSIONS || JAVA || INTUITIVE
Intuition\n Describe your first thoughts on how to solve this problem. \nPREFIX SUM APPROACH IMPLEMENTED FOR EACH QUERY WHICH DRASTICALLY REDUCES THE TC.\n\n# A
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nPREFIX SUM APPROACH IMPLEMENTED FOR EACH QUERY WHICH DRASTICALLY REDUCES THE TC.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nBRUTE FORCE APPROACH WONT WORK FOR C++ SUNMISSIONS . SO GO AHEAD WITH THIS PREFIX SUM APPROACH WHICH IS MUCH FASTER. IMPLEMENT THE PREFIX SUM CALCULATION FOR EACH QUERY THEN FORM THE FINAL 2D MATRIX BY ADDING THE CONTENT OF EACH ROW WHICH FINALLY FORMS THE ARRAY.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(q*N) + O(N^2)\n\nMUCH FASTER THAN BRUTE FORCE !\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nN*N MATRX IS ALL YOU NEED!\n\n# Code\n```\nclass Solution {\n   public int[][] rangeAddQueries(int n, int[][] queries) {\n   int[][] ans = new int[n][n];\n   for (int[] q : queries) {\n       int row1 = q[0], col1 = q[1], row2 = q[2], col2 = q[3];\n       for (int i = row1; i <= row2; i++) \n       {\n           ans[i][col1] +=1; //MARK THE BEGINNING OF QUERY WITH +1\n           if ((col2 +1) < n ) //CHECK IF THE POSITION LIES WITHIN THAT COL IN THE ARRAY\n           {\n               ans[i][col2 +1] -=1; //IF THE POS EXISTS, MARK IT WITH -1 ... DRY RUN IT FOR BETTER UNDERSTANDING.\n           }\n        }\n    }\n    for(int i=0;i<n;i++)\n    {\n        for(int j=1;j<n;j++)\n        {\n            ans[i][j] += ans[i][j-1]; //FINALLY TRAVERSE THE ARRAY AND ADD THE CONTENT OF EACH ROW IN IT.\n        }\n    }\n   return ans;\n   }\n}\n```
['Array', 'Prefix Sum', 'C++', 'Java', 'Python3']