Longest alternating Subsequence

In this post, we will discuss another dynamic programming problem called the longest zigzag subsequence which can be solved using dynamic programming.

A sequence of numbers is called a alternating sequence if differences between successive numbers strictly alternate between positive and negative value. In other words, alternate subsequence is where elements of subsequence are alternate increasing and decreasing order, means, they satisfy below conditions:

x1 < x2 > x3 < x4 > x5 < ….  x2 < x3 > x4 < x5 > …. xn

A sequence with fewer than two elements is trivially a zigzag subsequence.

For example, 1,9,3,9,1,6 is a zigzag sequence because the differences (8,-6,6,-8,5) are alternately positive and negative. In contrast, 1,6,7,4,5 and 1,9,4,4,5 are not zigzag sequences, first sequence is not because its first two differences are positive and second because its last difference is zero.
Coming to the problem of the day: Given an array of integers, find longest alternating subsequence.

We have already seen a similar problem longest increasing subsequence in an array. That problem is solved using a dynamic programming approach. To apply dynamic programming, we need to properties: first, Optimal subproblem structure, that is the solution of the original problem depends on the optimal solution of subproblem; and second, overlapping subproblems, so that we can save computation by memoization.

Do these two properties exist in this problem? Does the longest zigzag subsequence till length i has anything to do with the longest zigzag subsequence till j where j is less than i? Also, it is already clear that alternating subsequence can start with decreasing first and then increasing or increasing first and then decreasing.

To add ith as next element in subsequence, consider two cases. First, ith element can be greater than previous element in longest zigzag subsequence till j where j < i. In this case, we are looking for all such j where A[j] < A[i]. Another criterion for j should be that A[j] less than the previous element in the sequence, that means, at j, we are looking exactly opposite condition than that i.

Second, ith element can be less than previous element in longest zigzag subsequence till j where j < i. In this case, we are looking for all such j where A[j] > A[i]. Another criterion for j should be that A[j] is greater than the previous element in the sequence, that means, at j again, we are looking exactly opposite condition than that at i.
For each i we will store these two.

Let’s say increase[i] describes LZS, for the first case and decrease[i] describes it for the second case.

  increase[i] = max(decrease[j] + 1) for all j< i && A[j] < A[i]
  decrease[i] = max(increase[j] + 1) for all j< i && A[j] > A[i]

Longest alternating subsequence dynamic programming approach

Before going through the implementation, it will be great if you can go through Longest increasing subsequence using dynamic programming
Implementation wise, both increase and decrease array can be one two dimensional array Table[][]. Table[i][0] represents length of longest zigzag subsequence ending at i with A[i] being greater than A[j] for all j in earlier subsequences.

Similarly, Table[i][1] represents length of subsequence ending at i with A[i] being less than A[j] for all j in earlier subsequences.

Table(i,0) = max(Table(j,1) + 1); 
             for all j < i and A[j] < A[i] 
Table(i,1) = max(Table(j,0) + 1); 
             for all j < i and A[j] > A[i]

What will be length of longest zigzag subsequence for index i?

Result =  max (Table(i,0), Table(i,1))

Click here to see longest alternating subsequence implementation

#include <stdio.h>
#include <stdlib.h>
 
int max(int a, int b) {  return (a > b) ? a : b; }
 
int longestZigzagSubsequence(int A[], int n)
{
    int Table[n][2];
 
    for (int i=0; i<n; i++){
    	Table[i][0] = 1; 
    	Table[i][1] = 1;
    }
 
    int result = 1;
 
    for (int i=1; i<n; i++) {
        for (int j=0; j<i; j++){
        	// If A[i] is greater than last element in subsequence, 
        	//then check with Table[j][1]
        	if (A[j] < A[i] && Table[i][0] < Table[j][1] + 1)
                    Table[i][0] = Table[j][1] + 1;
                /* If A[i] is smaller than last element in subsequence,
                then check with Table[j][0] */
                if( A[j] > A[i] && Table[i][1] < Table[j][0] + 1)
                   Table[i][1] = Table[j][0] + 1;
        }
 
        /* Pick maximum of both values at index i  */
        if (result < max(Table[i][0], Table[i][1]))
            result = max(Table[i][0], Table[i][1]);
        printf("\n %d", result);
    }
 
    return result;
}
Complexity of dynamic programming approach to find longest alternate subsequence is O(n2) using O(n) extra space.

Please share if there is something wrong or missing. If you want to contribute to website, please contact us.

Boolean Parenthesization Problem

Boolean Parenthesization problem

Given a boolean expression, a string with True or False as operands and between each pair of operand,  there is boolean operator (and &, or | and xor ^). Find number of ways in which this Boolean expression can be parenthesized so that expression evaluates to True. This is known as Boolean Parenthesization problem. To understand problem better, let’s take some examples
Expression :

