The input is an array (n*m 1<n,m< 1000)
. I have to find the maximum element in every sub-matrice of size( a*b )
.
I was trying to do this by iterating x
over n-a+1
and y
over m-j+1
.
2D segment trees
orquad tree
s are not sufficiently fast as the number of queries is large.I tried to extend
sparse table
but was not able to due to shortage of space.I have read about solutions with
Cartesian trees
but some code is needed as I cannot understand it.
Please explain a solution that will answer a query in O(nm)
time or in O(1)
time by pre-computation. Also, the input array is static.
Note: although I've tried sparse table
, it might not have been correct, so feel free to post a solution with it.
I'm a Java
coder, so an implementation in Java
or c/c++
would be great.
Also this is not a duplicate as I have searched a lot about it without finding anything suitable.
Number of possibilities:
(From Number of submatrix of size AxB in a matrix of size MxN)
In a matrix of
size (m*n)
, there are(n-A+1)*(m-B+1)
different matrices ofsize (A*B)
.So the total number of possible input for your function is
sum((n-A+1)*(m-B+1))
whereA=1..n
andB=1..m
.Structure:
I propose you build an
hashmap
that you simply index with the boundaries of your matrix:A string built from
a=M(i,j)
,b=M(k,l)
where0< i < k <(n+1)
and0< j < l <(m+1)
aHashMap("["+i+","+j+"].["+k+","+l+"]")
Pre-computation:
Have a function that calculates the max of a given matrix (a[i,j],b[k,l]) - say
myMax(i,j,k,l)
. I assume there is no point showing you how.Then its easy (sorry I can't easily compile anything so I give only the principle for now):
This is
O(n^4)
, but assuming its pre-computational, there's no point, it just make your program bigger and bigger when storingaHashMap
.Good to know
Such problem also seem to be widely addressed at http://cs.stackexchange.com ; e.g. this or that... so this SE could be of interest to the OP.
Implementation of this naive approach:
With
99 x 95
it already gives millions of possibilities to pre-compute, taking about 3Go RAM!matrix.h
matrix.cpp
main.cpp
make