## Right view of a binary tree

We learned different traversals of a binary tree like inorder, preorder, postorder, level order etc in previous posts. Today’s problem includes traversal of a binary tree too but in a different manner. The problem statement is to write a program to print the right view of a binary tree. The first question would be what is the right view of a binary tree?

Right view of a binary tree would be all the nodes of the binary tree which are visible when the tree is looked at from the right-hand side of the binary tree. For example, we would see nodes: 10, 15, and 19 when we look at the binary tree below from the right side as node 7 will be hidden by node 15 and node 8,9 and 18 will be hidden by node 19.

### Right view of a binary tree: thoughts

What do we see when we look at the tree from the right-hand side? What is the observation? It is that once we see a node, we can not see any node which is on the same level behind the visible node. The visible node obstructs all other nodes.
Which node will be the first one to be visible? It would be the rightmost node on that level. So we have to visit the right child of a node first before we visit the left child. If there was a right child of a node, the left child will not be visible. How can we make sure even the cousins of the rightmost node are not visible?

The idea is simple, we will do a preorder traversal of a binary tree with the right child visited first. Why? Because if we see the right child, the left child will not be visible as explained above.

To make sure none of the cousins are visible of a rightmost node are visible, we have to keep track of the levels. When we reach a node, we see if the level of the node is deeper than already seen maximum level? If yes, this node is the rightmost node (Why? because we are visited right child first) on that level and should be visible. Now, the maximum visited level is this new level, all the nodes which are this new level will not be visible.

### Right view of a binary tree: example

Let’s take an example and see how this method works.

We have current max level traversed as -1. At `node(10)`, we visit the level 0 which is greater than the current maximum. So `node(10)` should be visible in the right view of the binary tree.

At `node(15)`, we are moving down a level, so the current level would be 1, whereas current max visited level is 0. `node(15)`will be visible from the right-hand side of the tree. The max level visited is 1.

As we are doing preorder traversal, we will visit `node(19)` next, which is at level 2 which is greater than max level, so, `node(19)` will be visible in the right view of the binary tree.

Next, we visit the `node(18)`, which is at the level 2, which is equal to max level, hence `node(18)` will not be visible.

`node(7)` is at the level 1, which is less than current max level 2, so it will not be visible. Same is the case for the `node(8)` and `node(9)`.

#### Right view of a binary tree: implementation

```#include<stdio.h>
#include<stdlib.h>

struct node{
int value;
struct node *left;
struct node *right;
};
typedef struct node Node;

void printRightView(Node * node, int currLevel, int *maxLevel){

if(node == NULL) return;

if(currLevel >  *maxLevel){
printf("%d  ", node->value);
*maxLevel = currLevel;
}
printRightView(node->right, currLevel+1, maxLevel);
printRightView(node->left, currLevel+1, maxLevel);
}
/* driver program */
Node * createNode(int value){
Node *temp =  (Node *)malloc(sizeof(Node));
temp->value = value;
temp->right= NULL;
temp->left = NULL;
return temp;
}

if(node == NULL){
return createNode(value);
}
else{
if (node->value > value){
}
else{
}
}
return node;
}

int main(){

Node *root = NULL;
//Creating a binary tree

int max = -1;
printRightView(root, 0, &max);

return 0;
}
```

We visit each node only once, complexity of above code is O(n).

Please share if there is something wrong or missing. If you are willing to contribute and share your learning with thousands of learners across the world, please reach out to us at [email protected]

Posted on 1 Comment on Right view of a binary tree

## Zigzag traversal of a binary tree

In the last post, level order traversal of a binary tree, we discussed how to do the breadth-first traversal of a tree. Today’s problem is twisted version of it, literally. The problem statement is to do a zigzag traversal of a binary tree.  What do we mean by zigzag?  It means that while traversing tree level order, the first level is traversed left to right, the second level is right to left and the third is again traversed left to right and so on.
For example, for the given below binary tree, zigzag traversal would be [10.15,7,8,9,18,19]

This problem is also know as spiral traversal of binary tree.

### Zigzag traversal: Line of thought

We already solved the problem to traverse a binary tree level order. In the recursive solution, we first find the number of levels in the tree. For each level, we start from the root and traverse or print all the nodes at that level. How about passing a hint which indicates where we have to traverse next level left to right or right to left? Based on the hint, we can change the recursion calls order to do left or right first.

```package com.company.BST;

import java.util.ArrayList;
import java.util.Stack;

/**
* Created by sangar on 24.10.18.
*/
public class ZigzagTraversal {
public ArrayList<Integer>
zigzagTraversalRecursive(BinarySearchTree tree){
ArrayList<Integer> traversal = new ArrayList<>();

int height = tree.height();
boolean leftToRight = true; //hint

for(int i=1; i>=height; i++){
traverseLevel(tree.getRoot(), i,
traversal,leftToRight);
//Toggle the hint
leftToRight = !leftToRight;
}
return traversal;
}

private void traverseLevel(TreeNode root, int level,
ArrayList<Integer> levelTraversal,
boolean leftToRight){
if(level == 1){
}

//Based on hint, recursive call order will change
if(leftToRight) {
if (root.getLeft() != null)
traverseLevel(root.getLeft(), level - 1,
levelTraversal, leftToRight);
if (root.getRight() != null)
traverseLevel(root.getRight(), level - 1,
levelTraversal, leftToRight);
}
else{
if (root.getRight() != null)
traverseLevel(root.getRight(), level - 1,
levelTraversal, leftToRight);
if (root.getLeft() != null)
traverseLevel(root.getLeft(), level - 1,
levelTraversal, leftToRight);
}
}
}

```

### Zigzag traversal using stacks

Above implementation has a complexity of `O(n2)` as we traverse nodes at least once, however, some nodes are accessed multiple times. The first level nodes will be traversed n times, second level nodes are accessed n-1 times and so on, where last level nodes are accessed only 1 time. This is true when the tree is completely skewed, where each node has only one child. In worst case, we will be accessing n + (n-1) + (n-2) + … + 1 nodes overall, hence the complexity of this method is `O(n2)`

Can we do better than this?  Problem with the recursive method is that we have to start from the root node for each level. Can we save some information current level in order to traverse the next level in the correct direction? What if we store children of the current node in the order they should be traversed (left to right or right to left). We can use two data structures, queues or stack, as we want some kind of order on the nodes being inserted. I have chosen stack to store the nodes at the next level in correct order. As to direction changes at each level, we need to stacks, one which stores all the nodes to be traversed in left to right direction and other stores all the nodes to be traversed in right to left direction.

In one stack, push right child first and left child next, when we pop from the stack, we get the left child first and right child next. This stack stores node in left to right order.
In another stack, we push left child first and right child next,  when we pop, we get right child first and the left child next. This stack stores node in right to left order.

### Zigzag traversal using stack: algorithm

• Initialize two stacks empty: s1 and s2
• While s1 and s2 both are not empty:
• While s1 is not empty:
• Pop node from s1, currentNode = s1.pop()
• Push right child of currentNode on s2
• Push left child of currentNode on s2.
• While s2 is not empty:
• Pop node from s2, currentNode = s2.pop().
• Push left child of currentNode in s1.
• Push right child of currentNode in s1.

#### Zigzag traversal using stacks implementation