T ^ F & T

Two ways :

((T ^ F) & T) and (T ^ (F & T))

boolean parenthesization problem

T | T & F ^ T

Four ways :

((T|T)&(F^T)), (T|(T&(F^T))), (((T|T)&F)^T)
and (T|((T&F)^T))

boolean-parenthesization

Boolean Parenthesization problem : Line of thoughts

What will be the most trivial Boolean expression? Of course, an expression with only one Boolean value T or Boolean value F.

How many ways can this expression be parenthesized so that expression evaluates to True ? Apparently, there is only one way.

For Boolean value T, there is one way, (T); whereas for F, there no way we can parenthesize to evaluates True. An expression can evaluate to either True or False value.

Let’s say, T(i,j) is number of ways expression from i to j can be parenthesized so that it evaluates to True. Similarly, F(i,j) is number of ways expression evaluates to False. With base case, only one value either T or F is there, hence i=j, hence following equations hold true

T(i,i) = 1 if operand is T
         0 if operand is F

F(i,i) = 0 if operand is T
         1 if operand is F

How to calculate T(i, j) for expression with more than one values and operators between them?  This is something familiar to matrix chain multiplication problem. We will put parenthesis at all possible position and count how many ways these two resultant expressions hold True. Once we have count for each expression, we can combine count based on operator between split expression.

For expression from index i to index j, find k such that i<k<j, and find number of ways expressions from i to k and k+1 to j evaluates to True. Interesting, once these numbers are determined, number of ways for expression i to j can be calculated based on operator between expression i to k and k+1 to j.

When Boolean operator is & (AND)

When can expression (i,j) be True if expression is of form Expression(i, k) & Expression(k+1, j)?  Only if Expression(i,k) and Expression(k+1,j) are  both True. Hence, for any k, expression can be True in T(i,k) * T(k+1, j) where T(i,k) is number of ways Expression(i,k) is True and T(k+1, j) is number of ways Expression(j+1, j) is True. For all possible values of k, expression becomes

T(i,j)  = Summation ( T(i,k) * T(k+1,j)) for all k such that i < k < j

How about expression (i,j) being evaluates to False? Simple enough, one of the two expression should evaluate to False.

If Total(i,j) represents total number of ways an expression can be parenthesized irrespective of out being True or False, then

Total(i,j) =  Total(i,k) * Total(k+1, j)
or
Total(i,j) = T(i,j) + F(i,j)

If we take out number of ways an expression can parenthesized as True from Total, it gives number of ways it can be evaluates False. Hence, below equation

F(i,j) = Sum ( Total (i,j) - T(i,k)* T(k+1)) for all k for i< k< j
or
F(i,j) = Sum (Total(i,k) * Total(k+1, j) - T(i,k)* T(k+1) )

When Boolean operator | (OR)

In case, operator is OR, then, whole expression is True is any one of the expressions is True. How many ways both Exp(i,k) and Exp(k+1, j) be False.

Following the same logic from AND operator True, it can be derived that

F(i,j) = Summation (F(i,k)* F(k+1,j)) for all  i<k<j

Overall expression is True when both sub-expressions are not False. Hence.

T(i,j) = sum ( Total(i,j) - F(i,k)* F(k+1,j)) for k such i<k

In the same vein, T(i,j) and F(i,j) when operand is xor will be

T(i,j) = sum(T(i,k)*F(k+1,j) + F(i,k)* T(k+1,j)) for k such i<k

To find solution to Boolean parenthesis problem, find is T(1,N).

Implementation : Boolean parenthesization problem

package com.company;

/**
 * Created by sangar on 31.12.17.
 */
public class BooleanParenthesis {

    public static int calculateNumberOfWays(String operators, String operands){
        int numOperands = operands.length();


        int[][] F = new int[numOperands][numOperands];
        int[][] T = new int [numOperands][numOperands];

        for (int i=0; i<numOperands; i++){
            System.out.println(operands.charAt(i));
            F[i][i] = (operands.charAt(i) == 'F')? 1: 0;
            T[i][i] = (operands.charAt(i) == 'T')? 1: 0;
            System.out.println(T[i][i]);
        }

        for (int L=1; L<numOperands; L++) {
            for (int i=0; i<numOperands-L; ++i){
                int j = i+L;
                T[i][j] = F[i][j] = 0;
                for (int k=i; k<j; k++){
                    int totalIK = T[i][k] + F[i][k];
                    int totalKJ = T[k+1][j] + F[k+1][j];
                    if (operators.charAt(k) == '&') {
                        T[i][j] += T[i][k]*T[k+1][j];
                        F[i][j] += (totalIK *totalKJ - T[i][k]*T[k+1][j]);
                    }
                    if (operators.charAt(k) == '|'){
                        F[i][j] += F[i][k]*F[k+1][j];
                        T[i][j] += (totalIK*totalKJ - F[i][k]*F[k+1][j]);
                    }
                    if (operators.charAt(k) == '^'){
                        T[i][j] += F[i][k]*T[k+1][j] + T[i][k]*F[k+1][j];
                        F[i][j] += T[i][k]*T[k+1][j] + F[i][k]*F[k+1][j];
                    }
                }
            }
        }
        for(int i=0; i<numOperands; i++){
            for(int j=0; j<numOperands; j++){
                System.out.println("(" + i + "," + j + ") :"  + T[i][j]);
            }
        }
        return T[0][numOperands-1];
    }

