## Minimum in sorted rotated array

In post find element in sorted rotated array, we discussed an algorithm based on binary search, to find a given key in sorted rotated array.

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). Find the minimum element. You may assume no duplicate exists in the array.

To understand the problem, let’s understand what is a sorted array, and then what is sorted rotated array?

An array is called sorted where for all i and j such that i < j, A[i] <= A[j].
A rotation happens when the last element of an array is pushed at the start and all elements of array move right by one position. This is called as rotation by 1. If the new last element is also pushed to start again, all elements are moved to the right, it’s a rotation by 2, and so on.

Find minimum in sorted rotated array problem is asked during telephonic or online coding rounds of companies like Microsoft or Amazon.

## Minimum in sorted rotated array and binary search algorithm

As always, first, come up with a brute force solution without worrying about any optimizations as of now. The simplest way would be to scan through the array and keep track of the minimum. The complexity of this method is O(n).

In the brute force solution, we did not use the fact that the array is sorted and then rotated. Let’s forget about rotation and concentrate only on the sorted part.

What is the minimum element in a sorted array? Obviously, it is the first element of the array. We see that all the elements on the right side of the minimum elements are greater than the minimum.

What will happen if start rotating array now, is the condition that all the elements on the right of the minimum element are greater than it still holds? Yes, it does. Either there will be no element on the right side of minimum or the will be definitely greater than it. So it is obvious, that the first element in the sorted part of the array is a candidate for the minimum element in a sorted rotated array, rest all can be discard.

What if we start with the middle element. How do I know that if array on the right side of it is sorted or not? What information comparison between the middle and end gives us?

If middle element is less than the last element, the array is sorted from index mid to end, in this case, we have to look for minimum on the left part including the mid

If the middle element will be greater than the last element, array on the right side is not sorted, there must be someplace in this right part, where the sorted array start, hence minimum element should be in the right part of the array.

When should we stop? Well, what is the minimum of an array with only one element? The element itself. We will also stop when there is only 1 element left.

### Algorithm to find minimum in sorted rotated array

1. Find mid = start + (end- start) /2
2. See if mid is part of sorted array or not, check A[mid] < A[end]
3. If yes, minimum should be on the left part
4. If no, minimum should be on the right part

### Minimum in sorted rotated array implementation

```class Solution {
public int findMin(int[] nums) {

int start = 0;
int end = nums.length-1; //O(1)
int mid;

while(start < end){
mid = start + ((end - start)/2);

if(nums[mid]<nums[end]){
end = mid;
}
else{
start = mid+1;
}
}

return nums[start];
}
}
```

The complexity of the algorithm to find minimum in a sorted rotated array is O(logn) because of binary search algorithm.

This problem is asked in many variations like find pivot in a sorted rotated array or find the number of rotations.

Interview coming up? Check out our full coding interview prep course. There’s a get-the-job-or-your-money-back guarantee, so it only costs money if it actually works.

As always, shoot me an email if there’s anything I can help with.

## 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))`

```#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.

# 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))

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 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

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.

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.

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) {

//Put the current timer.
tin.put(u, timer);
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:

# 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 {
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();
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();
}
}
while(!pq.isEmpty()){
}
} catch (IOException e) {
e.printStackTrace();
}
}

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:

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?

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 {

/* 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.
*/
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;
}

/* 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;
}

}
}
```

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.

# 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

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

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;
}
};

Map<Integer, Integer> verticalSum = new HashMap<>();

if(root == null) return verticalSum;

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.
current.line-1)
);
}
if(current.node.getRight()!= null){
// Increment the line when moving right
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

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

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

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)`.

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 */
Node * newNode  = createNode(data);
}

}
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;
}

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

prev->next  = NULL;

//Reverse back second half

//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) {

printf("\nOriginal list :");
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 */
Node * newNode  = createNode(data);
}

}
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
*/
if((*forward)->data != backward->data){
return false;
}
//Move ahead forward pointer, backward will move back
automatically due to recursion
*forward = (*forward)->next;

return isPalindrome;
}

/* we are starting with forward pointer and backward at head.
Notice that we passing reference to forward and just pointer
for backward pointer */
}

int main(void) {