മാട്രിക്സ് ഡയഗണൽ സം ലീറ്റ്കോഡ് പരിഹാരം


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു അഡോബി
അറേ മാട്രിക്സ്

പ്രശ്നം പ്രസ്താവന

മാട്രിക്സ് ഡയഗണൽ സം പ്രശ്‌നത്തിൽ ഒരു ചതുരം മാട്രിക്സ് പൂർണ്ണസംഖ്യകളുടെ നൽകിയിരിക്കുന്നു. അതിന്റെ ഡയഗണലുകളിൽ ഉള്ള എല്ലാ മൂലകങ്ങളുടെയും ആകെത്തുക, അതായത് പ്രാഥമിക ഡയഗണൽ, സെക്കൻഡറി ഡയഗണൽ എന്നിവയിലെ മൂലകങ്ങൾ കണക്കാക്കേണ്ടതുണ്ട്. ഓരോ ഘടകങ്ങളും ഒരു തവണ മാത്രം കണക്കാക്കണം.

ഉദാഹരണം

mat = [[1,2,3],
       [4,5,6],
       [7,8,9]]
25

വിശദീകരണം:

ഡയഗോണലുകളുടെ ആകെത്തുക: 1 + 5 + 9 + 3 + 7 = 25
മാറ്റ് [1] [1] = 5 എന്ന ഘടകം ഒരു തവണ മാത്രം കണക്കാക്കുന്നത് ശ്രദ്ധിക്കുക

mat = [[1,1,1,1],
       [1,1,1,1],
       [1,1,1,1],
       [1,1,1,1]]
8

വിശദീകരണം:

Diagonals sum: (1+1+1+1)+(1+1+1+1)=8.

സമീപനം

മാട്രിക്സ് ഡയഗണൽ സം ലീറ്റ്കോഡ് പരിഹാരം

തന്നിരിക്കുന്ന സ്ക്വയർ മാട്രിക്സിൽ നമ്മൾ ഡയഗണൽ ഘടകങ്ങൾ ചേർത്ത് അതിന്റെ തുക തിരികെ നൽകണം.
ഡയഗണൽ ഘടകങ്ങൾക്കായുള്ള മാട്രിക്സിലെ സൂചികകളുടെ പാറ്റേൺ എന്താണെന്ന് നോക്കാം. ആദ്യം നമ്മൾ പ്രാഥമിക ഡയഗണലിൽ കാണുന്നുവെങ്കിൽ, അതിന്റെ ആദ്യ ഘടകം സൂചിക i = 0, j = 0, അടുത്ത ഘടകം ഓണാണ് (i + 1, j + 1). അതുപോലെ അവസാന ഘടകം സൂചികയിലായിരിക്കും (n-1, n-1), ഇവിടെ n എന്നത് തന്നിരിക്കുന്ന സ്ക്വയർ മാട്രിക്സിന്റെ വീതിയാണ്. ഈ ഡയഗണലിലെ എല്ലാ സൂചികകൾക്കും i = j ഉണ്ട്.
അതിനാൽ നമുക്ക് ഈ ഡയഗോണലിന് മുകളിലൂടെ ഒരു ലൂപ്പിൽ ആവർത്തിക്കാം:

1. i = 0, j = 0 എന്നിവ സമാരംഭിക്കുക.
2. ഞാൻ ഒരു ലൂപ്പ് പ്രവർത്തിപ്പിക്കുക
3. നിലവിലെ ഘടകം ചേർക്കുക. I, j എന്നിവ രണ്ടും 1 വർദ്ധിപ്പിക്കുക.

ദ്വിതീയ ഡയഗണലിനായി ഇപ്പോൾ നോക്കാം. ആദ്യ വരിയിലെ ആദ്യ മൂലകത്തിന്റെ സൂചിക i = 0, j = n-1. അടുത്ത ഘടകം (i + 1.j-1) ആണ്. അതുപോലെ അവസാന ഘടകം (n-1,0) ആണ്.
അതിനാൽ നമുക്ക് ഈ ഡയഗോണലിന് മുകളിലൂടെ ലൂപ്പിൽ ആവർത്തിക്കാം:

1. i = 0, j = n-1 എന്നിവ സമാരംഭിക്കുക.
2. ഞാൻ ഒരു ലൂപ്പ് പ്രവർത്തിപ്പിക്കുക = 0.
3. നിലവിലെ ഘടകം ചേർക്കുക (അത് പ്രാഥമിക ഡയഗണലിൽ കിടക്കുന്നില്ലെങ്കിൽ, അതായത്. I == j). I 1 ഉം വർദ്ധനവ് j ഉം 1 ഉം വർദ്ധിപ്പിക്കുക.

രണ്ട് പ്രവർത്തനത്തിനും ശേഷം അവസാനം തുക നൽകുക.

നടപ്പിലാക്കൽ

മാട്രിക്സ് ഡയഗണൽ സം ലീറ്റ്കോഡ് പരിഹാരത്തിനായുള്ള സി ++ പ്രോഗ്രാം

#include <bits/stdc++.h>
using namespace std;

int diagonalSum(vector<vector<int>>& mat) 
{
    int n=mat.size();

    int sum=0;
    int i=0,j=0;

    while(i<n)
    {
        sum+=mat[i][j];
        i++;
        j++;
    }

    i=0;
    j=n-1;

    while(i<n)
    {
        if(i!=j)   sum+=mat[i][j];
        i++;
        j--;
    }

    return sum;
}

int main() 
{
    vector<vector<int>> mat={
            {1,2,3},
            {4,5,6},
            {7,8,9}  
    };
   
    cout<<diagonalSum(mat)<<endl;

  return 0; 
}
25

മാട്രിക്സ് ഡയഗണൽ സം ലീറ്റ്കോഡ് പരിഹാരത്തിനായുള്ള ജാവ പ്രോഗ്രാം

import java.lang.*;

class Rextester
{  
    public static int diagonalSum(int[][] mat) 
    {
        int n=mat.length;
        
        int sum=0;
        int i=0,j=0;
        
        while(i<n)
        {
            sum+=mat[i][j];
            i++;
            j++;
        }
        
        i=0;
        j=n-1;
        
        while(i<n)
        {
          if(i!=j)   sum+=mat[i][j];
            
            i++;
            j--;
        }
        
        return sum;
        
    }
    
    public static void main(String args[])
    {
       int[][] mat={
            {1,2,3},
            {4,5,6},
            {7,8,9}  
        };
    
       System.out.println(diagonalSum(mat));
   
    }
}
25

മാട്രിക്സ് ഡയഗണൽ സം ലീറ്റ്കോഡ് പരിഹാരത്തിനായുള്ള സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N): N ^ 2 ഘടകങ്ങളുള്ള സ്ക്വയർ മാട്രിക്സിന്റെ വലുപ്പമാണ് ഇവിടെ N. ഞങ്ങൾ രണ്ട് ഡയഗണൽ മൂലകങ്ങളിലും മാത്രമേ സഞ്ചരിക്കുന്നതിനാൽ, സമയ സങ്കീർണ്ണത ഡയഗണലുകളിൽ (2 * N), അതായത് O (N) ഉള്ള മൂലകങ്ങളുടെ എണ്ണത്തിന് തുല്യമായിരിക്കും.

ബഹിരാകാശ സങ്കീർണ്ണത 

O (1): ഞങ്ങൾ അധിക മെമ്മറിയൊന്നും ഉപയോഗിക്കാത്തതിനാൽ ഇവിടെ സ്ഥല സങ്കീർണ്ണത സ്ഥിരമാണ്.