Horje
Find the sum of diagonals passing through given coordinates for Q query

Given a 2D matrix of size N x M and Q queries where each query represents a coordinate (x, y) of the matrix, the task is to find the sum of all elements lying in the diagonals that pass through the given point.

Examples:

Input: N = 4, M = 4, mat[][] = {{1, 2, 2, 1}, {2, 4, 2, 4}, {2, 2, 3, 1}, {2, 4, 2, 4}}, query = { {0, 0}, {3, 1}, {3, 3} }     
Output:  12, 13, 12  
Explanation: 
For query 1, The sum of all diagonal elements from (0, 0) is 1 + 4 + 3 + 4 = 12
For query 2, The sum of all diagonal elements from (3, 1) is 2 + 4 + 3 + 4 = 13
For query 3, The sum of all diagonal elements from (3, 3) is 4 + 3 + 4 + 1 = 12

Input: N = 3, M = 4, mat[][] = {{1, 0, 1}, {0, 1, 1}, {1, 1, 0}}, query = {{1, 1}, {2, 1}}
Output: 4, 2

 

Naive approach: The simple way to solve the problem is as follows:

  • For each query run a loop to calculate the sum of the left inclined diagonal that passes through (x, y).
  • Run another loop to calculate the sum of the right inclined diagonal that passes (x, y).
  • In the calculation of these two side diagonals, we counted (x, y) twice. So now subtract that from the summation of both diagonal sums.

Time Complexity: O(Q * N * M)
Auxiliary Space: O(1)

Efficient Approach: The problem can be solved efficiently based on the following idea:

Pre-compute the left inclined and right inclined diagonal sums and store it in such a way that can be easily accessed and utilized for all values of (x, y)

In any matrix of size N x M, the total number of left inclined diagonal or right inclined diagonal is always N + M – 1. So create two vectors of size (N + M – 1) to store the sum of every that particular type of diagonal in the respective vector.

The value of (i+j) along right inclined diagonals are equals and (N-i+j-1) along left inclined diagonals are equal. So these values can be used as the indices for storing the sum of that diagonal.

Illustrations:

In this 3 x 4 matrix:

         1     2     3     4
         ________________

  1  | A00  A01  A02  A03

  2  | A10  A11  A12  A13

  3  | A20  A21  A22  A23

  • For (1, 1) The output will be (A00 + A11 + A22 + A20 + A02).
  • For (2, 1) The output will be (A10 + A21 + A12 + A03)
  • For right inclined diagonals
    • Start from top left and keep covering all diagonals till bottom right.
    • According to above illustration the ith right inclined diagonal contains following elements
      • 0th diagonal = A00
      • 1st diagonal  = A10+ A01
      • 2nd diagonal = A20 + A11 + A02
      • 3rd diagonal = A21 + A12 + A03
      • 4th diagonal = A22 + A13
      • 5th diagonal = A23
    • Storing the above values in the vector right_inclined_digsum in the same order.
    • In order to check the (x, y) element belonging to which diagonal just observe that Aij belongs to (i + j)th right inclined diagonal.
  • For left inclined diagonals
    • Start from bottom left and keep covering all diagonals till top right
    • According to above illustration the ith left inclined diagonal contains following elements
      • 0th diagonal = A20
      • 1st diagonal = A10 + A21
      • 2nd diagonal = A00 + A11 + A22
      • 3rd diagonal = A01 + A12 + A23
      • 4th diagonal = A02 + A13
      • 5th diagonal = A03
    • Storing the above values in the vector left_inclined_digsum in the same order.
    • In order to check the (x, y) element belongs to which diagonal just observe that Aij belongs to (N – i + j – 1)th left inclined diagonal.
  • After precomputing all these data, for each query of (x, y) output 
    •  right_inclined_digsum[x + y] + left_inclined_digsum[N – x + y – 1] – arr[x][y]

Follow the steps mentioned below to implement the idea:

  • Create two vectors to store the diagonal sums (one for left inclined and the other for right inclined).
  • Store the sum of the diagonals in the indices as shown above.
  • Find the diagonals of which the current coordinate is a part.
  • Calculate the sum as shown above.

