Mirror Diagonals

Easy
0/40
profile
Contributed by
5 upvotes
Asked in companies
AdobeWatchGuard Technologies

Problem statement

Ninja has a 2D array ‘arr’ with ‘N’ rows and each row contains ‘N’ elements. Your task is to check if the left diagonal numbers and right diagonal numbers are equal in the 2D Array.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains one integer ‘N’ denoting the number of rows and columns.

Each of the next ‘N’ lines contains ‘N’ integers separated by a single space.

Output Format:

For each test case, print ‘true’  if the diagonals numbers are equal, else print ‘false’.

The output of each test case will be printed in a separate line.

Note:

You do not need to input or print anything, as it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 100
- 10 ^ 9 <= arr[i][j] <= 10 ^ 9

Where ‘T’ is the total number of test cases, ‘N’ is the number of rows and columns, arr[i][j] represents the elements of the 2D Array.

Sample Input 1:

3
4
1 2 3 1
3 2 2 4
5 4 4 7
9 3 3 9
1
5
3
1 2 -3
3 1 3
5 4 6

Sample Output 1:

true
true
false

Explanation of Sample Input 1:

Test case 1:
We can get the left diagonal as [ 1 , 2 , 4 , 9 ] and the right diagonal as [ 1 , 2 , 4 , 9 ]. As both are the same , so we print True.

Test case 2:
We can get the left diagonal as [ 1 ] and the right diagonal as [ 1 ]. As both are the same,  so we print True.

Test case 3:
We can get the left diagonal as [ 1 , 1 , 6 ] and the right diagonal as [ -3 , 1 , 5 ]. As both are not the same, so we print False.

Sample Input 2:

1
3
-1 2 -1
4 -7 8
8 8  8

Sample Output 2:

true

Explanation of Sample Input 2:

Test case 1:
We can get the left diagonal as [ -1 , -7 , 8 ] and the right diagonal as [ -1 , -7 , 8 ]. As both are the same, so we print True.
Hint

Travel only throw the diagonals

Approaches (1)
Greedy Approach

We only need to check whether the diagonal elements are equal or not. So we can only iterate over the main diagonal elements and do the checking.

For the left diagonal, 'i' should be equal to ‘j’ and for the right diagonal, sum of 'i' and ‘j’ must be ‘N’ - 1 where 'i' is the row index and 'j' is the column index. For the left diagonal, we can use ‘i’ in place of ‘j’ as they both are the same and for the right diagonal, using the relationship we can find ‘j’ that is equal to “N - 1 - i”

As we know the exact relationship between the indexes, we can only travel through those particular indexes and check the elements.

 

Algorithm:

 

  • Run a loop “i”  =  0 to “N” for the diagonal elements
    • Compare arr[i][i] with arr[i][N - 1 - i]
      • If they are same,we can continue
      • Else return false.
  • Return true

 

Time Complexity

O(N) where N is the number of rows and column of the matrix

 

As we only need to iterate through the diagonal elements, so if there are N rows and each row contains one diagonal element, we need to travel through N diagonal elements. Hence the overall time complexity will be O(N).

Space Complexity

O(1)

 

We are not using any extra space, hence the space complexity is constant.

Code Solution
(100% EXP penalty)
Mirror Diagonals
Full screen
Console