```package com.company.BST;

import java.util.ArrayList;
import java.util.Stack;

/**
* Created by sangar on 24.10.18.
*/
public class ZigzagTraversal {

public ArrayList<Integer> zigzagTraversal(TreeNode root){

Stack<TreeNode> leftToRightStack = new Stack<>();
Stack<TreeNode> rightToLeftStack = new Stack<>();

ArrayList<Integer> traversal = new ArrayList<>();

if(root == null) return traversal;

while (!leftToRightStack.isEmpty()
||!rightToLeftStack.isEmpty()){
TreeNode current = null;
while(!leftToRightStack.isEmpty()){
current = leftToRightStack.pop();
/* As next level will be right to left,
If push right child last, we want it to first
*/
if(current.getLeft()!= null)
if(current.getRight()!= null)
}
while(!rightToLeftStack.isEmpty()){
current = rightToLeftStack.pop();

/* As next level will be left to right,
If push left child last, we want it to first
*/
if(current.getRight()!= null)
if(current.getLeft()!= null)
}
}
return traversal;
}
}
```

Definition of tree node is as follows.

```package com.company.BST;

/**
* Created by sangar on 21.10.18.
*/
public class TreeNode<T> {
private T value;
private TreeNode left;
private TreeNode right;

public TreeNode(T value) {
this.value = value;
this.left = null;
this.right = null;
}

public T getValue(){
return this.value;
}
public TreeNode getRight(){
return this.right;
}
public TreeNode getLeft(){
return this.left;
}

public void setValue(T value){
this.value = value;
}

public void setRight(TreeNode node){
this.right = node;
}

public void setLeft(TreeNode node){
this.left = node;
}
}
```

Test cases for zigzag traversal implementations

```package test;

import com.company.BST.BinarySearchTree;
import com.company.BST.ZigzagTraversal;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
* Created by sangar on 23.9.18.
*/
public class ZigZagTraversalTest {

ZigzagTraversal tester = new ZigzagTraversal();

@Test
public void queueTest() {

BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();
binarySearchTree.insert(10);
binarySearchTree.insert(8);
binarySearchTree.insert(15);
binarySearchTree.insert(12);
binarySearchTree.insert(6);
binarySearchTree.insert(9);

ArrayList<Integer> zigzagTraversal = new ArrayList<>(Arrays.asList(10,15,8,6,9,12));

ArrayList<Integer> result = tester.zigzagTraversalRecursive(binarySearchTree);
System.out.println(result);
assertEquals(zigzagTraversal, tester.zigzagTraversalRecursive(binarySearchTree));
}
}

```

The complexity of the above method to do a zigzag traversal of a binary tree is O(n) with an additional space complexity of O(n).

If there is something wrong or missing, please reach out to us at [email protected] If you want personalized coaching to prepare for your interviews, please signup for a free session.

## Balanced partition problem

Given a set of integers, partition those integers into two parts where the difference between the two parts is minimum. This problem is known as balanced partition problem. For example,

```Input:
A = [1,7,4,11],
Output:
1
Explanation:
Two subsets can be: {1,11} and {7,4}, two have a difference of 1, which is the minimum difference we can get by splitting this array.
```
Mathematically, you have a set of n integers each in the range 0, . . . , K. Partition these integers into two subsets such that you minimize |S1 − S2|, where S1 and S2 denote the sums of the elements in each of the two subsets.

Balance partition problem can be asked in many other ways, for instance, given a list of 22 players and their strengths, divide those 22 players into two teams so that both teams are balanced. Another version can be that you have n candy, each candy has a value associated with it. You want to distribute those candies between two kids as equally as possible.

No matter what version is asked, the approach remains the same.

## Balance partition problem: thoughts

The brute force method will be to list down all the subsets of the given set and find the sum of each one of them. Then scan through the sum of all the subsets and find the two closest ones. For a set of n elements, there can be `2n` subset. Therefore, the complexity of this brute force solution is already exponential.

Let me tweak balance partition problem a bit. We find if there are two subsets of the set of integers such that the difference between sum of these two subsets is zero. Essentially, this is a special case of the original problem. If the difference between the sum of two subsets is zero that means the sum of both subsets should be exactly equal to half of the sum of all elements in the set.

So problem reduces to a smaller problem that is to find if there is a subset of integers which add up to half the sum of all integers in the set? This is the subset sum problem which we have already solved.

How can we use information provided by subset set problem above? Let’s say S is the sum of all the integers in the set. S/2 will be half of that sum. We have to find a subset with sum i such that S/2 -i is minimum.

Whether or not, there is a subset with sum i in the set is given by solving subset sum problem. For the sums, i, which are possible with subsets of the set, find the one which is the least distance from S/2. That will give us other subsets which are least greater than half of the sum of all elements of the set and that will be minimal difference possible between two subsets.

So,  expression would be as

```min(S/2 - i) where T[n][i] = True and i>=0 and i<=S/2
```

Why we took i >=0 and i<S/2? Because, we want to be balanced, so i cannot be more than half of the total sum in any case.

### Balanced partition problem implementation

```package com.company;

/**
* Created by sangar on 25.11.18.
*/
public class BalancedPartition {
public int findBalancePartition(int[] a){

// Calculate sum of all the elements in set
int S = 0;
for (int i=0; i<a.length; i++)
S += a[i];

boolean T[][] = new boolean[a.length + 1][S + 1];

/* Initialize the first column as true.
0 sum is possible with all elements.
*/
for (int i=0; i<=a.length; i++)
T[i] = true;

/*  Initialize top row, except dp,
as false. With 0 elements, no other
sum except 0 is possible
*/
for (int i=1; i<=S; i++)
T[i] = false;

for (int i = 1; i <= a.length; i++) {
for (int j = 1; j <= S; j++) {
// If ith element is excluded
T[i][j] = T[i - 1][j];

// If ith element is included
if (a[i - 1] <= j)
T[i][j] |= T[i - 1][j - a[i - 1]];
}
}

// Initialize difference of two sums.
int diff = Integer.MAX_VALUE;

for (int j = S/2; j >= 0; j--) {
// Find the
if (T[a.length][j] == true)
{
diff = S - 2 * j;
break;
}
}
return diff;
}
}
```

Once, we get the nearest sum, we can always backtrack the table and find elements of the subset itself. Actually, this problem is now reduced to 0/1 knapsack problem, where maximum value we can get is j from the set of integers.

Complexity to split set into two balanced partitions is O(n * S) with a space complexity of O(n * S), where S will be the max value array can have.

# Minimum jumps to reach end of array

Given an array of integers, find minimum jumps to reach end of the array. Condition is that you can maximum jump a[i] indices from index i.

For example, in following array, minimum jumps required are 2.

At index 1, we can either jump 0, 1 or 2 indices ahead. If we jump 2 indices, we would require two more jumps (at 1 and 1) to reach at 4. So total number of jumps would be 3. You jump maximum at start, but at the end, more number of jumps required.

However if we jump only 1 index ahead, next A[i] will allow us to jump 3 indices ahead, doing so we will reach at the end of the array. So minimum number of jumps to reach at the end of array is 2.

## Minimum number of jumps : thought process

What would be the brute force method to solve this? At each index, you try all possible jumps and get the combination which gives you the minimum jumps. This method will have exponential complexity which we do not want.

What is the original problem? It’s `minJumps(start, end)` Of all the jumps possible from start, let’s say we go to index k, then what how does problem reduces? Well, now we have to find minimum number of jumps from k to end. How to decide on k now? We try all k values from start+1 to start + a[i].

```minJumps(start, end) = Min ( minJumps(k, end) )
for all k reachable from start
```

