CODEWITHSUNDEEP
algorithmsegment-tree
HackAround
HackAround

Reputation: 85

K-ordered blocks range query

Given a list of N numbers(1-indexed), a continuous block is K-ordered block if it has more than K same elements occurring consecutively.

Example : [2,4,4,5,5,5,3,3] is having a 3-ordered block from index 4 to 6 and a 2-ordered block from 7 to 8. Block from 4 to 6 is 2-ordered block too.

Now if we are given Queries of form : LeftIndex,RightIndex,Order-K

We need to tell between LeftIndex and RightIndex how many Order-K blocks are present.

Say if query is of type 2,8,2 then answer is 3 as 3 blocks are with Order 2. They are from index 2 to 3,4 to 6,7 to 8.

How to solve this problem if queries are up to 100000, and list can be 100000.

Upvotes: 0

Views: 124

Answers (1)

Hac
Hac

Reputation: 3

You should show what you've done and your idea. Refer to tour

Include details about what you have tried and exactly what you are trying to do.

The algorithm is quite simple.

Start a loop with i = leftIdx - 1, skip and count all the next elements that equal to list[i](use while() loop). If the number of same elements(including list[i]) is larger than or equal to K, a new Order-K block is found. Now update i to i+count, and continue the loop until i > rightIdx.

Just be careful with the corner cases(empty list, rightIdx<=leftIdx, etc.) and IndexOutOfBound exception.

Upvotes: 0

Related Questions