    public static void main(String[] args) {

        String operands = "TTFT";
        String operators = "|&^";

        System.out.println("Number of ways to parenthisize expression : " +
                calculateNumberOfWays(operators, operands));

    }
}

Complexity of  dynamic programming approach to find ways to parenthesize a Boolean expression to evaluate it to True is O(n3). and space complexity is O(n2) .

Please share if there is something missing or wrong. If you want to contribute to algorithms and me and share your knowledge with thousands of learners across world, please contact us..

Find bridges in graph

Given a direct graph, detect bridges in the graph.

An edge is called as bridge edge if and only if on removal of that edge will increases number of components increase by one.

For example, in the below graphs, bridges are shown in green
bridges in graph

The concept of detecting bridges in a graph will be useful in solving the Euler path or tour problem.

Depth First Search of graph can be used to see if graph is connected or not. We can use the same concept, one by one remove each edge and see if the graph is still connected using DFS. If yes, then the edge is not bridge edge, if not, then edge is bridge edge.

However, this method entails quite a complexity of O(E * (V+E)) where E is number of edges and V is number of vertices.

Let’s think something better. Consider that we are looking at the edge (u,v) in a graph. In what condition, we can say that it is a bridge edge?
If we can somehow reach node u or any ancestor of u from any node which is a decedent of v, that means the graph is still connected and (u,v) is not a bridge edge. If the above condition is not possible, then (u,v) is the bridge.

How can we determine that there is no edge from decedent of v to u or its ancestor? For that we need to maintain time when a node was discovered during the depth-first search, call it tin[].

tin[u] is time when node u was discovered using DFS. If d[u] < d[v], means u was discovered before v.

Below is a graph with tin[u] filled for each node.
find bridges in a graph

Now, figure out the lowest tin[x] which can be reached from each node. Reason to find that is to see if there is a node x which is reachable from children of v and has tin[x] less than tin[u], i.e. x is ancestor of u reachable from children of v.

Store lowest DFS ancestor reachable from a node i in an array low[u].
low[u] = min(low[u], low[v])  for edge (u,v)

Idea here is that if (u,v) is an edge, then either there is no back edge from subtree of v to u and ancestor of u.
If there is a back edge to x from subtree of v, then minimum tin[x] reached by node in subtree will be assigned to the low[u].

The diagram shows the calculation of low[] in a graph.
bridge edges in a graph
Finally, if low[v] > tin[u] that means if discovery time of u is less than least ancestor that can be reached from subtree of v, we have a bridge, because there is no way we can reach to an ancestor of u once we disconnect edge (u,v).

Lots of theory, let’s code it. We will be modifying Depth First Search implementation to keep track of tin[] and low[].

Bridges in a graph implementation

package AlgorithmsAndMe;

import java.util.*;

public class Bridges {

    Set<Integer> visited = new HashSet<>();
    /* This map stores the time when the
    current node is visited
     */
    Map<Integer, Integer> tin = new HashMap<>();

    /*
      low will store minimum on 
       tin[v]
       tin[p] for all p for which (v,p) is a back edge
       low[to] for all to for which (v,to) is a tree edge
     */
    Map<Integer, Integer> low = new HashMap<>();
    
    //To maintain monotonic increasing order.
    int timer;

    void dfs(Graph g, int u, int parent) {
        visited.add(u);

        //Put the current timer.
        tin.put(u, timer);
        //Low is the time of entry to start with
        low.put(u,timer);
        
        timer++;
        
        /*
            Go through all the neighbors
         */
        for (int to : g.getNeighbors(u)) {
            //If it is parent, nothing to be done
            if (to == parent) continue;
            
            /* If the neighbor was already visited
                get the minimum of the neighbor entry time
                or the current low of the node.
             */
            if (visited.contains(to)) {
                low.put(u, Math.min(low.getOrDefault(u, Integer.MAX_VALUE),
                        tin.getOrDefault(to, Integer.MAX_VALUE)));
            } else {
                //Else do the DFS
                dfs(g, to, u);
                /*
                 Normal edge scenario,
                 take the minimum of low of the parent and the child. 
                 */
                low.put(u, Math.min(low.getOrDefault(u, Integer.MAX_VALUE),
                        low.getOrDefault(to, Integer.MAX_VALUE)));
                
                /* If low of the child node is less than
                   time of entry of current node, then
                   there is a bridge.
                 */
                if (low.get(to) > tin.get(u))
                    System.out.println(u + "->" + to);
            }
        }
    }

