0

Input: A 2-dimensional array NxN - Matrix - with numbers from 0 to 9.

Output: Largest rectangular area where absolute value of number's difference in area is k.

Possible input:

int k=3;
const int N=5;
int matrix[N][N] = {{9, 3, 8, 2, 0},
                    {2, 7, 6, 8, 5},
                    {8, 5, 7, 7, 6},
                    {3, 0, 4, 0, 9},
                    {7, 2, 0, 4, 0}};

Is it related to find largest area in histogram problem? If it does how I can transform this matrix two binary matrix? And how to approach this kind of problems?

Answer: largest area is 8 by following sub matrix {{7, 6, 8, 6}, {5, 7, 7, 6}}

What I think should be done:

  1. Transform matrix to binary matrix
  2. Create histogram from binary matrix
  3. Calculate largest area using largest area in histogram.

What is unclear is how to transform input matrix to binary matrix.

Khamidulla
  • 2,927
  • 6
  • 35
  • 59
  • down voter explain what is problem? – Khamidulla Sep 22 '14 at 01:16
  • Questions asking for homework help must include a summary of the work you've done so far to solve the problem, and a description of the difficulty you are having solving it. ([link](http://stackoverflow.com/help/on-topic)) – Csq Sep 22 '14 at 01:20
  • @Csq It is not for homework. I am not student for long time. I am just wondering how I can transform it to histogram problem if it is possible. And all calculation will be done after transformation done. And this type question perfectly normal see here:http://stackoverflow.com/questions/6014147/finding-elements-within-distance-k-from-a-matrix?rq=1 – Khamidulla Sep 22 '14 at 01:21
  • The main reason for the downvotes is because stackoverflow is primarily a Q&A site for actual programming problems. Your question in its current form is much better suited to cs.stackexchange.com. Basically, best questions for stackoverflow comes in the form of "Here's my problem, here's my code to solve it, but it doesn't work, why?" Your current question is simply "how do I solve this?" You have over 1K reputation so it's surprising that you are surprised by the downvotes. – wookie919 Sep 22 '14 at 01:26
  • The question you linked to is over three years old. Just because a type of question was acceptable then does not mean it is today. – Captain Obvlious Sep 22 '14 at 01:27
  • @wookie919 before asking question like this I already search similar questions in stack overflow and it is perfectly accepted by community. – Khamidulla Sep 22 '14 at 01:28
  • I am just explaining the downvotes as the reasons seem quite obvious to me at least. (I didn't downvote you, by the way.) – wookie919 Sep 22 '14 at 01:30
  • i think this question could be OK, but can you explain a little more how to get the answer, maybe using pseudo code? – Segfault Sep 22 '14 at 01:39
  • @Segfault Problem is here in my point of view transform matrix two binary one and make histogram out of it and find largest area in histogram. But how to transform it? I do not have any idea? but if i will have pseudo code by myself I can easily program it. My problem is how to correctly approach to this problem. I mean how to transform to binary matrix. – Khamidulla Sep 22 '14 at 01:43
  • I get your problem, but your proposed solution seems fiction to me! what are basing on to suggest that? what is meant by binary matrix ? – chouaib Sep 22 '14 at 01:53
  • @chaouaib Do you familiar with http://stackoverflow.com/questions/7770945/largest-rectangular-sub-matrix-with-the-same-number kind of question? If you do you can understand rest once it will transform to 1 and 0 based matrix. Rest is already done by many other. Complexty to problem came with argument k. Which means number's in cell should be same or absolute value difference of numbers in cell should be no more than k. – Khamidulla Sep 22 '14 at 01:57
  • @chouaib If you see answer section. Number difference is no more than k. I man abs(7-6)=1, abs(7-8)=1 and so on. – Khamidulla Sep 22 '14 at 01:59
  • This kind of technique is used in photoshop for magic wand in order to select similar colored areas. – Khamidulla Sep 22 '14 at 02:03
  • can't you apply the algorithm from http://stackoverflow.com/questions/7770945/largest-rectangular-sub-matrix-with-the-same-number here though? just store the bounds for your numbers. say you start from [7, 7] then go [3, 7] restart then [3, 8] restart and so on just compare the diff to your k – user3012759 Sep 22 '14 at 11:29
  • Brute forcing would cost `O(N^3)`. Not good enough? You could try looking at algorithms for solving the maximum sub-array problem and adapt it for solving this problem. – wookie919 Sep 23 '14 at 02:06
  • @wookie919 I almost done :) I simplified matrix to binary and will calculate largest area using Largest area in Histogram. And may be answer to my question by my self or just put answer to question it self. P.S. There is solution for this O(nlogn) – Khamidulla Sep 23 '14 at 04:41

0 Answers0