Getting the number of "friend" tower

Question

Given n towers numbered 1, 2, 3,...,n, with their height (h[i] = towers[i] 's height) and a number k.

Two tower a, b are considered friends iff:

a - b = k
h[a] == h[b]
max(h[a+1], h[a+2] ... h[b - 1]) <= h[a]

How many `friendships' are there ?

Solution is straight forward:

for i = 1, 2, 3, 4, 5, ..., n - k:
    if h[i] == h[i+k]:
        for j in range[i, i+k] :
             MAX = max(MAX, h[j]
        if MAX <= h[i]:
             ans++

But I want the solution in the most efficient way. Please help.

For a large n, the program will eat the RAM; to reduce that, instead of array I used a queue to add the height of towers (when q.size() == k, Just q.pop() ) . Checking for 3rd condition with a large k with naive solution must take time.

You can use the answer to [this question](http://stackoverflow.com/q/4802038/2095090) to efficiently have a sliding maximum (the question is about minimum, but that change is straightforward). Then you can solve this in `O(n)` time. — Vincent van der Weele, Apr 04 '14 at 07:02
"For a large n, the program will eat the RAM": can you explain ? This algorithm uses no extra storage ! And using a deque does not reduce storage ! — , Apr 04 '14 at 07:16
because n very large compare to k, so that if I am using array, I have to store all of the number to array -> wasted — Xeing, Apr 04 '14 at 13:27

score 0 · Answer 1 · edited May 23 '17 at 10:26

0

You can use deque to provide O(n) algorithm.
At every step:

Remove too old elements from the deque head  
       (if currentindex - index >= k)  
Remove elements from tail that have no chance to become maximum 
       in the k-size window (those < currentvalue)  
Add new element (index) to the deque tail

This keeps index of max element in k-size window on the head of the deque, so you can determine - is there larger value between two towers

Decription of (sliding minimum) algorithm with pseudocode: Can min/max of moving window achieve in O(N)?

edited May 23 '17 at 10:26

Community

1
1

answered Apr 04 '14 at 07:11

MBo

77,366
5
53
86

Don't know why this is downvoted. This is the correct answer (although it could be a little more explicit how this works). – Vincent van der Weele Apr 04 '14 at 07:31
Deque is not required for this problem. Check my solution. – cegprakash Apr 04 '14 at 08:41

score 0 · Answer 2 · edited May 23 '17 at 12:05

Elaborating on my comment, you could use the answer to this question to build a queue that can keep track of the maximum element between two towers. Moving to the next element only takes O(1) amortized time. I made a simple implementation in pseudocode, assuming the language supports a standard stack (would be surprised if it didn't). For an explanation, see the linked answer.

class TupleStack
    Stack stack

    void push(int x)
        if stack.isEmpty()
            stack.push((value: x, max: x))
        else 
            stack.push((value: x, max: max(x, stack.peek().max))

    int pop()
        return stack.pop().value

    bool isEmpty()
        return stack.isEmpty()

    int getMax()
        if isEmpty()
            return -infinity
        else
            return stack.peek().max

class MaxQueue
    TupleStack stack1
    TupleStack stack2

    void enqueue(int x)
        stack1.push(x)

    int dequeue()
        if stack2.isEmpty()
            while !stack1.isEmpty()
                stack2.push(stack1.pop())
        return stack2.pop()

    int getMax()
        return max(stack1.getMax(), stack2.getMax())

Your algorithm is now very trivial. Put the first k elements in the queue. After that, repetitively check if two towers at distance k have the same height, check that the max in between (which is the max of the queue) is at most their height, and move to the next two towers. Updating the queue takes O(1) amortized time, so this algorithm runs in O(n), which is clearly optimal.

MaxQueue queue
for (int i = 1; i <= k; i++)    // add first k towers to queue
    queue.enqueue(h[i])
for (int i = k+1; i <= n; i++)
    if h[i] == h[i-k] and h[i] >= queue.getMax()
        ans++
    queue.enqueue(h[i])
    queue.dequeue()

hi.. can you edit this answer? I'd like to remove my downvote. — cegprakash, May 06 '14 at 08:55

Getting the number of "friend" tower

2 Answers2