Now, we have clear recursion relationship, what should be the base case? When `k + A[k]` > end, or `k == end`, we should return 1 as there would be only one jump required from k to end now.

```package com.company;

/**
* Created by sangar on 10.10.18.
*/
public class MinimumJumps {

public int minimumNumberOfJump(int[] a, int start, int end){
//If start == end, we reached the end, return 0.
if(start == end) return 0;

//if current element is 0, you cannot jump to end at all
if(a[start] == 0) return Integer.MAX_VALUE;

int minimumJumps = Integer.MAX_VALUE;

for(int k=start+1; k<=start+a[start] && k<=end; k++){
/*
For each K from start+1 to end, find the minimum jumps.
*/
int jumps = minimumNumberOfJump(a,k,end);
if(jumps != Integer.MAX_VALUE && jumps + 1 <; minimumJumps){
minimumJumps  = jumps + 1;
}
}
return minimumJumps;
}
}
```

Test cases for above function

```package test;

import com.company.MinimumJumps;
import org.junit.jupiter.api.Test;

import static org.junit.Assert.assertEquals;

/**
* Created by sangar on 23.9.18.
*/
public class MinimumJumpTest {

MinimumJumps tester = new MinimumJumps();

@Test
public void baseTest() {

int[] a = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
assertEquals(3,
tester.minimumNumberOfJump(a,0, a.length-1));
}

@Test
public void arrayContainsZeroTest() {

int[] a = {1, 3, 0, 0, 0, 2, 6, 7, 6, 8, 9};
assertEquals(Integer.MAX_VALUE,
tester.minimumNumberOfJump(a,0, a.length-1));
}

@Test
public void nullArrayTest() {

assertEquals(0, tester.minimumNumberOfJump(null,0, 0));
}

@Test
public void arrayWithTwoElementsTest() {

int[] a = {1, 0};
assertEquals(1,
tester.minimumNumberOfJump(a,0, a.length-1));
}
}
```

Let’s see execution trace of above function for an input.

From the above execution tree, we notice that some subproblems are calculated again and again. This is typically known as overlapping subproblems.
Also, optimal solution to subproblem actually lead us to optimal solution for original problem which is optimal subproblem structure. These two property are must to apply dynamic programming to a problem.

What if we store minimum number of jumps required to reach a particular index. To reach first index, jumps required is 0. `Jump[i]` represents the number of reach index i. Solution to reach at the end of the array would be Jump[n-1]. How do we feel this array? For each i,  from  j = 0 to i-1 and check if j+a[j] <= i, if yes, update `jump[i] = min (jump[i], jump[j]+1)`.

### Minimum number of jumps: dynamic programming approach

```package com.company;

/**
* Created by sangar on 10.10.18.
*/
public class MinimumJumps {

public int minimumNumberOfJumpDP(int[] a){

if(a == null || a.length == 0) return 0;

if(a == 0) return Integer.MAX_VALUE;

int[] jump = new int[a.length];

//no jumps required for first element
jump = 0;

for(int i=1; i<a.length;i++){
jump[i] = Integer.MAX_VALUE;

for(int j=0; j<i; j++){
if(j+a[j]>=i && jump[j] != Integer.MAX_VALUE ){
jump[i] = Integer.min(jump[i], 1 + jump[j]);
}
}
}
return jump[a.length-1];
}
}
```

Complexity of dynamic programming approach to find minimum number of jumps to reach end of an array is `O(n2)` with space complexity of `O(n)`

If you are interested to solve this problem in `O(n)` time, please visit stack overflow discussion

Please share if there is something wrong or missing. If you are interested in taking coaching from one of our experienced teachers, please reach out to us at [email protected]

# Sliding window problem

Given a large integer array of size x, window size of n and a random number k, find smallest k numbers in every window of n elements in array. This is commonly know as sliding window problem. For example: for an array [2,3,1,5,6,4,2,5,4,3,8] k = 2 and n = 6, output should be [1,2],[1,2],[1,3][1,4][1,3][1,3]. How? see below figure.

This problem regularly features in Amazon interviews.

## Find k numbers in sliding window : thoughts

If we spit down the problem, it reduces to find k smallest elements in an array, which can easily be solve in multiple ways. All we have to take care of is moving the window and storing results for each window.

Quick sort method
First way is to use quick sort, we randomly pick a pivot and put it in right place. When pivot is at right place, all elements on the right side of pivot are greater than pivot and all elements on the left side are less than pivot. If pivot is a kth position in array, all elements on left side of pivot automatically become K smallest elements of given array. In worst case this method take O(n log n) for each window.

Using heaps
What are we interested in is k elements, what if from current window, we take out first k numbers and consider them as k smallest elements? This set of k numbers may change based value of following numbers in the window. Which way? If new number is smaller than any of the number chosen randomly, new number has to be added into the k smallest element set. However, we have only k spaces there, so someone has to move out.

If new number is less than any number in set, it must be less than maximum number in set

Given above fact, we can always swap new number with maximum of set. Now problem is how to find max in a set? This set will modified repeatedly, so we cannot just sort it once and find the max. For use cases when data is changing and we have to find max of that set, heaps are the best data structures to use. In this case we will use max heap. Max heap is kind of heap where children of root node are smaller than root node. Max heap will give us O(1) complexity to find max and O(log n) complexity to heapify on removal old max and insertion of new number.

Algorithm

1. Create a max heap with first k elements of window.
2. Scan through remaining elements in window
1. If root of max heap is less than new number, remove the root and add new element to heap
2. All elements in heap at the end of processing are k smallest numbers in window.

### Sliding window algorithm to find k smallest elements : Implementation

```#include<stdio.h>
#include<stdlib.h>
#include <math.h>

typedef struct node {
struct node * left;
struct node * right;
int data;
} heapNode;

int leftChild(int i){
return 2*i + 1;
}

int rightChild(int i){
return 2*i + 2;
}

void swapPtr(heapNode *a[], int i, int largest){
heapNode *temp = a[i];
a[i] = a[largest];
a[largest] = temp;
}
/* This function heapifies heap after removal of root
or at time of building heap from an array */
void max_heapify_ptr(heapNode *a[], int i, int len){
int largest = i;
int left, right;

left = leftChild(i);
right = rightChild(i);

if(left <= len && a[i]->data <a[left]->data){
largest = left;
}
if(right <= len && a[largest]->data < a[right]->data){
largest = right;
}
if(largest != i){
swapPtr(a, i, largest);
max_heapify_ptr(a, largest, len);
}
}

/* Building heap from given elements */
void build_max_heap_ptr(heapNode *a[], int len){
int i = len/2 +1;
for(; i>=0; i--){
max_heapify_ptr(a,i, len);
}
}

/* This function allocates node of heap */
heapNode * create_node(int data){
heapNode *node = (heapNode *)(malloc)(sizeof(heapNode));
if(node){
node->data = data;
}
return node;

}

/* This function is real implementation of
the sliding window algorithm */
void slide_window(int buffer[], int N, int K, int buffer_len){

int i =0, j =0,s;
heapNode *max_heap[K+1];
int num = K;

for(j=0 ; j + N < buffer_len; j++){
/* Window starts at index 0 and is of size N */
printf("\nCurrent window :");
for(s =j; s<j+N; s++){
printf("%d ", buffer[s]);
}
printf("\n");
/* Put K element from N element window */
for(i=0;i<K; i++){
/* Since we wold be doing for every window,
avoiding reallocation of node */
if(max_heap[i]){
max_heap[i]->data = buffer[i+j];
}
else{
max_heap[i] = create_node(buffer[i+j]);
}
}
/* Build min heap with those entered elements */
build_max_heap_ptr(max_heap,K-1);

/*Now for all remaining N-K-1 elements in window,
check if they fit in max heap */
for(i=K+j; i< N+j; i++){
heapNode * root = max_heap;
if(buffer[i] < root->data){
root->data = buffer[i];
max_heapify_ptr(max_heap, 0, K-1);
}
}

/*Print the current max heap, it will contain K smallest
element in current window */
printf("K minimum elements in this window :");
for(int x=0; x< K; x++){
printf("%d ", max_heap[x]->data);
}

}
}
/* Driver Program to execute above code */
int main(){
int buffer = {1,4,5,6,3,2,4,8,9,6};

int K= 4;
int N =5;

int size = sizeof(buffer)/ sizeof(buffer);

slide_window(buffer,N, K,size);
return 0;
}
```

