No. 33 - Maximums in Sliding Windows

Question: Given an array of numbers and a sliding window size, how to get the maximal numbers in all sliding windows?

For example, if the input array is {2, 3, 4, 2, 6, 2, 5, 1} and the size of sliding windows is 3, the output of maximums are {4, 4, 6, 6, 6, 5}, as illustrated in Table1.

Sliding Windows in an Array	Maximums in Sliding Windows
[2, 3, 4], 2, 6, 2, 5, 1	4
2, [3, 4, 2], 6, 2, 5, 1	4
2, 3, [4, 2, 6], 2, 5, 1	6
2, 3, 4, [2, 6, 2], 5, 1	6
2, 3, 4, 2, [6, 2, 5], 1	6
2, 3, 4, 2, 6, [2, 5, 1]	5

Table 1: Maximums of all sliding windows with size 3 in an array {2, 3, 4, 2, 6, 2, 5, 1}. A pair of brackets indicates a sliding window.

Analysis: It is not difficult to get a solution with brute force: Scan numbers in every sliding window to get its maximal value. The overall time complexity is O(nk) if the length of array is n and the size of sliding windows is k.

The naïve solution is not the best solution. Let us explore better solutions.

Solution 1: Maximal value in a queue

A window can be viewed as a queue. When it slides, a number is pushed into its back, and its front is popped off. Therefore, the problem is solved if we can get the maximal value of a queue.

There are no straightforward approaches to getting the maximal value of a queue. However, there are solutions to get the maximal value of a stack, which is similar to the solution introduced in the blog “Stack with Function min()”. Additionally, a queue can also be implemented with two stacks (details are discussed in another blog “Queue implemented with Two Stacks”). 

If a new type of queue is implemented with two stacks, in which a function max() is defined to get the maximal value, the maximal value in a queue is the greater number of the two maximal numbers in two stacks.

This solution is workable. However, we may not have enough time to write all code to implement our own queue and stack data structures during interviews. Let us continue exploring a more concise solution.

Solution 2: Saving the maximal value into the front of a queue

Instead of pushing every numbers inside a sliding window into a queue, we try to push the candidates of maximum only into a queue. Let us take the array {2, 3, 4, 2, 6, 2, 5, 1} as an example to analyze the solution step by step.

The first number in the array is 2, we push it into a queue. The second number is 3, which is greater than the previous number 2. The number 2 should be popped off, because it is less than 3 and it has no chance to be the maximal value. There is only one number left in the queue when we pop 2 at the back and push 3 at the back. The operations are similar when we push the next number 4. There is only a number 4 remaining in the queue. Now the sliding window already has three elements, we can get the maximum value at the front of the queue.

We continue to push the fourth number.  It is pushed at the back of queue, because it is less than the previous number 4 and it might be a maximal number in the future when the previous numbers are popped off. There are two numbers, 4 and 2, in the queue, and 4 is the maximum.

The next number to be pushed is 6. Since it is greater than the existing numbers, 4 and 2, these two numbers can be popped off because they have no chance to be the maximum. Now there is only one number in the queue, which is 6, after the current number is pushed. Of course, the maximum is 6.

The next number is 2, which is pushed into the back of the queue because it is less than the previous number 6. There are two numbers in the queue, 6 and 2, and the number 6 at the front of the queue is the maximal value.

It is time to push the number 5. Because it is greater than the number 2 at the back of the queue, 2 is popped off and then 5 is pushed. There are two numbers in the queue, 6 and 5, and the number 6 at the front of the queue is the maximal value.

Now let us push the last number 1. It can be pushed into the queue. It is noticeable that the number at the front is beyond the scope the current sliding window, and it should be popped off.  How do we know whether the number at the front of the queue is out of sliding window? Rather than storing numbers in the queue directly, we can store indices instead. If the distance between the index at the front of queue and the index of the current number to be pushed is greater than or equal to the window size, the number corresponding to be the index at the font of queue is out of sliding window.

The analysis process above is summarized in Table 2.

Step	Number to Be Pushed	Numbers in Sliding Window	Indices in queue	Maximum in Window
1	2	2	0(2)
2	3	2, 3	1(3)
3	4	2, 3, 4	2(4)	4
4	2	3, 4, 2	2(4), 3(2)	4
5	6	4, 2, 6	4(6)	6
6	2	2, 6, 2	4(6), 5(2)	6
7	5	6, 2, 5	4(6), 6(5)	6
8	1	2, 5, 1	6(5), 7(1)	5