Below is the implementation of the above approach.

C++

// C++ code for the above approach:
 
#include <bits/stdc++.h>
using namespace std;
const int n = 4;
const int m = 4;
 
// Function for diagonal sum
int diagonal_sum(vector<vector<int> >& arr,
                 vector<int>& right_inclined_digsum,
                 vector<int>& left_inclined_digsum, int n,
                 int x, int y)
{
    // To make it compatible with 0 based indexing
    int a = (n - x) + y - 1;
    int b = x + y;
    int sum = right_inclined_digsum[b]
              + left_inclined_digsum[a] - arr[x][y];
    return sum;
}
 
// Precomputaion
void precompute(int n, int m, vector<vector<int> > arr,
                vector<int>& right_inclined_digsum,
                vector<int>& left_inclined_digsum)
{
 
    // To cover all diagonals of (/) type
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            right_inclined_digsum[i + j] += arr[i][j];
        }
    }
 
    // To cover all diagonals of (\) type
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < m; j++) {
            left_inclined_digsum[n - 1 - i + j]
                += arr[i][j];
        }
 
        // precomputaion done
    }
}
 
void solve(vector<vector<int> >& arr, int Q,
           vector<pair<int, int> >& query)
{
    vector<int> right_inclined_digsum(n + m - 1, 0);
    vector<int> left_inclined_digsum(n + m - 1, 0);
 
    // Function for precomputation
    precompute(n, m, arr, right_inclined_digsum,
               left_inclined_digsum);
 
    // Iterator for these coordinates
    int it = 0;
 
    while (Q--) {
        int x = query[it].first;
        int y = query[it].second;
        cout << diagonal_sum(arr, right_inclined_digsum,
                             left_inclined_digsum, n, x, y)
             << "\n";
        it++;
    }
}
// Drivers code
int main()
{
    vector<vector<int> > arr = { { 1, 2, 2, 1 },
                                 { 2, 4, 2, 4 },
                                 { 2, 2, 3, 1 },
                                 { 2, 4, 2, 4 } };
    int Q = 3;
 
    // Defining coordinates for each query
    vector<pair<int, int> > query;
    query.push_back({ 0, 0 });
    query.push_back({ 3, 1 });
    query.push_back({ 3, 3 });
 
    // Function call
    solve(arr, Q, query);
    return 0;
}

Java

// Java code to implement the approach
import java.io.*;
import java.util.*;
 
class GFG {
    static int n = 4;
    static int m = 4;
 
    // Function for diagonal sum
    static int diagonal_sum(int[][] arr,
                            int[] right_inclined_digsum,
                            int[] left_inclined_digsum,
                            int n, int x, int y)
    {
        // To make it compatible with 0 based indexing
        int a = (n - x) + y - 1;
        int b = x + y;
        int sum = right_inclined_digsum[b]
                  + left_inclined_digsum[a] - arr[x][y];
        return sum;
    }
 
    // Precomputaion
    static void precompute(int n, int m, int[][] arr,
                           int[] right_inclined_digsum,
                           int[] left_inclined_digsum)
    {
 
        // To cover all diagonals of (/) type
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                right_inclined_digsum[i + j] += arr[i][j];
            }
        }
 
        // To cover all diagonals of (\) type
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < m; j++) {
                left_inclined_digsum[n - 1 - i + j]
                    += arr[i][j];
            }
            // precomputaion done
        }
    }
 
    static void solve(int[][] arr, int Q, int[][] query)
    {
        int[] right_inclined_digsum = new int[n + m - 1];
        int[] left_inclined_digsum = new int[n + m - 1];
 
        // Function for precomputation
        precompute(n, m, arr, right_inclined_digsum,
                   left_inclined_digsum);
 
        // Iterator for these coordinates
        int it = 0;
 
        while (Q-- > 0) {
            int x = query[it][0];
            int y = query[it][1];
            System.out.println(diagonal_sum(
                arr, right_inclined_digsum,
                left_inclined_digsum, n, x, y));
            it++;
        }
    }
    // Driver code
    public static void main(String[] args)
    {
        int[][] arr = { { 1, 2, 2, 1 },
                        { 2, 4, 2, 4 },
                        { 2, 2, 3, 1 },
                        { 2, 4, 2, 4 } };
        int Q = 3;
 
        // Defining coordinates for each query
        int[][] query = new int[3][2];
        query[0] = new int[] { 0, 0 };
        query[1] = new int[] { 3, 1 };
        query[2] = new int[] { 3, 3 };
 
        // Function call
        solve(arr, Q, query);
    }
}
// This code is contributed by Karandeep1234