Following figures explain how window slides and how heap is updated.
1. Window starts at index 0 and ends at N. We take K minimum elements among N elements and store in max heap. Array is given in below picture with window size of 9 and k = 4.
First step is to create a max heap with first 4 elements of window. Next we are looking at 4, which is less than max in max heap. So we remove the max from heap and add the new element(4) to heap. Next is 2, which is less than max in max heap. So we remove the max from heap and add the new element(2) to heap. Next is 3, which is less than max in max heap. So we remove the max from heap and add the new element(3) to heap. Next we have 10 and 11 which are greater than root of max heap, so nothing happens. We come to end of window. Therefore, 4 smallest element in window are [ 1,2,3,4 ]

Next window moves one step ahead, that’s where you discard the max heap and create the new empty one and repeat the process.

We can actually avoid discarding the entire heap when window moves, however complexity of overall algorithm will remain the same. This problem is asked in a different way, which is to find maximum in sliding window.

```#include <iostream>
#include<deque>
using namespace std;

void slidingWindow(int buffer[], int n, int w, int output[])
{
deque<int> Q;
int i;
/*Initilize deque Q for first window, put all W elements, however also
removing elements which cannot be maximum in this window */
for (i = 0; i < w; i++)
{
//This is where we are removing all less than elements
while (!Q.empty() && buffer[i] >= buffer[Q.back()])
Q.pop_back();
// Pushing the index
Q.push_back(i);
}

for (i = w; i < n; i++)
{
output[i-w] = buffer[Q.front()];

//update Q for new window
while (!Q.empty() && buffer[i] >= buffer[Q.back()])
Q.pop_back();

//Pop older element outside window from Q
while (!Q.empty() && Q.front() <= i-w)
Q.pop_front();

//Insert current element in Q
Q.push_back(i);
}
output[n-w] = buffer[Q.front()];
}

int main(){
int a[]={3,5,4,2,-1,4,0,-3};
int n = sizeof(a)/sizeof(a);
int output[n];

slidingWindow(a,n,4,output);
return 0;
}
```

Worst case complexity of sliding window algorithm would be O(n2k). K is included as it takes O(k) complexity to build heap of k elements.

Please share if there is something wrong or missing.

# Word break problem

This problem is commonly asked in the Google and Amazon interview. We all know that if you typed string in Google search box does not make sense, Google breaks that into meaningful words and asks us back if we meant those words instead of a single word. This post discusses how can we find if the given string can be broken into meaningful dictionary words. For example, if I typed algorithmsandme and given dictionary is [“algorithms”, “and”, “me”], this string is breakable in meaningful words. but if the string is algorithmsorme this is not breakable into meaningful words. You can find this problem for practice at leetcode.

## Word break problem : thoughts

We start with the first character of the string, check if the character itself is a word in the dictionary? If yes, then our problem reduces to the smaller problem, that is to check if substring from index 1 to s.length is breakable or not.
If not, then we check two characters and then three characters and so on till we can check the whole string. As with every character inclusion, the problem reduces in size but remains the same, so ideal case for recursive implementation.

```package AlgorithmsAndMe;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class WordBreak {

public boolean wordBreak(String s, List<String> wordDict) {
return wordBreakUtil(s, wordDict, 0, table);
}

private boolean wordBreakUtil(String s,
List<String> wordDict,
int index) {

if (index == s.length()) return true;

boolean isBreakable = false;
for(int i=index; i<s.length(); i++) {
isBreakable = isBreakable
|| wordDict.contains(s.substring(index, i+1))
&& wordBreakUtil(s, wordDict, i + 1);
}

return isBreakable;
}
}

```

If you notice we are solving the same problems again and again in recursive function `wordBreakUtil`, how can we save that repeated calculations? Best way to save the already solve problems in a cache, that way we can refer to the cache if the problem is already solved or not. If yes, do not solve it again and use the cached value. This approach is called a Top Down approach and uses memoization to avoid repeated subproblems.

```package AlgorithmsAndMe;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class WordBreak {

public boolean wordBreak(String s, List<String> wordDict) {
int [] table =  new int[s.length()];
for(int i=0; i<s.length(); i++){
table[i] = -1;
}
return wordBreakUtilTopDown(s, wordDict, 0, table);
}

private boolean wordBreakUtilTopDown(String s,
List<String> wordDict,
int index,
int[] table) {

if (index == s.length()) return true;

if(table[index] < 0) {
boolean isBreakable = false;
for (int i = index; i < s.length(); i++) {
isBreakable = isBreakable
|| wordDict.contains(s.substring(index, i + 1))
&& wordBreakUtilTopDown(s, wordDict, i + 1);
}
table[index] = isBreakable ? 1 : 0;
}
return table[index] == 1 ? true : false;
}
}

```

If you run the first solution, it will exceed the time limit on leetcode, however, the second implementation should be accepted with 4ms as the time to run. Now you can appreciate the efficiency by memoization.

### Word break problem using dynamic programming

In the last two implementations, two things are evident: first, the optimal solution of a subproblem leads to the optimal solution of the original problem. Second, there are overlapping subproblems. These are two must have conditions for applying dynamic programming. We already saw the memoization and top-down approach of DP to avoid repeated solving of subproblems. How can we do it bottom up?

What if store an information if the string till index i is breakable? What will be the base case? The string before index 0 is alway breakable as empty string. So table can be always true. To check if string till index i is breakable or not, we check from index 0 to index i-1 if there is any index j till which string is breakable. If yes, then we just check if substring from index j to i, that will make `table[i]` as true.

```package AlgorithmsAndMe;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class WordBreak {

public boolean wordBreak(String s, List<String> wordDict) {
return wordBreakBottomUp(s, wordDict, 0, table);
}

private boolean wordBreakUtilBottomUp(String s, List<String> wordDict){

if(s == null || s.length() == 0) return false;

boolean[] table  = new boolean[s.length()+1];

table = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = i - 1; j >= 0; j--) {
if (table[j] && wordDict.contains(s.substring(j, i))) {
table[i] = true;
}
}
}
}
return table[s.length()];
}
}
```

The time complexity of the above implementation of the word break problem is `O(n2)`

If you want to store all the strings which can be generated by breaking a particular word, below is the code.