    public void findBridges(Graph g) {
        timer = 0;
        Iterator it = g.getNodes().iterator();
        while(it.hasNext()){
            int i = (int) it.next();
            if (!visited.contains(i))
                dfs(g, i, -1);
        }
    }
}

The complexity of finding bridges in a graph is O(V+E) where V is number of vertices and E is number of edges in graph.

Problems you can solve using this concept:
796 – Critical Links

Most frequent words in file

Most frequent words in file

In last post:  find K smallest element in an array, we learned some concepts to find top or bottom element in a given set. Let’s apply those concept again to a different problem called most frequent words in a file.

Given a text file which contains strings/words, find n most frequently occurring words in it i.e. n words whose count is the maximum.

For example, if given file is like follows: one, two, two, three, three, three, four,four, four,four, five, five, five, five, five, six,six, six, six, six, six  and we are looking for three most frequent words, output should be :  six,five, four.

Line of thoughts

Brute force solution would be really easy, scan the whole file, get the count for each unique words in file. Then sort the output based on that count in descending order and then return first n words.

This problem has three parts to it. First, read all words from file, second created a map which store frequency count of each word on file. Third is to get top n words from that map.

Reading a file is pretty standard operation in any language.  Brush upon Java basics here. We will not focus on that and also that’s not the intention of this question.
Assuming we can read from the file, how can we store frequency count against words. Simple, use a hash map. We read word from file, store in hash if it is not already there with count 1. If words is already in hash map, update the count by 1.

After this step, we have a hash with count of occurrence of each word. Now comes the challenging part:  how to find top n or most frequent words from this hash map. Mind you that hash map does not store elements in sorted or any order. 

Rule of thumb is to find top or least from collection of items, heaps are best bet. To find top N most frequently occurring words, let’s try heap. 
Which heap would be best?  We need to get a limited set, if we have free entry in that set till n words(as we need n top words). All further words have to pass a test before they enter the set. 

If new word is less than the least frequent word in the set, what can be said about this new word? Well, it cannot be in top n words right? 
If new word has frequency more than word with least frequency in set, new word should enter the set and  word with least frequency should be moved out.
What we just explained is typical use of min heap, as it give least element at the root. To find top n most frequent words in file, below is the algorithm.

Most frequent words in file : algorithm

  1. Take first N words appearing in map along with their count and create a min heap with these N words.
  2. One by one read words from hash and check if frequency of new word is more than least frequent word on heap, i.e word at root of heap.
  3. If yes, remove root and add new word in min heap. If not, continue with next word.
  4. When done with all words in hash, min heap will contain N most frequently occurring words in file.

Implementation

package com.company;

import javafx.util.Pair;

import java.io.IOException;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.*;

/**
 * Created by sangar on 1.10.18.
 */
public class FrequentWords {

	public static HashMap<String, Integer> readFile(String fileName)
		throws IOException {
	HashMap<String, Integer> wordMap = new HashMap<>();

	Path path = Paths.get(fileName);
	try (Scanner scanner =  new Scanner(path)){
		while (scanner.hasNextLine()){
			String line = scanner.nextLine();
			if(wordMap.containsKey(line)) {
				wordMap.put(line, wordMap.get(line) + 1);
			}
			else{
				wordMap.put(line, 1);
			}
		}
	}
	return wordMap;
	}