Table 2: The process to get the maximal number in all sliding windows with window size 3 in the array {2, 3, 4, 2, 6, 2, 5, 1}. In the column “Indices in queue”, the number inside a pair of parentheses is the number indexed by the number before it in the array.

We can implement a solution based on the analysis above. Some sample code in C++ is shown below, which utilizes the type deque of STL.

vector<int> maxInWindows(const vector<int>& numbers, int windowSize)

{

    vector<int> maxInSlidingWindows;

    if(numbers.size() >= windowSize && windowSize > 1)

    {

        deque<int> indices;

        for(int i = 0; i < windowSize; ++i)

        {

            while(!indices.empty() && numbers[i] >= numbers[indices.back()])

                indices.pop_back();

            indices.push_back(i);

        }

        for(int i = windowSize; i < numbers.size(); ++i)

        {

            maxInSlidingWindows.push_back(numbers[indices.front()]);

            while(!indices.empty() && numbers[i] >= numbers[indices.back()])

                indices.pop_back();

            if(!indices.empty() && indices.front() <= i - windowSize)

                indices.pop_front();

            indices.push_back(i);

        }

        maxInSlidingWindows.push_back(numbers[indices.front()]);

    }

    return maxInSlidingWindows;

}

Extension: Another solution to get the maximum of a queue

As we mentioned before, a sliding window can be viewed as a queue. Therefore, we can implement a new solution to get the maximal value of a queue based on the second solution to get the maximums of sliding windows.

The following is the sample code:

template<typename T> class QueueWithMax

{

public:

    QueueWithMax(): currentIndex(0)

    {

    }

    void push_back(T number)

    {

        while(!maximums.empty() && number >= maximums.back().number)

            maximums.pop_back();

        InternalData internalData = {number, currentIndex};

        data.push_back(internalData);

        maximums.push_back(internalData);

        ++currentIndex;

    }

    void pop_front()

    {

        if(maximums.empty())

            throw new exception("queue is empty");

        if(maximums.front().index == data.front().index)

            maximums.pop_front();

        data.pop_front();

    }

    T max() const

    {

        if(maximums.empty())

            throw new exception("queue is empty");

        return maximums.front().number;

    }

private:

    struct InternalData

    {

        T number;

        int index;

    };

    deque<InternalData> data;

    deque<InternalData> maximums;

    int currentIndex;

};

Since this solution is similar to the second solution to get maximums of sliding windows, we won’t analyze the process step by step, and leave it as an exercise if you are interested.

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.
 

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.    

No. 17 - Queue Implemented with Two Stacks

Problem: Implement a queue with two stacks. The class for queues is declared in C++ as below. Please implement two functions: appendTail to append an element into tail of a queue, and deleteHead to delete an element from head of a queue.

template <typename T> class CQueue

{

public:

    CQueue(void);

    ~CQueue(void);

   

void appendTail(const T& node);

    T deleteHead();                 

private:

    stack<T> stack1;

    stack<T> stack2;

};

Analysis: According to declaration above, a queue contains two stacks stack1 and stack2. Therefore, it is required to implement a queue which follows the rule “First In First Out” with two stacks which follow the rule of “First In Last Out”.

We analyze the process to add and delete some elements via some examples. Firstly en element a is inserted. Let us push it into stack1. There is an element {a} in stack1and stack2 is empty. We continue to add two more elements b and c (push them into stack1 too). There are three elements {a, b, c} in stack1 now, where c is on its top, and stack2 is still empty (as shown in Figure 1-a).

We then have a try to delete an element from a queue. According to the rule “First in First out”, the first element to be deleted is a since it is added before b and c. The element a is stored in to stack1, and it is not on the top of stack. Therefore, we cannot pop it directly. We can notice that stack2 has not been used, so it is the time for us to utilize it. If we pop elements from stack1 and push them into stack2 one by one, the order of elements in stack2 is reverse to the order in stack1. After three popping and pushing operations, stack1 becomes empty and there are three elements {c, b, a} in stack2. The element a can be popped out now since it is on the top of stack2. Now there are two elements left {c, b} in stack2 and b is on its top (as shown in Figure 1-b).

How about to continue deleting more elements from the tail of queue? The element b is inserted into queue before c, so it should be deleted when there are two elements b and c left in queue. It can be popped out since it is on the top of stack2. After the popping operation, stack1 remains empty and there is only an element c in stack2 (as shown in Figure 1-c).