```package AlgorithmsAndMe;

import java.util.*;

public class WordBreak2 {

public List<String> wordBreak(String s, List<String> wordDict) {
Map<String, List<String>> map = new HashMap<>();
return wordBreakUtil2(s, wordDict, map);
}

private List<String> wordBreakUtil2(String s,
List<String> wordDict,
Map<String, List<String>> map) {

if(map.containsKey(s)){
return map.get(s);
}

List<String> result = new ArrayList<String>();
if (wordDict.contains(s)){
}

for(int i=1; i<=s.length(); i++) {
String prefix = s.substring(0, i);
if(wordDict.contains(prefix)){
List<String> returnStringsList = wordBreakUtil2(s.substring(i), wordDict, map);

for(String returnString :returnStringsList ){
result.add(prefix + " " + returnString);
}
}
}
map.put(s,result);

return result;
}
}

```

Please share if there is something is wrong or missing. If you are preparing for an interview and need any help with preparation, please reach out to us or book a free session.

# Constant time max operation on stack

We understood stack data structure, operations on it and some examples problems which can be solved using stack. Let’s take problem which is actually based on stack and with the help of other data structures, how can make it more efficient for certain function. Today’s problem is to implement constant time max operation on stack.

To elaborate, you have been given a stack, where elements are pushed and popped randomly. At any given point of time, you have to tell max of all the elements present in stack.
For example : we have stack, we push 5,3,1, current max in stack is 5; we push 6 next, current max is 6 now. How about we pop 6 back. Current max goes back to 5 again.

## Constant time max operation: Line of thoughts

Push and pop operation in a stack are already constant time operations. Let’s concentrate on max operation.
If always just pushed on to stack, it would have been easy to just keep track of ma of all the elements we pushed on to stack. However if we are popping out from stack, this may not be as easy. Max will change if the element just popped from stack was current max. What can we do? We keep track of previous max just before the current max. What if next operation is again pop and it pops out the new current max. Again, we have to keep track of previous to previous max.
Are you getting some hint here? We have to keep track of all the max we ever saw while operating on stack in reverse order. That means the max we saw the last, goes out first. LIFO pattern and what better data structure than stack to implement that.

Idea is to have an auxiliary stack which stores all the max seen till a given point of time. Top of this auxiliary stack would be current max. What happens when pop happens on original array? We check if popped element is equal to top element of auxiliary array, that means popped element was current max. So we pop that from auxiliary stack too.

Let’s take an example and see if it works? To start with, both stacks are empty. Now, you add 2 as first element on to stack. Since auxiliary stack is empty, we add 2 on to that stack too. Push 3 on to stack. Push operation so check if current top of aux stack is less than new element pushed. If yes, push new element to aux stack too. Push 5 on to stack. Again, push operation and new push element is greater than top of aux stack, we push 5 there too. Now, push 1. Tricky case. Push 1 on to original stack, but since new element is less than current top of aux stack, nothing gets pushed on aux stack. Pop from stack now. 1 is popped, it is not equal to current top on aux stack, nothing happens. Pop from stack again, this time popped element is equal to current max, so we have pop from aux stack too. If we are asked max at this point of time, answer would be 3. ### Constant time max operation on stack : Implementation

```package com.company;

import java.util.Stack;

/**
* Created by sangar on 22.9.18.
*/
public class MaxStack {
Stack<Integer> stack;
Stack<Integer> auxStack;

public MaxStack() {
stack = new Stack();
auxStack = new Stack();
}

public void push(int x) {
int max = auxStack.isEmpty() ? x : auxStack.peek();
//Push on max stack only if max value is being changed.
if (max <= x) auxStack.push(x);
stack.push(x);
}

public int pop() {
int returnValue = stack.pop();
//Pop from aux stack only if ax value is being popped out.
if(auxStack.peek() == returnValue) {
auxStack.pop();
}
return returnValue;
}

public int top() {
return stack.peek();
}

public int peekMax() {
return auxStack.peek();
}

public int popMax() {
int max = peekMax();
Stack<Integer> buffer = new Stack();
while (top() != max) buffer.push(pop());
pop();
while (!buffer.isEmpty()) push(buffer.pop());
return max;
}
}
```

Complexity of implementation of constant time max operation stack is `O(n)` in terms of space, with `O(1)` time complexity for push, pop and max operation.

Wait, interviewer is not satisfied with this only. What we solve is just reporting the max element in stack at a given point of time. What if we were asked to implement pop max element from stack? Well, first of all finding the max element works as it is. However, popping max element requires popping out all element before max, popping out max and then pushing back all other elements again. Quite a lot of work, even when max operation is O(1).

Which data structure allows us to remove an element in constant time? It’s doubly link list. Once you know which node is to be removed, all we have to do is link previous node to next node. If we implement our original stack as doubly linked list, popping max from stack is `O(1)` operation without moving any other element on stack.

However finding the node in doubly linked list itself is `O(n)` operation. Back to square one. What would be helpful is that instead of just storing the max element, we store node address of max in doubly linked list. So in our aux stack, we do not store primitive data type, but a pointer to node which is current max.

Let’s see how it works? We follow the same process of finding the max as explained in earlier solution. It starts with pushing element 2 on to stack. This creates the first node on DLL and stores the pointer on stack. Now, we push 3 on to stack. Since this is greater than current max being pointed to by top of aux stack, we push that to DLL and store the pointer as max pointer on aux stack. As for 3, same thing happens when 5 is pushed on to stack. Since new element pushed is less than current max, it’s pointer is not pushed on to aux stack. After pushing 1, we want to pop max. Step 1 would be to fetch the node pointer for current max. Go to that node in doubly linked list. Remove that node from DLL and then remove the pointer from top of stack. Make a note that whenever, new pushed element is equal to current max, push that on aux stack too. Why?

Let’s see the implementation of this method using doubly linked list.

```package com.company;

import java.util.Stack;

/**
* Created by sangar on 22.9.18.
*/
public class MaxStackDLL {
private Stack<ListNode<Integer>> auxStack;

public MaxStackDLL() {
auxStack = new Stack();
}

public void push(int x) {
int max = auxStack.isEmpty() ? x : auxStack.peek().getData();
//Push on max stack only if max value is being changed.
if (max <= x) auxStack.push(newNode);
}

public int pop() {

//Pop from aux stack only if ax value is being popped out.
if(auxStack.peek() == returnValue) {
auxStack.pop();
}
return returnValue.getData();
}

public int peekMax() {
return !auxStack.isEmpty() ? auxStack.peek().getData() : -1;
}

public int popMax() {
return auxStack.isEmpty() ? -1 : dll.deleteNode(auxStack.pop()).getData();
}
}
```

Doubly linked list class is as follows

```package com.company;

/**
* Created by sangar on 22.9.18.
*/

}

public boolean isEmpty(){
}

if(this.isEmpty()) {
}
/*
We are inserting node at head. So following things happen
1. Create a new node.
2. Set next of new pointer to current head.
3. Set prev of head to new node
*/
//First two steps are done here
ListNode<Integer> newNode = new ListNode<Integer>(data,this.head, null);
//Step 3.
//Step 4.

}

if(this.isEmpty()) {
return null;
}
/*
We are deleting node at head. So following things happen
1. Set temporary node point to head.
2. Move head to next of node.
3. Set prev of new head to NULL.
4. Free the temp node.
*/

return tempNode;
}

public ListNode<Integer> deleteNode(ListNode<Integer> node){
if(this.isEmpty()) {
return null;
}
/*
We are deleting node in between. So following things happen
1. If node has prev, set node.prev.next = node.next.
2. If node has next, set node.next.prev = node.prev
*/
if(node.getPrev() != null) node.getPrev().setNext(node.getNext());
if(node.getNext() != null) node.getNext().setPrev(node.getPrev());

return node;
}
}
```