	public static ArrayList<String> mostFrequentWords(String fileName, int n){
		ArrayList<String> topWords = new ArrayList<>();

		try {
			HashMap<String, Integer> wordMap = readFile(fileName);
			PriorityQueue<Pair<String, Integer>> pq =
				new PriorityQueue<>(n, (x,y) -> x.getValue().compareTo(y.getValue()));

			int i = 0;
			Iterator it = wordMap.entrySet().iterator();
			/*
				Get first n words on heap
			*/
			while(it.hasNext()){
				if(i == n) break;
				HashMap.Entry<String, Integer> entry =
					(HashMap.Entry<String, Integer>)it.next();
				pq.add(new Pair<>(entry.getKey(), entry.getValue()));
				it.remove();
				i++;
			}

			/*
				Check all other words, if anyone more than least
				remove the least and add the new word.
			*/
			for (String key : wordMap.keySet()){
				if(pq.peek().getValue() < wordMap.get(key)){
					pq.poll();
					pq.add(new Pair<>(key, wordMap.get(key)));
				}
			}
			while(!pq.isEmpty()){
				topWords.add(pq.poll().getKey());
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
		return topWords;
	}
	
	public static void main(String[] args){  
		System.out.println(mostFrequentWords("/home/sangar/Documents/test.txt", 3));
	}
}

Reading M words from file will require O(m) time, where as creating N element heap will take O(n). Also, scanning through all words and inserting them on to heap has complexity of O((m-n) log n). Overall complexity to find top n most frequent words in fileis O(m log m).


Clone linked list with random pointer

Given a linked list with every node has two pointers: next and random, ask is to clone this linked list with a random pointer to a new linked list.
The linked list will look like:
clone list with random pointer

This problem can be solved using n extra spaces where we store a mapping of the existing node and new node in a hash map, then go through the linked list again, find the copy node of the current node, find copy node for its next, and link them. Then find the random pointer node of the current node, find the corresponding clone node of the random node, and link random pointer of the current nodes copy node to cloned random node. It takes 2 scans of the linked list as well.

However, the challenge is to do it in O(1) space complexity.

Thought process

We are using hashmap to know the corresponding cloned node of a node in the linked list, can we do that without using hashmap? Can we use the linked list itself to store the information?
The idea here is to add the cloned node after the original node in the given linked list. For each node, we will insert the cloned node between the original node and its next node. After inserting the nodes as a subsequent node of the original node, we can easily get the mapping we were storing in the hashmap right?
clone a linked list

Once, all the nodes are linked together, we can copy the random pointer of the original node to the random pointer of the cloned node as

node.next.random = node.random.next


The last step will be to separate the two lists. We go through the list, for each node, we will get the cloned node by node.next, next of the current original node should be the next of the cloned node.

Node clonedNode = node.next;
node.next = cloneNode.next;

Last, we have to link the cloned nodes next to node.next.next and move forward to the next node of the original node.

Overall, this implementation required 3 passes to the linked list, first to insert nodes in between, then to copy the random pointers and then to detach the cloned linked list. Pass 2 and 3 can be combined but it is easier to understand that way.

Show me the implementation

/*
// Definition for a Node.
class Node {
    public int val;
    public Node next;
    public Node random;

    public Node() {}

    public Node(int _val,Node _next,Node _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
    public Node copyRandomList(Node head) {
        
        Node current = head;
        if(head == null) return null;
        
        /* Step 1. create clones of each node and
            insert them next to the original node.
            List [1,2,3] will look like [1,1,2,2,3,3]
        */
        while(current != null){
            //create node.
            Node newNode = new Node(current.val);
            
            //Insert to the next of current
            newNode.next = current.next;
            current.next = newNode;
            
            current = newNode.next;
        }
        
        /* Step 2. Copy the random pointers.
        The cloned node's random will point to the 
        next of the original node.
        */
        current = head;
        while(current != null){
            if(current.random != null){
                //current.next is cloned node. it's random points
                //to next of current node's random.
                current.next.random = current.random.next;
            }
            current = current.next.next;
        }
        
        current = head;
        Node newHead = head.next;
        /* Step 3 : Detach the cloned list from the original list */
        while(current != null){
            Node node = current.next;
            current.next = current.next.next;
            //IMPORTANT: Check for the last node.
            if(current.next != null){
                node.next = current.next.next;
            }
            current = current.next;
        } 
        
        //Return new head
        return newHead;
    }
}

The time complexity of above implementation is O(N) and space complexity is O(1)

Palindrome anagram

Given a string, find out if any anagram of a given string is a palindrome. For example, “AABBC” has an anagram “ABCBA” which is a palindrome.
The brute force solution will be to find all anagrams of string and then check each one if that is a palindrome. For N character long string, we will have n! anagrams, and checking each one of that for palindrome will be a computation-intensive task, so not a good solution.

What is required for a string to be palindrome string? We need first half of the string to contain the same characters as the second half. In the case of odd length string, we can safely ignore the middle character.
In other terms, each character should occur even a number of times except one which is a middle character that may occur an odd number of times. Best way to check if the character occurs even number of times is to increment to count when it is zero and decrement when it is 1.If at the end we have count corresponding to that character as zero, that means we have even number of occurrence of this character, if not then we have an odd number of occurrence.

Extending the same idea from the previous post: we will be using a hash table and increment- decrement the corresponding count of character in the hash. In the end, we will sum the array and if the sum of the array is greater than 1, then we cannot have any anagram which will be palindrome else at least anagram of the string will be a palindrome.

The complexity of above code is O(N) with a constant amount of memory required.

Anagrams : Find if two strings are anagrams

Check if strings are anagram

Given two strings, find out if they are anagrams of each other. Strings are said to be anagrams if they have same characters but in different order.For example, abcd and dcba are anagrams.

Analysis