Python3

# Python code for the above approach
 
 
n = 4
m = 4
right_inclined_digsum = [0]*(n+m-1)
left_inclined_digsum = [0]*(n+m-1)
# Function for diagonal sum
 
 
def diagonal_sum(arr, right_inclined_digsum, left_inclined_digsum, n, x, y):
    # To make it compatible with 0 based indexing
    a = (n-x)+y-1
    b = x+y
    summ = right_inclined_digsum[b]+left_inclined_digsum[a]-arr[x][y]
    return summ
# Precomputaion function
 
 
def precompute(n, m, arr, right_inclined_digsum, left_inclined_digsum):
    # To cover all diagonals of (/) type
    for i in range(n):
        for j in range(m):
            right_inclined_digsum[i+j] += arr[i][j]
    # To cover all diagonals of (\) type
    for i in range(n-1, -1, -1):
        for j in range(0, m):
            left_inclined_digsum[n-1-i+j] += arr[i][j]
    # precomputaion done
 
 
def solve(arr, Q, query):
    # Function for precomputation
    precompute(n, m, arr, right_inclined_digsum, left_inclined_digsum)
    # Iterator for these coordinates
    it = 0
    while(Q > 0):
        x = query[it][0]
        y = query[it][1]
        print(diagonal_sum(arr, right_inclined_digsum,
                           left_inclined_digsum, n, x, y))
        it += 1
        Q -= 1
 
 
# Drivers code
if __name__ == "__main__":
    arr = [[1, 2, 2, 1], [2, 4, 2, 4], [2, 2, 3, 1], [2, 4, 2, 4]]
    Q = 3
    # Defining coordinates for each query
    query = []
    query.append([0, 0])
    query.append([3, 1])
    query.append([3, 3])
    # Function call
    solve(arr, Q, query)
" Code is written by RAJAT KUMAR [GLAU] "

C#

// C# code for the above approach:
 
using System;
using System.Collections.Generic;
 
class pair {
    public int first, second;
    public pair(int x, int y)
    {
        this.first = x;
        this.second = y;
    }
}
 
class GFG {
    static int n = 4;
    static int m = 4;
 
    // Function for diagonal sum
    static int diagonal_sum(int[, ] arr,
                            List<int> right_inclined_digsum,
                            List<int> left_inclined_digsum,
                            int n, int x, int y)
    {
        // To make it compatible with 0 based indexing
        int a = (n - x) + y - 1;
        int b = x + y;
        int sum = right_inclined_digsum[b]
                  + left_inclined_digsum[a] - arr[x, y];
        return sum;
    }
 
