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;
}
You can also try this code with Online C++ Compiler
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 Matrix, Find Good Matrix, Print Matrix, Book Allocation Problem, Matrix 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 problems, interview 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!
84+ registered