It’s actually a simple problem, we need to just check if both the strings contain same characters. 
First approach will be to sort both the string and compare if they are same. While sorting all the characters will come in lexicographical order and string with same characters will have same order of characters.
Best we can achieve using sort is O(N log N).
Can we do better? We have to keep track of character in one string in another. So if we find what all characters (count of each character) are there in first string, we can easily do that using hash table and compare with characters (count again) present in second string. If both the hash tables are equal, we can say that strings are anagrams.
Here we are using two hash tables. We can do away with on hash table. How?
While traversing the first string we will increment the count against character. While traversing the second string, we will decrement the count against character in the same hash table. If at any time if count of any character goes less than zero, it means, character is present in second string but not in first, so we can say strings are not anagrams.
If we finish complete scanning of second string, we return true.
To avoid check the hash table at the end for non zero count, we can first have a check on length of two strings, if lengths are not equal, straightforwardly say non anagrams. (Think how it avoids check of non zero count at the end :))

Code to find if strings are anagrams

Complexity Analysis

Complexity of algorithm to identify to strings as anagrams is O(N) where N is length of string.

Vertical sum of nodes in BST

Vertical sum of nodes in BST

Given a binary search tree, sum all the nodes which are on the same vertical line. This problem is known as a vertical sum problem. For example, given a binary tree as shown below
vertical sum in binary tree

the output will be:
Sum of vertical line 1 = 2
Sum of vertical line 2 = 3
Sum of vertical line 3 = 18
Sum of vertical line 4 = 8
Sum of vertical line 5 = 9

Algorithm

To add the node to a particular line we have to reach that node. Question is what kind of traversal will be best suited for this problem? Imagine we have a binary that has only one level, root. It will be easy to say that the sum of the only vertical line is the root itself. What if there are two levels? Then we have three lines, first contains the left child of the root, second contains root itself, and third the right child.

As we increase the levels, the number of lines also increase and we can easily know that by moving the counter, increment it when we move to right and decrement when moving to left. So, it requires level order traversal of the binary tree.

package AlgorithmsAndMe;
import java.util.*;

public class VerticalSum {
    public Map<Integer,Integer> getVerticalSum(TreeNode root){

        class VerticalInfo {
            TreeNode node;
            int line;

            public VerticalInfo(TreeNode node, int line){
                this.node = node;
                this.line = line;
            }
        };

        Queue<VerticalInfo> queue = new LinkedList<>();
        Map<Integer, Integer> verticalSum = new HashMap<>();

        if(root == null) return verticalSum;

        queue.add(new VerticalInfo(root, 0));

        while (!queue.isEmpty()){
            VerticalInfo current = queue.poll();
            if(!verticalSum.containsKey(current.line)){
                verticalSum.put(current.line,0);
            }

            /* add to the corresponding line */
            verticalSum.put(current.line,
                    (int)verticalSum.get(current.line) 
                    + (int)current.node.getValue());

            if(current.node.getLeft()!= null){
                //decrrement the line number when moving left.
                queue.add(new VerticalInfo(current.node.getLeft(), 
                                           current.line-1)
                );
            }
            if(current.node.getRight()!= null){
                // Increment the line when moving right
                queue.add(new VerticalInfo(current.node.getRight(), 
                                           current.line + 1)
                );
            }
        }
        return verticalSum;
    }
}

The complexity of the above implementation will be O(n) because we traverse all the nodes if the tree at least once.

Please share if there is anything wrong or missing. If you are looking for coaching to prepare for your interview, please reach book a free session

Palindrome linked list

Palindrome linked list

First of all, what is a palindrome linked list? A linked list is palindrome if you get the same output by traversing it from head to tail or tail to head. For example, below linked list is a palindrome linked list as forward traversal is same as reverse traversal : 3,4,5,5,4,3

is linked list palindrome
palindrome linked list

Where as this linked list is not palindrome for obvious reasons.

palindrome linked list
Non palindrome linked list

Given a singly linked list, find if linked list is palindrome or not.

This problem will give us more understanding on how to iterate over singly linked list as well as how to handle linked lists in recursive functions. 

If linked list is palindrome : thoughts

What will be the brute force solution for the problem? We can scan the linked first and store the output in an storage. Then we reverse the linked list, and see if order of elements is same as what was in previous traversal.

Complexity of brute force solution is O(n), however, it requires three full traversals of linked list; first forward traversal, then to reverse linked list and then reverse traversal. Also, it require additional O(n) space.

We can put half of the linked list on stack. Traverse remaining half, for each node, same time, pop the node from stack, if data is equal, move forward, else return false. If you reach the end of linked list with stack empty, linked list is palindrome. Complexity is O(n) with additional space complexity of O(n).

is linked list palindrome
Scan till middle of linked list and push all elements in stack
Now, pop the element from stack as we move in linked list. If they are equal, continue
else return false 

if linked list is palindrome
Next node is popped and compared
we reached the end of linked list and stack is empty. Hence, linked list is palindrome

