Given an array
A
[
1
:
n
]
=
[
a
1
,
a
2
,
.
.
.
,
a
n
]
, we wish to answer queries of the form
m
o
d
e
(
A
,
i
:
j
)
, where
1
≤
i
≤
j
≤
n
. The mode of an array
S
=
[
s
1
,
s
2
,
.
.
.
,
s
n
]
,
m
o
d
e
(
S
)
, is an element
s
i
such that the frequency of
s
i
is greater than the frequency of
s
j
∀
j
∈
{
1
,
.
.
.
,
n
}
. For example, if
S
=
[
1
,
2
,
4
,
2
,
3
,
4
,
2
]
,
m
o
d
e
(
s
)
=
2
. This definition can be extended to the mode of any subset of the array
A
[
i
:
j
]
=
[
a
i
,
a
i
+
1
,
.
.
.
,
a
j
]
.
Let
A
and
B
be any multisets. If
c
is a mode of
A
∪
B
and
c
∉
A
, then
c
is a mode of
B
.
Let
c
∉
A
be a mode of
C
=
A
∪
B
and
f
c
be its frequency in
C
. Suppose that
c
is not a mode of
B
. Thus, there exists an element
b
with frequency
f
b
that is the mode of
B
. Since
b
is the mode of
B
and that
c
∉
A
, then
f
b
>
f
c
. Thus,
b
should be the mode of
C
which is a contradiction.
Any data structure using
S
cells of
w
bits each needs
Ω
(
log
n
log
(
S
w
/
n
)
)
time to answer a range mode query.
This contrasts with other range mode problems, such as the range minimum query which have solutions offering constant time query time and linear space. This is due to the hardness of the mode problem, since if we know the mode of
A
[
i
:
j
]
and the mode of
A
[
j
+
i
:
k
]
, there is no simple way of computing the mode of
A
[
i
:
k
]
. Any element of
A
[
j
+
i
:
k
]
or
A
[
j
+
i
:
k
]
could be the mode. For example, if
m
o
d
e
(
A
[
i
:
j
]
)
=
a
and its frequency is
f
a
, and
m
o
d
e
(
A
[
j
+
1
:
k
]
)
=
b
and its frequency is also
f
a
, there could be an element
c
with frequency
f
a
−
1
in
A
[
i
:
j
]
and frequency
f
a
−
1
in
A
[
j
+
1
:
k
]
.
a
≠
c
≠
b
, but its frequency in
A
[
i
:
k
]
is greater than the frequency of
a
and
b
, which makes
c
a better candidate for
m
o
d
e
(
A
[
i
:
k
]
)
than
a
or
b
.
This method by Chan et al. uses
O
(
n
+
s
2
)
space and
O
(
n
/
s
)
query time. By setting
s
=
n
, we get
O
(
n
)
and
O
(
n
)
bounds for space and query time.
Let
A
[
1
:
n
]
be an array, and
D
[
1
:
Δ
]
be an array that contains the distinct values of A, where
Δ
is the number of distinct elements. We define
B
[
1
:
n
]
to be an array such that, for each
i
,
B
[
i
]
contains the rank (position) of
A
[
i
]
in
D
. Arrays
B
,
D
can be created by a linear scan of
A
.
Arrays
Q
1
,
Q
2
,
.
.
.
,
Q
Δ
are also created, such that, for each
a
∈
{
1
,
.
.
.
,
Δ
}
,
Q
a
=
{
b
|
B
[
b
]
=
a
}
. We then create an array
B
′
[
1
:
n
]
, such that, for all
b
∈
{
1
,
.
.
.
,
n
}
,
B
′
[
b
]
contains the rank of
b
in
Q
B
[
b
]
. Again, a linear scan of
B
suffices to create arrays
Q
1
,
Q
2
,
.
.
.
,
Q
Δ
and
B
′
.
It is now possible to answer queries of the form "is the frequency of
B
[
i
]
in
B
[
i
:
j
]
at least
q
" in constant time, by checking whether
Q
B
[
i
]
[
B
′
[
i
]
+
q
−
1
]
≤
j
.
The array is split B into
s
blocks
b
1
,
b
2
,
.
.
.
,
b
s
, each of size
t
=
⌈
n
/
s
⌉
. Thus, a block
b
i
spans over
B
[
i
⋅
t
+
1
:
(
i
+
1
)
t
]
. The mode and the frequency of each block or set of consecutive blocks will be pre-computed in two tables
S
and
S
′
.
S
[
b
i
,
b
j
]
is the mode of
b
i
∪
b
i
+
1
∪
.
.
.
∪
b
j
, or equivalently, the mode of
B
[
b
i
t
+
1
:
(
b
j
+
1
)
t
]
, and
S
′
stores the corresponding frequency. These two tables can be stored in
O
(
s
2
)
space, and can be populated in
O
(
s
⋅
n
)
by scanning
B
s
times, computing a row of
S
,
S
′
each time with the following algorithm:
algorithm computeS_Sprime
is
input: Array
B=[0:n-1],
Array
D=[0:Delta-1],
Integer
s
output: Tables
S and
Sprime
let
S ← Table(0:s-1,0:s-1)
let
Sprime ← Table(0:s-1,0:s-1)
let
firstOccurence ← Array(0:Delta-1)
for all i
in {0,...,Delta-1}
do
firstOccurence[i] ← -1
end for
for i ← 0:s-1
do
let
j ← i*t
let
c ← 0
let
fc ← 0
let
noBlock ← i
let
block_start ← j
let
block_end ← min{(i+1)*t-1, n-1}
while j < n
do
if firstOccurence[B[i]] = -1
then
firstOccurence[B[i]] ← j
end if
if atLeastQInstances(firstOccurence[B[j]], block_end, fc+1)
then
c ← B[i]
fc ← fc+1
end if
if (j+1)%t = 0
or j = size-1
then
S[i*s+noBlock] ← c
Sprime[i*s+noBlock] ← fc
noBlock ← noBlock+1
block_end ← min{block_end+t, size-1}
end if
end while
for all i
in {0,...,Delta-1}
do
firstOccurence[i] ← -1
end for
end for
We will define the query algorithm over array
B
. This can be translated to an answer over
A
, since for any
a
,
i
,
j
,
B
[
a
]
is a mode for
B
[
i
:
j
]
if and only if
A
[
a
]
is a mode for
A
[
i
:
j
]
. We can convert an answer for
B
to an answer for
A
in constant time by looking in
A
or
B
at the corresponding index.
Given a query
m
o
d
e
(
B
,
i
,
j
)
, the query is split in three parts: the prefix, the span and the suffix. Let
b
i
=
⌈
(
i
−
1
)
/
t
⌉
and
b
j
=
⌊
j
/
t
⌋
−
1
. These denote the indices of the first and last block that are completely contained in
B
. The range of these blocks is called the span. The prefix is then
B
[
i
:
m
i
n
{
b
i
t
,
j
}
]
(the set of indices before the span), and the suffix is
B
[
m
a
x
{
(
b
j
+
1
)
t
+
1
,
i
}
:
j
]
(the set of indices after the span). The prefix, suffix or span can be empty, the latter is if
b
j
<
b
i
.
For the span, the mode
c
is already stored in
S
[
b
i
,
b
j
]
. Let
f
c
be the frequency of the mode, which is stored in
S
′
[
b
i
,
b
j
]
. If the span is empty, let
f
c
=
0
. Recall that, by Theorem 1, the mode of
B
[
i
:
j
]
is either an element of the prefix, span or suffix. A linear scan is performed over each element in the prefix and in the suffix to check if its frequency is greater than the current candidate
c
, in which case
c
and
f
c
are updated to the new value. At the end of the scan,
c
contains the mode of
B
[
i
:
j
]
and
f
c
its frequency.
The procedure is similar for both prefix and suffix, so it suffice to run this procedure for both:
Let
x
be the index of the current element. There are three cases:
- If
Q
B
[
x
]
[
B
′
[
x
]
−
1
]
≥
i
, then it was present in
B
[
i
:
x
−
1
]
and its frequency has already been counted. Pass to the next element.
- Otherwise, check if the frequency of
B
[
x
]
in
B
[
i
:
j
]
is at least
f
c
(this can be done in constant time since it is the equivalent of checking it for
B
[
x
:
j
]
).
- If it is not, then pass to the next element.
- If it is, then compute the actual frequency
f
x
of
B
[
x
]
in
B
[
i
:
j
]
by a linear scan (starting at index
B
′
[
x
]
+
f
c
−
1
) or a binary search in
Q
B
[
x
]
. Set
c
:=
B
[
x
]
and
f
c
:=
f
x
.
This linear scan (excluding the frequency computations) is bounded by the block size
t
, since neither the prefix or the suffix can be greater than
t
. A further analysis of the linear scans done for frequency computations shows that it is also bounded by the block size. Thus, the query time is
O
(
t
)
=
O
(
n
/
s
)
.
This method by uses
O
(
n
2
log
log
n
log
n
)
space for a constant time query. We can observe that, if a constant query time is desired, this is a better solution than the one proposed by Chan et al., as the latter gives a space of
O
(
n
2
)
for constant query time if
s
=
n
.
Let
A
[
1
:
n
]
be an array. The preprocessing is done in three steps:
- Split the array
A
in
s
blocks
b
1
,
b
2
,
.
.
.
,
b
s
, where the size of each block is
t
=
⌈
n
/
s
⌉
. Build a table
S
of size
s
×
s
where
S
[
i
,
j
]
is the mode of
b
i
∪
b
i
+
1
∪
.
.
.
∪
b
j
. The total space for this step is
O
(
s
2
)
- For any query
m
o
d
e
(
A
,
i
,
j
)
, let
b
i
′
be the block that contains
i
and
b
j
′
be the block that contains
j
. Let the span be the set of blocks completely contained in
A
[
i
:
j
]
. The mode
c
of the block can be retrieved from
S
. By Theorem 1, the mode can be either the mode of the prefix (indices of
A
[
i
:
j
]
before the start of the span), the mode of the suffix (indices of
A
[
i
:
j
]
after the end of the span), or
c
. The size of the prefix plus the size of the suffix is bounded by
2
t
, thus the position of the mode isstored as an integer ranging from
0
to
2
t
, where
[
0
:
2
t
−
1
]
indicates a position in the prefix/suffix and
2
t
indicates that the mode is the mode of the span. There are
(
t
2
)
possible queries involving blocks
b
i
′
and
b
j
′
, so these values are stored in a table of size
t
2
. Furthermore, there are
(
2
t
+
1
)
t
2
such tables, so the total space required for this step is
O
(
t
2
(
2
t
+
1
)
t
2
)
. To access those tables, a pointer is added in addition to the mode in the table
S
for each pair of blocks.
- To handle queries
m
o
d
e
(
A
,
i
,
j
)
where
i
and
j
are in the same block, all such solutions are precomputed. There are
O
(
s
t
2
)
of them, they are stored in a three dimensional table
T
of this size.
The total space used by this data structure is
O
(
s
2
+
t
2
(
2
t
+
1
)
t
2
+
s
t
2
)
, which reduces to
O
(
n
2
log
log
n
log
n
)
if we take
t
=
log
n
/
log
log
n
.
Given a query
m
o
d
e
(
A
,
i
,
j
)
, check if it is completely contained inside a block, in which case the answer is stored in table
T
. If the query spans exactly one or more blocks, then the answer is found in table
S
. Otherwise, use the pointer stored in table
S
at position
S
[
b
i
′
,
b
j
′
]
, where
b
i
′
,
b
j
′
are the indices of the blocks that contain respectively
i
and
j
, to find the table
U
b
i
′
,
b
j
′
that contains the positions of the mode for these blocks and use the position to find the mode in
A
. This can be done in constant time.