It is time to summarize the steps to delete an element from a queue: The top of stack2 can be popped out since it is the first element inserted into queue when stack2 is not empty. When stack2 is empty, we pop all elements from stack1 and push them into stack2 one by one. The first element in a queue is pushed into the bottom of stack1. It can be popped out directly after popping and pushing operations since it is on the top of stack2.

Let us insert another element d. How about to push it into stack1 (as shown in Figure1-d)? When we continue to delete the top of stack2, which is element c, can be popped because it is not empty (as shown in Figure 1-d). The element c is indeed inserted into queue before the element d, so it is a reasonable operation to delete c before d. The final status of the queue is shown as Figure 1-e.

Figure 1: The process to simulate a queue with two stacks.

We can write code after we get clear ideas about the process to insert and delete elements. Some sample code is shown below:

template<typename T> void CQueue<T>::appendTail(const T& element)

{

    stack1.push(element);

}

template<typename T> T CQueue<T>::deleteHead()

{

    if(stack2.size()<= 0)

    {

        while(stack1.size()>0)

        {

            T& data = stack1.top();

            stack1.pop();

            stack2.push(data);

        }

    }

    if(stack2.size() == 0)

        throw new exception("queue is empty");

    T head = stack2.top();

    stack2.pop();

    return head;

}

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.    

No. 11 - Print Binary Trees from Top to Bottom

Problem: Please print a binary tree from its top level to bottom level, and print nodes from left to right if they are in same level. 

For example, it prints the binary tree in Figure 1 in order of 8, 6, 10, 5, 7, 9, 11.

A binary tree node is defined as below:

struct BinaryTreeNode

{

    int                    m_nValue;

    BinaryTreeNode*        m_pLeft; 

    BinaryTreeNode*        m_pRight;

};

Figure 1: A binary tree sample. If it is printed from top to bottom, it prints 8, 6, 10, 5, 7, 9, 11 sequentially.

Analysis: It examines candidates’ understanding of tree traverse algorithms, but the traverse here is not the traditional pre-order, in-order or post-order traverses. If we are not familiar with it, we may analyze the printing process with some examples during interview. Let us take the binary tree in Figure 1 as an example.

Since we begin to print from the top level of the tree in Figure 1, we can start our analysis from its root node. Firstly we print the value in its root node, which is 8. We need to store the children nodes with value 6 and 10 in a data container in order to print them after we print the root. There are two nodes in our container at this time.

Secondly we retrieve the node 6 from the container, since nodes 6 and 10 are in same level and we need to print them from left to right. We also need to store the nodes 5 and 7 after we print the node 6. There are three nodes in the container now, which are node 10, 5 and 7.

Thirdly we retrieve the node 10 from the container. It is noticeable that node 10 is stored into the container before nodes 5 and 7 are stored, and it is also retrieved ahead of nodes 5 and 7. It is typically “First in first out”, so the container is essentially a queue. After print the node 10, we store its two children nodes 9 and 11 into the container too.

Since nodes 5, 7, 9, 11 do not have children, we print them in order.

The printing process can be summarized in the following Table 1:

Step	Operation	Nodes in queue
1	Print Node 8	Node 6, Node 10
2	Print Node 6	Node 10, Node 5, Node 7
3	Print Node 10	Node 5, Node 7, Node 9, Node 11
4	Print Node 5	Node 7, Node 9, Node 11
5	Print Node 7	Node 9, Node 11
6	Print Node 9	Node 11
7	Print Node 11

Table 1: The process to print the binary tree in Figure 1 from top to bottom

We can summarize the rules to print a binary tree from top level to bottom level: Once we print a node, we store its children nodes into a queue if it has. We continue to print the head of the queue, pop it from the queue and store its children until there are no nodes left in the queue.

The following sample code is based on the deque class of STL:

void PrintFromTopToBottom(BinaryTreeNode* pTreeRoot)

{

    if(!pTreeRoot)

        return;

    std::deque<BinaryTreeNode *> dequeTreeNode;

    dequeTreeNode.push_back(pTreeRoot);

    while(dequeTreeNode.size())

    {

        BinaryTreeNode *pNode = dequeTreeNode.front();

        dequeTreeNode.pop_front();

        printf("%d ", pNode->m_nValue);

        if(pNode->m_pLeft)

            dequeTreeNode.push_back(pNode->m_pLeft);

        if(pNode->m_pRight)

            dequeTreeNode.push_back(pNode->m_pRight);

    }

}

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.