What can be better? We are interested in if only half of the linked list, rest half have to be checked w.r.t to first half we they are same of not.

If we divide linked list in two halves exactly at the middle, and reverse first half, then if all the nodes from middle node to end are same as middle to start node, linked list is palindrome.

We have to reverse only half of the linked list.

We traverse linked list to find the size, then reverse half the list, traverse again to check if first half is same as latter half. You have to take middle based on the fact if size of linked list odd or even.
Actually, you can avoid calculating the size, by following the hare and tortoise algorithm to find middle of linked list. Overall complexity is O(n) with no additional space required.

Implementation

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

#define true 1
#define false 0

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

typedef struct Node {
  int data;
  struct Node * next;
} Node;

Node * createNode(int val){
  Node * temp = (Node *)malloc(sizeof(Node));
  if(temp){
    temp->data = val;
    temp->next = NULL;
  }
  return temp;
}

/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
	Node * newNode  = createNode(data);
	newNode->next = *headRef;
	*headRef  = newNode;
}

void printList(Node *head){
	while(head){
		printf("%d->", head->data);
		head = head->next;
	}
	printf("Null");
}

/* We are returning next node as it will be required
	in calling function */
Node * reverseList(Node *node){
    Node *current = node;
    Node *prev = NULL;
    Node *next = node;

    while(current){
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

int isPalindromeList(Node *head){

    if(!(head && head->next)) return true;

    Node *current = head;
    Node *fast = head;
    Node *prev = NULL;
    Node *midNode = NULL;
    /* We are finding the middle node.*/
    while(fast && fast->next){
        fast = fast->next->next;
        /* We are saving previous node because 
		that will be end of fist list
        in case of even number of nodes */
        prev = current;
        current = current->next;
    }

    /*Check if there are odd number of nodes, if fast pointer is
	null, then there are even number of nodes,
		else it's odd number 
	*/
    if(fast){
    	midNode = current;
    	current = current->next;
    }
    
    //Let's reverse second half of list
    Node *reversedSecondHalfHead = reverseList(current);
    
    //Terminate first linked list
    prev->next  = NULL;
    
    int isPalindrome = compareTwoLinkedLists(head,
							reversedSecondHalfHead);
    
    //Reverse back second half
    current = reverseList(reversedSecondHalfHead);
    
    //If there are odd number of nodes, midNode should not be null
    if(midNode){
    	prev->next = midNode;
    	midNode->next = current;
    }
    else
    	prev->next = current;
    	
    return isPalindrome;
}

int main(void) {
	
	Node *head = NULL;
	push(&head, 3);
	push(&head, 4);
	push(&head, 5);
	push(&head, 6);
	push(&head, 5);
	push(&head, 4);
	push(&head, 3);
	printf("\nOriginal list :");
	printList(head);
	printf("\nIs list palindrome : %s", isPalindromeList(head)
		? "true" :"false");
	return 0;
}

Is palindrome linked list : recursive solution

To check if string is palindrome, standard way is to keep two pointers (i and j), i moving from left to right and j moving from right to left.  We check if character at i and j match or not.  If they don’t match, string is not palindrome. If i and j cross each other, string is palindrome.
Can we apply above algorithm on linked list? No, because we cannot move backward in singly linked list. So what is the way? How about simulating the stack using recursive function.

We use two pointers, forward and backward, we move backward pointer ahead till we reach the end of linked list, that will be the terminal condition of recursive function. At any given time after hitting the terminal condition, forward and backward pointers will be n nodes from start and end respectively, where n varies from 0 to n.
We check if content of both pointers are equal or not, if not, then linked list is not palindrome, if yes, linked list is palindrome till those nodes.

Palindrome linked list : implementation

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

#define true 1
#define false 0

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

typedef struct Node {
  int data;
  struct Node * next;
} Node;

Node * createNode(int val){
  Node * temp = (Node *)malloc(sizeof(Node));
  if(temp){
    temp->data = val;
    temp->next = NULL;
  }
  return temp;
}

/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
	Node * newNode  = createNode(data);
	newNode->next = *headRef;
	*headRef  = newNode;
}

void printList(Node *head){
	while(head){
		printf("%d->", head->data);
		head = head->next;
	}
	printf("Null");
}

int isPalindromeUtil(Node **forward, Node *backward){
	//There are no nodes is lists
	if(!backward) return true;
	
	/*we are recursing moving backward pointer ahead. Backward
	pointer will start moving backward once we hit
	above terminal condition of recursion */
	int isPalindrome = isPalindromeUtil(forward, backward->next);
	
	if(!isPalindrome) return isPalindrome;
	/*At this point forward is n nodes ahead from start and
	backward n nodes away from end n varies from 0 to n 
	Compare forwad and backward
	*/
	if((*forward)->data != backward->data){
		return false;
	}
	//Move ahead forward pointer, backward will move back
	automatically due to recursion
	*forward = (*forward)->next;
	
	return isPalindrome;
}

int isPalindromeListRecursiveMethod(Node *head){
	/* we are starting with forward pointer and backward at head.
	Notice that we passing reference to forward and just pointer
	for backward pointer */
    return isPalindromeUtil(&head, head);
}

int main(void) {
	
	Node *head = NULL;
	push(&head, 3);
	push(&head, 4);
	push(&head, 5);
	push(&head, 6);
	push(&head, 5);
	push(&head, 4);
	push(&head, 2);
	printf("\nOriginal list :");
	printList(head);
	printf("\nIs list palindrome : %s",
	    isPalindromeListRecursiveMethod(head) ? "true" :"false");
	return 0;
}

Complexity of algorithm to check if linked list is palindrome or not is O(n).

Please share if there is something missing or wrong. If you are interested in receiving study material for your interview preparation, please signup on Algorithms and Me mailing list.

Next greater element in array

Next greater element in array

Given an array of integers, find next greater element for current element in array i.e. for each a[i], find minimum j so that a[j] > a[i] and j>i.

For the rightmost element, value will be -1. For any i, if there is no such j, then result for that too will be -1.
In simple terms, we need to find nearest greater number for each element in given array. For example:

Next greater element in array: Line of thought

Brute force method would be to scan array in two loops. For each element in array, scan remaining right side elements and find out the greater number. Complexity of code is O(n2). How can we do better and solve this in linear time?

What if while scanning the array, we keep track of all numbers for which greater number is yet not found. Idea is that whenever we see a number, check if there are elements which are already visited in array and yet there is no greater number assigned to them. If there are such elements, we check if current element is greater than them. If yes, then for all those numbers which are less than current element, next greater element will be current number. However, we have yet not find next greater number for current number, so put it back to list.

This list will be in decreasing order, as we will be removing all the numbers which are less than current number fro the list. They got current number as next greater number. All remaining numbers on list will be greater than current number. What will be the best data structure store this list? Stack, as we are interested in last element first.
This problem is very similar to stock span problem.

Next greater element in array : Algorithm

  1. Push first element on to stack
  2. While(!stack.empty && stack.peek() < current) stack.pop()
  3. Pair all popped numbers with current number
  4. If stack.top() > current or stack.empty(), stack.push(current)
  5. After scanning all elements in array, print all elements in stack paired with -1 as there is no greater element on right side of these elements.

Next greater element in array : Implementation

package com.company;

import javafx.util.Pair;

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

/**
 * Created by sangar on 19.9.18.
 */
public class NextGreaterElement {
    public static ArrayList<Pair<Integer, Integer>> nextGreaterElement(int[] a){

        Stack<Integer> s = new Stack();
        ArrayList<Pair<Integer,Integer>> nextGreater = new ArrayList<>();

        for(int i=0; i<a.length; i++){
            while(!s.empty() && a[i] > s.peek()) {
                nextGreater.add(new Pair<>(s.pop(), a[i]));
            }
            s.push(a[i]);
        }
        while(!s.empty()) nextGreater.add(new Pair<>(s.pop(), -1));
        return nextGreater;
    }

    public static void main(String args[]){
        int a[] = {100, 60, 70, 65, 80, 85, 45, 77, 56, 98};
        ArrayList<Pair<Integer, Integer>> nextGreater = nextGreaterElement(a);

        System.out.println(nextGreater);

    }
}

Let’s workout an example: A = {5,6,3,35,23,6,8}. we start with empty stack = []. For the first element, we have empty stack, add 5 to stack. Now, stack = [5]

For next element 6, stack is not empty and element at the top of stack is less than 6. We will pop 5 from stack and create a pair. Output = {(5,6)}, we will push 6 back on to stack. stack = [6]

Next element is 3, which is less than top of stack, do nothing, and put the element on top of stack, stack = [6,3]

For 35, pop out 3 and 6 from stack and create pairs and add them to list. Output = {(5,6),(6,35), (3,35)}, add 35 to stack, stack = [35]

Next element is 23, which is less than top of stack, do nothing, and put the element on top of stack, stack = [35,23]

Again element 6, is less than top of stack, do nothing, and put the element on top of stack, stack = [35,23,6]

For 8, top of stack is less than 8, so pop and create pair and add to output. Output = {(5,6),(6,35), (3,35),(6,8)}, add 8 to stack, stack = [35,23,8]

Now there are not elements left, pop everything from stack and pair them with -1. Final output should be {(5,6), (6,35), (3,35), (6,8), (8, -1), (23, -1), (35, -1)}

Complexity of algorithm to find next greater element in array will be O(N) with extra space complexity of O(N) for stack.

Please share if there is something missing or wrong. If you are interested in taking personalized coaching for your interview preparations, please reach out to [email protected]