Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Sample Examples
3.
Approach
3.1.
Algorithm
3.2.
Implementation
3.2.1.
Time Complexity
3.2.2.
Space Complexity
4.
Frequently Asked Questions
4.1.
How do you define a Sparse matrix?
4.2.
What is the Time complexity for a complete traversal of a matrix?
4.3.
What is the preferred method to allocate a 2-d array dynamically?
5.
Conclusion
Last Updated: Mar 27, 2024

Maximum Product of 4 Adjacent Elements in a Matrix

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

This blog covers a matrix problem. Matrices are among the most important and often asked data structures in programming contests and technical interviews. There are various standard matrix problems and techniques. This blog tackles a coding task that discusses the problem of finding the maximum product of four adjacent elements in a matrix.

Problem Statement

Ninja is given a square matrix and challenged to calculate the largest product of four adjacent matrix elements. The matrix's adjacent elements can be top, bottom, left, right, diagonal, or anti-diagonal. The numbers should be adjacent to each other. Can you assist him in completing this task?

Sample Examples

Example 1

Input

Output

24024

 

Explanation

Multiplication of 11, 12, 13, and 14 yields the highest result, and all elements are adjacent in one direction.

 

Example 2

Input

Output

3024

 

Explanation

Multiplication of 9 8 7 6 yields the highest result, and all elements are adjacent in one direction. 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach

The approach for the above problem is quite simple and straightforward. We group elements adjacent to each other row-wise,column-wise, anti-diagonal, and diagonal-wise. Calculate their maximum results in each direction, compare them with each other, and return the maximum value among them.

Algorithm

1. In each row, group four items that are next to each other and compute their maximum result.

2. In each column, group four elements that are next to each other and compute their maximum results.

3. Calculate the greatest value of four items that are diagonally next to each other.

4. Group four elements that are anti-diagonal to each other and compute their maximum results.

5. Compare all maximum computed results and return the maximum amongst them.

Implementation

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

const int M = 5;

// function to find max product
int maxProduct(int nums[][M], int M)
{
  int max = 0, ans;
  for (int j = 0; j < M; j++)
  {
    for (int k = 0; k < M; k++)
    {


      // check for maximum product
      // in a row.
      if ((k - 3) >= 0)
      {
        ans = nums[j][k] * nums[j][k - 1] *
              nums[j][k - 2] * nums[j][k - 3];

        if (max < ans)
          max = ans;
      }

      // check for maximum product
      // in a column.
      if ((j - 3) >= 0)
      {
        ans = nums[j][k] * nums[j - 1][k] *
              nums[j - 2][k] * nums[j - 3][k];


        if (max < ans)
          max = ans;
      }


      // check the maximum product in
      // diagonal
      if ((j - 3) >= 0 && (k - 3) >= 0)
      {
        ans = nums[j][k] * nums[j - 1][k - 1] *
              nums[j - 2][k - 2] * nums[j - 3][k - 3];


        if (max < ans)
          max = ans;
      }

      // check for maximum product in
      // anti-diagonal
      if ((j - 3) >= 0 && (k - 1) <= 0)
      {
        ans = nums[j][k] * nums[j - 1][k + 1] *
              nums[j - 2][k + 2] * nums[j - 3][k + 3];

        if (max < ans)
          max = ans;
      }
    }
  }

  return max;
}


// Driver code
int main()
{
  int arr[][5] = {{1, 5, 4, 3, 2},
                  {9, 8, 7, 6, 1},
                  {1, 2, 3, 1, 4},
                  {4, 6, 0, 1, 0},
                  {0, 1, 3, 6, 7}};
  cout << "The given input array is: "<<endl;
  for (size_t i = 0; i < 5; i++)
  {
    for (size_t j = 0; j < 5; j++)
    {
      cout << arr[i][j] << " ";
    }
    cout << endl;
  }

  cout << "The maximum product is: " << maxProduct(arr, M);
  return 0;
}


Output

Time Complexity

The time complexity for the given approach is O(m*n) as we traverse the entire matrix to search for the maximum product between adjacent elements in any direction.

Space Complexity

The program's auxiliary space is O(1) because no additional data structure is involved.

Also see,  Rabin Karp Algorithm

Frequently Asked Questions

How do you define a Sparse matrix?

The sparse matrix is defined as a matrix with more zero elements than non-zero elements.

What is the Time complexity for a complete traversal of a matrix?

The Time complexity for a complete matrix traversal is O(N x M), where N, M are the dimensions of the matrix.

What is the preferred method to allocate a 2-d array dynamically?

A 2D array should be dynamically allocated in C++ using a single pointer. 

Conclusion

This article extensively discussed the problem of finding the maximum product of 4 adjacent elements in a matrix in any direction and its time and space complexities.

Cheers, you have reached the end. Hope you liked the blog and it has added some knowledge to your life. Please look at these similar topics to learn more: Types of MatrixFind Good MatrixPrint MatrixBook Allocation ProblemMatrix is Symmetric.

Refer to our Coding Ninjas Studio Guided Path to learn Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and even more! You can also check out the mock test series and participate in the contests hosted by Coding Ninjas Studio! But say you're just starting and want to learn about questions posed by tech titans like Amazon, Microsoft, Uber, and so on. In such a case, for placement preparations, you can also look at the problemsinterview experiences, and interview bundle.

You should also consider our premium courses to offer your career advantage over others!

Please upvote our blogs if you find them useful and exciting!

Happy Coding!

Previous article
Count All Sorted Rows in a Matrix
Next article
Minimum Number of Operations Required to Set All Elements of a Binary Matrix
Live masterclass