Find the weight at (Xi, Yi) after M operations in a Matrix

Given n x n points on cartesian plane, the task is to find the weight at (x_i, y_j) after m operation. x_i, y_j, w denotes the operation of adding weight w at all the points on the lines x = x_i and y = y_j.

Examples:

Input: n = 3, m = 2
0 0 1
1 1 2
x = 1, y = 0
Output: 3
Explanation: Initially, weights are
0 0 0
0 0 0
0 0 0
After 1st operation
2 1 1
1 0 0
1 0 0
After 2nd operation
2 3 1
3 4 2
1 0 0
Clearly, weight at (x₁, y₀) is 3

Input: n = 2, m = 2
0 1 1
1 0 2
x = 1, y = 1
Output: 3

Naive Approach:
Consider a 2-d array arr[n][n] = {0} and perform the given operations and then, retrieve the weight at (x_i, y_j). This approach will take O(n*m) time.

Efficient Approach:

• Consider the arrays arrX[n] = arrY[n] = {0}.
• Redefine the operation x_i, y_j, w as

  arrX[i] += w 
  and
  arrY[j] += w
  

• Find weight at (x_i, y_j) using

  w = arrX[i] + arrY[j]

Below is the implementation of the above approach:

C++








// C++ program to find the // weight at xi and yi    #include <bits/stdc++.h> using namespace std;    // Function to calculate weight at (xFind, yFind) int findWeight(vector<vector<int> >& operations,                int n, int m,                int xFind, int yFind) {     int row[n] = { 0 };     int col[n] = { 0 };        // Loop to perform operations     for (int i = 0; i < m; i++) {            // Updating row         row[operations[i][0]]             += operations[i][2];            // Updating column         col[operations[i][0]]             += operations[i][2];     }        // Find weight at (xi, yj) using     // w = arrX[i] + arrY[j]     int result = row[xFind] + col[yFind];        return result; }    // Driver code int main() {     vector<vector<int> > operations         = {             { 0, 0, 1 },             { 1, 1, 2 }           };     int n = 3,         m = operations.size(),         xFind = 1,         yFind = 0;     cout << findWeight(operations,                        n, m, xFind,                        yFind);     return 0; }

Python3








# Python3 program to find the # weight at xi and yi    # Function to calculate weight at (xFind, yFind) def findWeight(operations, n, m, xFind, yFind) :        row = [ 0 ] * n     col = [ 0 ] * n         # Loop to perform operations     for i in range(m) :             # Updating row         row[operations[i][0]]+= operations[i][2]             # Updating column         col[operations[i][0]]+= operations[i][2]         # Find weight at (xi, yj) using     # w = arrX[i] + arrY[j]     result = row[xFind] + col[yFind]         return result     # Driver code operations = [[ 0, 0, 1 ],[ 1, 1, 2 ]] n = 2 m = len(operations) xFind = 1 yFind = 0 print(findWeight(operations,n, m, xFind, yFind))    # This code is contributed by divyamohan123

Output:

3

Time Complexity: where m is the number of operations