Maximum Sum Subarray In A Sorted 2D Matrix

Filed Under: C++
Maximum Sum Subarray In A Sorted 2D Matrix

In this article, we will learn to solve the maximum sum subarray in a sorted 2D matrix problem using C++. This is one of the musts to do problems before appearing for an interview. Top-tier companies prefer to ask a lot of subarray-based questions. This is so because subarray-based questions are a little trickier to crack. We will first have a look at the problem statement and then move toward the concept.

Problem Statement

Given a two-dimensional row-wise and column-wise sorted matrix, you have to find the maximum sum subarray.

Concept

To tackle this problem, we will take carefully use the information that is given to us. This not only involves reading the problem statement carefully but also keeping an eye on the constraints.

The naive approach will be to generate all possible submatrices and find their sum and select the maximum out of them.

However, this is a bad idea because to generate all possible submatrices, we must use at least two corners of the submatrix. A pair of the top-left and the bottom-right corner can uniquely define a rectangle. To generate all possible pairs of top-left and bottom-right corners, we need O(N4)time complexity.

And to further evaluate its sum, you have to invest time in the order O(N2). This implies that to calculate the maximum sum subarray the naive algorithm needs O(N6)time complexity. This complexity is extremely poor. It can hardly compute for N = 10.

Notice that the matrix is row-wise and column-wise sorted, this is the most useful information for us. Let’s see how to interpret this information.

Approach

  • The area of the matrix to focus on starts from the bottom right.
    • Because it is given that the matrix is sorted. Hence, the bottom-right region of the submatrix would contain more positive and greater valued elements than the remaining region.
    • Also, the elements near the top-left region are going to be the least valued elements.
    • Why not bottom left?: Because the bottom-left will also have a magnitude smaller than the bottom-right
  • Now, we make use of the prefix-sum matrices.
    • The problem with this kind of matrix is that it starts from the top-left. But for our case, we want to start from the bottom right.
    • To tackle this problem, we would use the suffix sum submatrix.
  • Once we have this submatrix, we can just traverse over this whole suffix sum matrix.
  • For any index (i, j) we will have the sum from (N – 1, M – 1) to (i, j)
  • The maximum value of this suffix sum matrix will be our answer
  • So the algorithm boils down to finding the suffix sum submatrix and its maximum element will be the answer.

Maximum Sum Subarray In A Sorted 2D Matrix Program

Let’s now implement the maximum sum subarray in a sorted 2d matrix using C++.

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int maximum_sum(vector <vector <int>> v)
{
	int n = v.size();
	int m = v[0].size();

	// find the suffix sum matrix

	for(int i = n - 1; i >= 0; i--)
		for(int j = m - 2; j >= 0; j--)
		        v[i][j] += v[i][j + 1];

	for(int i = m - 1; i >= 0; i--)
		for(int j = n - 2; j >= 0; j--)
			v[j][i] += v[j + 1][i];

	int ans = INT_MIN;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			ans = max(ans, v[i][j]);

	return ans;
}

int main()
{
	cout << "Enter the size" << endl;
	int n, m;
	cin >> n >> m;
	cout << "Enter the array elements" << endl;
	vector <vector <int>> v(n, vector <int> (m, 0));

	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			cin >> v[i][j];
		}
	}

	cout << "Maximum sum for a subarray is: ";
	cout << maximum_sum(v) << endl;

	return 0;
}
Algorithm 10
Algorithm

Output

Maximum Subarray Sum Output
Maximum Subarray Sum Output

Conclusion

In today’s article, we learned to solve the maximum subarray sum in a sorted 2D matrix. Though you might feel that the concept was a little trickier, the code is very simple to write. That’s all for now, thanks for reading.

Further Readings

To learn more about two-dimensional matrices, you can go through the following articles

https://www.journaldev.com/60624/staircase-search-on-sorted-2d-matrices-cpp

https://www.journaldev.com/60799/spirally-read-2d-matrices-cpp

close
Generic selectors
Exact matches only
Search in title
Search in content