    // Precomputaion
    static void precompute(int n, int m, int[, ] arr,
                           List<int> right_inclined_digsum,
                           List<int> left_inclined_digsum)
    {
 
        // To cover all diagonals of (/) type
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                right_inclined_digsum[i + j] += arr[i, j];
            }
        }
 
        // To cover all diagonals of (\) type
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < m; j++) {
                left_inclined_digsum[n - 1 - i + j]
                    += arr[i, j];
            }
 
            // precomputaion done
        }
    }
 
    static void solve(int[, ] arr, int Q, List<pair> query)
    {
        List<int> right_inclined_digsum = new List<int>();
        List<int> left_inclined_digsum = new List<int>();
 
        for (int i = 0; i < n + m - 1; i++) {
            right_inclined_digsum.Add(0);
            left_inclined_digsum.Add(0);
        }
 
        // Function for precomputation
        precompute(n, m, arr, right_inclined_digsum,
                   left_inclined_digsum);
 
        // Iterator for these coordinates
        int it = 0;
 
        while (Q > 0) {
            Q--;
            int x = query[it].first;
            int y = query[it].second;
            Console.WriteLine(diagonal_sum(
                arr, right_inclined_digsum,
                left_inclined_digsum, n, x, y));
            it++;
        }
    }
    // Drivers code
    public static void Main(string[] args)
    {
        int[, ] arr = { { 1, 2, 2, 1 },
                        { 2, 4, 2, 4 },
                        { 2, 2, 3, 1 },
                        { 2, 4, 2, 4 } };
        int Q = 3;
 
        // Defining coordinates for each query
        List<pair> query = new List<pair>();
        query.Add(new pair(0, 0));
        query.Add(new pair(3, 1));
        query.Add(new pair(3, 3));
 
        // Function call
        solve(arr, Q, query);
    }
}
 
// This code is contributed by phasing17

Javascript

<script>
    // JavaScript code for the above approach
    let n = 4;
    let m = 4;
    let right_inclined_digsum = new Array(n + m - 1).fill(0);
    let left_inclined_digsum = new Array(n + m - 1).fill(0);
     
    // Function for diagonal sum
    function diagonal_sum(arr,
        right_inclined_digsum,
        left_inclined_digsum, n,
        x, y)
        {
         
        // To make it compatible with 0 based indexing
        let a = (n - x) + y - 1;
        let b = x + y;
        let sum = right_inclined_digsum[b]
            + left_inclined_digsum[a] - arr[x][y];
        return sum;
    }
 
    // Precomputaion
    function precompute(n, m, arr,
        right_inclined_digsum,
        left_inclined_digsum) {
 
        // To cover all diagonals of (/) type
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < m; j++) {
                right_inclined_digsum[i + j] += arr[i][j];
            }
        }
 
        // To cover all diagonals of (\) type
        for (let i = n - 1; i >= 0; i--) {
            for (let j = 0; j < m; j++) {
                left_inclined_digsum[n - 1 - i + j]
                    += arr[i][j];
            }
 
            // precomputaion done
        }
    }
 
    function solve(arr, Q, query)
    {
 
        // Function for precomputation
        precompute(n, m, arr, right_inclined_digsum,
            left_inclined_digsum);
 
        // Iterator for these coordinates
        let it = 0;
 
        while (Q--) {
            let x = query[it][0];
            let y = query[it][1];
            document.write(diagonal_sum(arr, right_inclined_digsum,
                left_inclined_digsum, n, x, y)
                + '</br>');
            it++;
        }
    }
     
    // Drivers code
    let arr = [[1, 2, 2, 1],
    [2, 4, 2, 4],
    [2, 2, 3, 1],
    [2, 4, 2, 4]];
    let Q = 3;
 
    // Defining coordinates for each query
    let query = [];
    query.push([0, 0]);
    query.push([3, 1]);
    query.push([3, 3]);
 
    // Function call
    solve(arr, Q, query);
 
// This code is contributed by Potta Lokesh
</script>

Output

12
13
12

Time Complexity: O(Q + N * M)
Auxiliary Space: O(N + M)


 


Reffered: https://www.geeksforgeeks.org

Analysis Of Algorithms

Related
Prove that a problem consisting of Clique and Independent Set is NP Complete Prove that a problem consisting of Clique and Independent Set is NP Complete
Prove that Dense Subgraph is NP Complete by Generalisation Prove that Dense Subgraph is NP Complete by Generalisation
Construct String with given frequency and minimum continuous occurrence of a letter Construct String with given frequency and minimum continuous occurrence of a letter
Check if Array elements can be made consecutive by performing given operations Check if Array elements can be made consecutive by performing given operations
For each value in [1, N] find Minimum element present in all Subarray of that size For each value in [1, N] find Minimum element present in all Subarray of that size

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 12



 

Horje