ListNode class is as follows

```package com.company;

/**
* Created by sangar on 22.9.18.
*/
public class ListNode<T> {
private T data;

private ListNode<T> next;
private ListNode<T> prev;

public ListNode(T data){
this.data = data;
next = null;
prev = null;
}

public ListNode(T data, ListNode<T> next, ListNode<T> prev){
this.data = data;
this.next = next;
this.prev = prev;
}

public ListNode<T> getNext(){
return this.next;
}

public ListNode<T> getPrev(){
return this.prev;
}

public void setPrev(ListNode<T> newNode){
this.prev = newNode;
}

public void setNext(ListNode<T> newNode){
this.next = newNode;
}

public T getData(){
return this.data;
}
}
```

Tester class is given below. Can you add more test cases to this?

```package test;

import com.company.MaxStackDLL;
import org.junit.jupiter.api.Test;

import static org.junit.Assert.assertEquals;

/**
* Created by sangar on 22.9.18.
*/
public class MaxStackTest {

MaxStackDLL tester = new MaxStackDLL();
@Test
public void popMaxTest() {

tester.push(2);
tester.push(3);
tester.push(5);
tester.push(1);

assertEquals(5, tester.popMax());
assertEquals(3, tester.popMax());
}
}
```

Time complexity of push, pop and popMax is `O(1)`. There is additional space requirement which is `O(n)`.

Please share if there is something wrong or missing. If you are interested in taking personalized coaching by our experienced coaches, please reach out to us at [email protected]

## Stacks : Stock Span Problem

The Stock Span problem is commonly asked in Google and Amazon interviews and taught as the application of the stack data structure in universities. Let’s take a look at the problem statement:

Given a list of prices of a single stock for N number of days, find stock span for each day. Stock span is defined as a number of consecutive days prior to the current day when the price of a stock was less than or equal to the price at current day.

For example, {100,60,70,65,80,85} span will be {1,1,2,1,4,5}. If you are preparing for an interview, you can signup for a free session to find a coach to help you with your preparation.

For the first day, span is always 1. In the example we can see that for day 2 at 60, there is no day before it where the price was less than 60. Hence span is 1 again. For day 3, the price at day 2 (60) is less than 70, hence span is 2. Similarly, for day 4 and day 5. Remember days should be consecutive, that’s why the span for day 4 is 1 – even though there was a day 2 where the price was less than 65. Stock span problem is slightly complicated to understand but the solution is pretty easy.

Let’s look at the solution. Brute force solution would be: For each day, says current day, scan all days prior to it, and increment span till the price of the stock is higher than the current day. For the simple implementation, the time complexity is `O(n2)` where n is the number of days.

## Stock Span problem: Solution

If we observe the brute force algorithm, it is evident that we are interested in a day that has a stock price that is greater than the current day’s stock price. So, we need to check the last price which was greater than the current day’s price. Can you see a potential pattern? Which is the data structure which allows you to maintain the last price and see it first? What should be the invariant here? We should be using a stack for sure! The invariant is that the stack elements should be in the increasing order of price. The element at the top should be the maximum price seen till the current day. How can we maintain this?

Go through each day’s stock price, check if the current price on top of the stack is less than the current day’s price. If yes, pop out till price on top of the stack is greater than the current day’s price, the stock span of the current day is the difference between the day of price on top of the stack and current day.
Storing the index of the last greatest stock price (i.e. the day when the stock was of that price) would make things easier as compared to storing actual stock price on the stack. Hence, store the index `i` on the stack and `price[i]` will give us the price of the stock on the ith day.

### Algorithm

1. Initialize span of day 1 (i=0) as 1 and put on to the stack.
2. For i=1 to n, do following
3. While `price[stack.top()] < price[i]` and !stack.isEmpty(), stack.pop()
4. If `price[stack.top()] > price[i]`, span = (i – stack.top())
5. Push current day index `i` on to stack.

Let’s take an example and see if this works? Let’s say prices are given on certain days are as following: 100, 60, 70, 65, 80, 85, 200

As per the above algorithm, we will put span = 1, and the stack will be .
On day 2, stock price is 60. Stock price on day at the top of stack is 100, which is greater than 60. So `span` = 1- 0 = 1. Stack = [0,1]
On day 3, stock price is 70. We will pop from the stack till `price[stack.top()]` < 70, which obviously pops out 1 as price = 60. So `span` = 2 – 0 = 2. Push new price on stack, stack = [0,2]
On day 4, stock price is 65. `price[stack.top()]` > `price`, so `span` = 3-2=1. Stack = [0,2,3]
On day 5, stock price is 80, now we pop out 3 and 2 from stack as price and price are less than 80. `span` = 4-0 = 4. stack = [0,4].
On day 6, stock price is 85, now we pop out 4 from stack as price is less than 85. `span` = 5-0 = 5. stack = [0,5].
On day 7, the stock price is 200, now we pop out 5 and 0 from the Stack as price and price is less than 200. Now stack is empty, at this point, `span` = 6. stack = .

### Stock span problem: Implementation

```
import java.util.Arrays;
import java.util.Stack;

/**
* Created by sangar on 18.9.18.
*/
public class StockSpan {
public static int[] stockSpan(int[] prices){

Stack<Integer> s = new Stack();
int[] span = new int[prices.length];

//Step 1. Initialization
span = 1;
s.push(0);

for(int i=1; i<prices.length; i++){
//Find the price on stack which is greater than current day's price
while(!s.empty() && prices[i] > prices[s.peek()]){
s.pop();

if(s.empty())
span[i] = i+1;
else
span[i] =  i - s.peek();

//Push current day onto top of stack
s.push(i);
}
}
return span;
}

public static void main(String args[]){
int prices[] = {100, 60, 70, 65, 80, 85, 45, 77, 56, 98, 200};
int[] span = stockSpan(prices);

Arrays.stream(span).forEach(System.out::println);

}
}

```

If you want to understand the basic implementation of the Stack data structure, this is the C code for it.

Stack implementation

```#include<stdio.h>
#include<stdlib.h>

#define STACK_SIZE 100

typedef struct stack{
int top;
int items[STACK_SIZE];
}stack;

void push(stack *ms, int item){
if(ms->top < STACK_SIZE-1){
ms->items[++(ms->top)] = item;
}
else {
printf("Stack is full\n");
}
}

int pop (stack *ms){
if(ms->top > -1 ){
return ms->items[(ms->top)--];
}
else{
printf("Stack is empty\n");
}
}
int peek(stack ms){
if(ms.top < 0){
printf("Stack empty\n");
return 0;
}
return ms.items[ms.top];
}
int isEmpty(stack ms){
if(ms.top < 0) return 1;
else return 0;
}

void stockSpan(int prices[], int days){

stack ms;
int i;

int span[days];

if(days ==0) return;

span = 1;
ms.top = -1;

push(&ms, 0);

for(i=1; i<days; i++){
while(!isEmpty(ms) && prices[i] > prices[peek(ms)])
pop(&ms);

if(isEmpty(ms)){
span[i] = i+1;
}
else{
span[i] =  i - peek(ms);
}
push(&ms, i);
}

for(i=0; i<days; i++){
printf("%d  ", span[i]);

printf("\n");
}
/* Driver program */
int main(){

//int prices ={100,60,70, 65, 85, 80};
int prices[] = {100, 60, 70, 65, 80, 85, 45, 77, 56, 98, 200};

int n  = sizeof(prices)/sizeof(prices);

stockSpan(prices, n);
return 0;
}
```

