Sorting sliding windows online

Revision en7, by div4only, 2023-02-08 09:35:02

Given an 1-index integer array $$$a=[a_1,\,a_2,\,a_3,...,\,a_n]$$$ and a fixed windows size $$$k$$$,define sliding window $$$I_{j,\,(j \geq k)} := [a_{j-k+1}, a_{j-k+2}, ..., a_j]$$$. For each $$$j \geq k$$$, we need to answer the following queries:

How many sliding windows in $$$\{I_k, I_{k+1}, ..., I_{j-1}\}$$$ are less or equal than $$$I_j$$$ in the alphabetical order?

For example, $$$a=[1, 2, 1, 3]$$$ and $$$k=2$$$:

(1) For $$$j=2$$$, we should answer $$$0$$$.

(2) For $$$j=3$$$, we should answer $$$1$$$ as $$$[1,2] < [2,1]$$$ in alphabetical order.

(3) For $$$j=4$$$, we should answer $$$1$$$ as $$$[1,2] < [1,3]$$$ in alphabetical order.

Suffix array + LCP array can solve it in $$$O(nlogn)$$$ offline. But how about solving online? For example, what if $$$a$$$ is an unbounded data stream instead of an array? In the datastream case, you have to process $$$a_j$$$ and $$$I_j$$$ before $$$a_{j+1}$$$.

Tags strings

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en15 English div4only 2023-02-08 10:36:54 0 (published)
en14 English div4only 2023-02-08 10:36:46 1 Tiny change: 'unded data stream ins' -> 'unded datastream ins' (saved to drafts)
en13 English div4only 2023-02-08 10:36:35 8 Tiny change: 'j$ before $a_{j+1}$' -> 'j$ before reading $a_{j+1}$'
en12 English div4only 2023-02-08 09:55:46 4 Tiny change: 'Given an 1-index integer a' -> 'Given an $1$-indexed integer a'
en11 English div4only 2023-02-08 09:51:24 18 Tiny change: 'to answer the following queries:\n\nHow m' -> 'to answer a query:\n\nHow m'
en10 English div4only 2023-02-08 09:40:41 0 (published)
en9 English div4only 2023-02-08 09:40:28 22 (saved to drafts)
en8 English div4only 2023-02-08 09:35:26 0 (published)
en7 English div4only 2023-02-08 09:35:02 4 Tiny change: 'owing query:\n\nHow m' -> 'owing queries:\n\nHow m' (saved to drafts)
en6 English div4only 2023-02-08 09:34:38 0 (published)
en5 English div4only 2023-02-08 09:34:12 507
en4 English div4only 2023-02-08 09:29:31 182
en3 English div4only 2023-02-08 09:27:35 1 Tiny change: ' ..., a_j]. ' -> ' ..., a_j]$. '
en2 English div4only 2023-02-08 09:27:23 109
en1 English div4only 2023-02-08 06:08:51 76 Initial revision (saved to drafts)