The optimal time complexity of the stock span algorithm is O(n) along with a space-complexity of O(n).
To understand the more advanced version of the problem, watch video by Keerti Purswani here:

Now that you have learned the concept, can you solve the similar problems on HackerEarth

Posted on Categories Data Structures, Google interview question, Stack1 Comment on Stacks : Stock Span Problem

## Check if tree is BST or not

This is one of the most asked programming interview questions. How to check or validate that a given binary tree is BST or not or if a given tree is a binary search tree? For example, the first and second binary trees are BST but not the third one.

In binary tree introduction  we touched upon the topic of recursive structure of binary search tree.  The first property to satisfy to be qualified as BST is: value in all nodes on the left subtree of the root node are smaller and the value of all nodes in the right subtree is greater than the root node. This property should be valid at all nodes.

## Check if binary tree is (BST) or not: Recursive implementation

So, to see if the binary tree rooted a particular node is BST, the root is greater than all nodes on the left subtree and less than all nodes on the right subtree. However, is it sufficient condition? Let’s take a counterexample and prove that even root is greater than all nodes on the left side and smaller than all nodes on the right subtree, a binary tree may not be binary search tree. Look at the tree below. In this tree above condition is satisfied, but we cannot call this binary tree a BST.

This is a recursive structure of a binary search tree that plays an important role. For a binary tree root at a node to be BST, it’s left subtree and right subtree should also be BST. So, there are three conditions which should be satisfied:

1. Left subtree is BST
2. Right subtree is BST
3. Value of root node is greater than the max in the left subtree and less than minimum in right subtree

### Check if binary tree is (BST) or not  : Recursive implementation

```#include<stdio.h>
#include<stdlib.h>

#define true 1
#define false 0

struct node{
int value;
struct node *left;
struct node *right;
};

typedef struct node Node;

Node * findMaximum(Node * root){
if( !root ) return root;
while( root->right ){
root = root->right;
}
return root;
}

Node * findMinimum(Node * root){
if( !root ) return root;
while( root->left ){
root = root->left;
}
return root;
}

int isBST(Node * node){

if(!node)
return true;

if( ! ( node->left || node->right ) ) return true;
int isLeft  = isBST(node->left);
int isRight = isBST(node->right);

if(isLeft && isRight){
/* Since we already know that left sub tree and
right sub tree are Binary search tree, finding min and max in them would be easy */

Node *max  =  NULL;
Node *min  =  NULL;
if( node->left )
max = findMaximum(node->left);
if( node->right )
min = findMinimum(node->right);

//Case 1 : only left sub tree is there
if(max && !min)
return node->value > max->value;
//Case 2 : Only right sub tree is there
if(!max && min)
return node->value < min->value;
//Case 3 : Both left and right sub tree are there
return (node->value > max->value && node->value < min->value);
}
return false;
}

Node * createNode(int value){
Node *newNode =  (Node *)malloc(sizeof(Node));

newNode->value = value;
newNode->right= NULL;
newNode->left = NULL;

return newNode;
}

Node * addNode(Node *node, int value){
if(node == NULL){
return createNode(value);
}
else{
if (node->value < value){
}
else{
}
}
return node;
}

/* Driver program for the function written above */
int main(){
Node *root = NULL;
//Creating a binary tree

printf("%s", isBST(root ) ? "Yes" : "No" );

return 0;
}
```

#### Check if binary tree is (BST) or not  : Optimized implementation

Above implementation to check if the binary tree is binary search tree or not is correct but inefficient because, for every node,  its left and right subtree are scanned to find min and max. It makes implementation non-linear.

How can we avoid re-scanning of left and right subtrees? If we can keep track max on left subtree and min on right subtree while checking those subtrees for BST property and use the same min and max.

Start with INTEGER_MAX and INTEGER_MIN, check if the root node is greater than max and less than min. If yes, then go down left subtree with max changed to root value, and go down to right subtree with min changed to root value. It is a similar implementation as above, except revisiting nodes.

```#include<stdio.h>
#include<stdlib.h>

#define true 1
#define false 0
#define INT_MIN -32999
#define INT_MAX 32999

struct node{
int value;
struct node *left;
struct node *right;
};

typedef struct node Node;

int isBSTHelper(Node *root, int max, int min){
if(!root) return true;

if(root->value < min || root->value > max){
return false;
}

return isBSTHelper(root->left, root->value, min) &&
isBSTHelper(root->right, max, root->value);
}

int isBST(Node *root){
return isBSTHelper(root, INT_MAX, INT_MIN);
}

Node * createNode(int value){
Node *newNode =  (Node *)malloc(sizeof(Node));

newNode->value = value;
newNode->right= NULL;
newNode->left = NULL;

return newNode;
}

Node * addNode(Node *node, int value){
if(node == NULL){
return createNode(value);
}
else{
if (node->value < value){
}
else{
}
}
return node;
}

/* Driver program for the function written above */
int main(){
Node *root = NULL;
//Creating a binary tree

printf("%s", isBST(root ) ? "Yes" : "No" );

return 0;
}
```

The complexity of the above implementation is O(n) as we are traversing each node only once.

Another method to see if the binary tree is BST or not is to do an inorder traversal of the binary tree and keep track of the previous node. As we know in-order traversal of a binary search tree gives nodes in sorted order, previously visited node should be always smaller than the current node. If all nodes satisfy this property, a binary tree is a binary search tree. If this property is violated at any node, the tree is not a binary search tree.

The complexity of this implementation is also O(n) as we will be traversing each node only once

Please share if there is something missing or not correct. If you want to contribute and share your knowledge with thousands of learner around the world, please reach out to us at [email protected]

Posted on 3 Comments on Check if tree is BST or not

## Find Kth smallest element in array

Given an array of integers which is non sorted, find kth smallest element in that array. For example: if input array is A = [3,5,1,2,6,9,7], 4th smallest element in array A is 5, because if you sort the array A, it looks like A = [1,2,3,5,6,7,9] and now you can easily see that 4th element is 5.

This problem is commonly asked in Microsoft and Amazon interviews as it has multiple layers and there are some many things that can be tested with this one problem.

## Kth smallest element : Line of thought

First of all, in any interview, try to come up with brute force solution. Brute force solution to find Kth smallest element in array of integers would be to sort the array and return A[k-1] element (K-1 as array is zero base indexed).

What is the complexity of brute force solution? It’s `O(n2)`? Well, we have sort algorithms like merge sort and heap sort which work in O(nlogn) complexity.

The problem with both searches is that they use additional space. Quick sort is another sorting algorithm. It has problem that it’s worst-case complexity will be `O(n2)`, which happens when input is completely sorted.
In our case, the input is given as unsorted already, so we can expect that quicksort will function with `O(n log n)` complexity which is its average-case complexity. Advantage of using quicksort is that there is no additional space complexity.

Optimising quick sort

Let’s see how quicksort works and see if we can optimize solution further?
Idea behind quicksort is to find the correct place for the selected pivot. Once the pivot is at the correct position, all the elements on the left side of the pivot are smaller and on the right side of the pivot are greater than the pivot. This step is partitioning.

If after partitioning, pivot is at position j, can we say that pivot is actually jth smallest element of the array? What if j is equal to k? Well problem solved, we found the kth smallest element.

If j is less than k, left subarray is less than k, we need to include more elements from right subarray, therefore kth smallest element is in right subarray somewhere. We have already found j smallest elements, all we need to find is k-j elements from right subarray.

What if j is greater than k? In this case, we have to drop some elements from left subarray, so our search space would be left subarray after partition.

Theoretically, this algorithm still has the complexity of `O(n log n)`, but practically, you do not need to sort the entire array before you find k smallest elements.

If you are preparing for a technical interview and need personal coaching along with mock interviews, book a free demo session with us

### Algorithm to find Kth smallest element in array

1. Select a pivot and partition the array with pivot at correct position j
2. If position of pivot, j, is equal to k, return A[j].
3. If j is less than k, discard array from start to j, and look for (k-j)th smallest element in right sub array, go to step 1.
4. If j is greater than k, discard array from j to end and look for kth element in left subarray, go to step 1

Let’s take an example and see if this algorithm works? A =  [4, 2, 1, 7, 5, 3, 8, 10, 9, 6 ], and we have to find fifth smallest element in array A.

Start with pivot as first index of array, so pivot = 0, partition the array into two parts around pivot such that all elements on left side of pivot element, i.e. A[pivot] are smaller and all elements on right side are greater than A[pivot].

Start with pivot as first index of array, so pivot = 0, partition the array into two parts around pivot such that all elements on left side of pivot element, i.e. A[pivot] are smaller and all elements on right side are greater than A[pivot].

In our example, array A will look like below after pivot has found it’s the correct position.

If pivot == k-1 (array is represented as zero base index), then A[pivot] is kth smallest element. Since pivot (3) is less than k-1 (4), look for kth smallest element on right side of the pivot.

k remains as it is as opposed to k-j mentioned in algorithm as pivot is given w.r.t entire array and not w.r.t subarray.

In second iteration, pivot = 4 (index and not element). After second execution of quick sort array A will be like After partition of right subarray, correct position of pivot is index 4

pivot(4) which is equal to k-1(5-1). 5th smallest element in array A is 5.

### Implementation

```package com.company;

/**
* Created by sangar on 30.9.18.
*/
public class KthSmallest {
private void swap(int[] a, int i, int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
private int partition(int[] a, int start, int end){
int pivot = a[start];
int i  = start+1;
int j  = end;

while(i <= j){
while(a[i] < pivot) i++;
while(a[j] > pivot) j--;

if(i < j) {
swap(a, i, j);
}
}
swap(a, start, j);
return j;
}

public int findKthSmallestElement(int a[], int start,
int end, int k){
if(start <= end){
int p = partition(a, start, end);
if(p == k-1){
return a[p];
}
if(p > k-1)
return findKthSmallestElement(a, start, p, k);
if(p < k-1)
return findKthSmallestElement(a, p+1, end, k);
}
return -1;
}
}
```

Test cases

```package test;

import com.company.KthSmallest;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
* Created by sangar on 28.8.18.
*/
public class KthSmallestTest {

KthSmallest tester = new KthSmallest();
private int[] a = {4, 2, 1, 7, 5, 3, 8, 10, 9};
@Test
public void kthSmallest() {
assertEquals(7, tester.findKthSmallestElement(a,0,8,6));
}

@Test
public void firstSmallest() {
assertEquals(1, tester.findKthSmallestElement(a,0,8,1));
}

@Test
public void lastSmallest() {
assertEquals(10, tester.findKthSmallestElement(a,0,8,9));
}

@Test
public void kGreaterThanSize() {
assertEquals(-1, tester.findKthSmallestElement(a,0,8,15));
}
@Test
public void emptyArray() {
int[] a = {};
assertEquals(-1, tester.findKthSmallestElement(a,0,0,1));
}

@Test
public void nullArray() {
assertEquals(-1, tester.findKthSmallestElement(null,0,0,1));
}
}
```

Complexity of using quicksort algorithm to find the kth smallest element in the array of integers is still O(n logn).

### Kth smallest element using heaps

Before going into details of this problem, I strongly recommend reading heap fundamentals.

Imagine a case where there are a billion integers in the array and you have to find 5 smallest elements from that array. The complexity of O(n log n) is too costly for that use case. Above algorithm using quicksort does not take into consideration disparity between k and n.

We want top k elements, how about we chose those k elements randomly, call it `set A` and then go through all other n-k elements, call it `set B`, check if element from set B (n-k elements) can displace element in set A (k elements)?

What will be the condition for an element from set B to replace an element in set A? Well, if the new element is less than maximum in set A than the maximum in set A cannot be in the set of k smallest elements right?  Maximum element in set A would be replaced by the new element from set B.

Now, the problem is how to quickly find the maximum out of set A. Heap is the best data structure there. What kind of heap: min heap or max heap? Max heap as it store the maximum of the set at the root of it.

Let’s defined concrete steps to find k smallest elements using a max heap.

1. Create a max heap of size k from first k elements of array.
2. Scan all elements in array one by one.
1.  If current element is less than max on heap, add current element to heap and heapify.
2. If not, then go to next element.
3. At the end, max heap will contain k smallest elements of array and root will be kth smallest element.

Let’s take an example and see if this algorithm works? The input array is shown below and we have to find the 6th smallest element in this array.

Step 1 : Create a max heap with first 6 elements of array.

Step 2: Take the next element from set B and check if it is less than the root of max heap. In this case, yes it is. Remove the root and insert the new element into max heap.

Step 2: It continues to 10, nothing happens as the new element is greater than the root of max heap. Same for 9.  At 6, again the root of max heap is greater than 6. Remove the root and add 6 to max heap. Again, new element from set B is less than root of max heap. Root is removed and new element is added.

Array scan is finished, so just return the root of the max heap, 6 which is the sixth smallest element in given array.

### Implementation

```	public int findKthSmallestElementUsingHeap(int a[], int k){
//https://stackoverflow.com/questions/11003155/change-priorityqueue-to-max-priorityqueue

PriorityQueue<Integer>  maxHeap =
new PriorityQueue<>(k, Collections.reverseOrder());

if(a == null || k > a.length) return -1;
//Create max with first k elements
for(int i=0; i<k; i++){
}

/*Keep updating max heap based on a new element
If new element is less than root,
remove root and add new element
*/

for(int i=k; i<a.length; i++){
if(maxHeap.peek() > a[i]){
maxHeap.remove();
}
}
return maxHeap.peek();
}
```

Can you calculate the complexity of above algorithm? `heapify()` has complexity of log(k) with k elements on heap. In worst case, we have to do `heapify()` for all elements in array, which is n, so overall complexity of algorithm becomes O(nlogk). Also, there is additional space complexity of O(k) to store heap.
When is very small as compared to n, this algorithm again depends on the size of array.

We want k smallest elements, if we pick first k elements from a min heap, will it solve the problem? I think so. Create a min heap of n elements in place from the given array, and then pick first k elements.
Creation of heap has complexity of O(n), do more reading on it. All we need to do is delete k times from this heap, each time there will be `heapify()`. It will have complexity of O(log n) for n element heap. So, overall complexity would be O(n + klogn).

Depending on what you want to optimize, select correct method to find kth smallest element in array.

Please share if there is something wrong or missing. If you are interested in taking coaching sessions from our experienced teachers, please reach out to us at [email protected]

Posted on 2 Comments on Find Kth smallest element in array