Find the day on which stock should be bought and sell, to have maximum profit, Stock can be bought and sold only once.

Problem Explanation

Given an array with the price of stocks on different days. A person can buy and sell stock only once.Compute the maximum profit can be made in that single transaction.

If person cannot make any profit, return 0 as an answer

Example

Sample Input:  [9,8,7,6,5,4,3]  Expected output: 6 {9-3}

Sample Input:  [3,4,5,6,7,8,9]  Expected output: 0

Sample Input: [7,1,5,3,6,4]  Expected output: 6 {7-1}

Solution

For this solution we will use Print next Greatest Element for entry in an Array

```
public int currentSolution(int[] input){

<code class="java keyword">if</code><code class="java plain">(input == </code><code class="java keyword">null</code> <code class="java plain">|| input.length <=</code><code class="java value">1</code> <code class="java plain">) </code><code class="java keyword">return</code> 0;

int n = input.length;

int currentMax = 0;

String[] nextGreater = solution(input);

for(int i =0;i<n;i++){

String value = nextGreater[i];

if(value.equals("MAX")){

continue;

}

int nextValue =Integer.valueOf(value);

currentMax = Math.max(currentMax, nextvalue - input[i]);

}

return currentMax;

}

```

TimeComplexity: O(n)

Space Complexity: O(n)

Print next Greatest Element for entry in an Array.

Problem

Given an array, which can have positive and negative numbers, write a code to print the next greatest element for each element. For the last number, next greater element will always be Integer.MIN.

For element, for which no greater number is present, print Integer.MIN.

Example – input array – [7,1,5,3,6,4]

Expected output – [MIN,6,6,6,MIN,MIN] .{MIN is considered as Integer.MIN}

Method to implement :

```
public String[] solution(int[] input);

```

Solution

```
public String[] solution(int[] input){

if(input == null || input.length <=1 ) return null;
int n = input.length;
String[] result = new String[n];
Stack<Integer> s = new Stack<>();
result[n-1] = "MIN";
s.push(input[n-1]);

for(int i = n-2;i>=0;i--){

while (!s.empty() && s.peek() < input[i]){
s.pop();
}
if(s.isEmpty()){
result[i] = "MIN";
s.push(input[i]);

}else{
result[i] = s.peek().toString();

}

}
return result;
}
```

Hashing And Different Techniques

What is hashing why we need it?

Consider it as a process of converting any input to an integer value.A string can have a hash value, a java Object can have hash value.

We need it to place these input to particular cell or bucket.So that whenever we need to find this object, we will find it in particular cell or bucket only.This will decrease the search time for an input object.

Good Hashing Techniques

Since we need to convert the input value to some integer value, method or step to convert it should be simple and faster, as a user should not spend much time and effort on the secondary task.The second thing you should keep in mind is that your function should create different int value for different input for maximum cases.Otherwise, you will end up keeping elements in single or only a few buckets which will make search more problematic.

Two thing you have to learn is

This is a minimum of hashing everyone should know.Will try to cover the hashing in depth in my upcoming blogs.

Given an array, find all the subsets

int arr[] = {1,2,3,4,5};
int level= 0;

for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
subset(arr[i]+””,i+1,arr);

}
}

private void subset(String i, int level,int[] arr) {

for (int j = level; j < arr.length; j++) {
System.out.println(i+””+arr[j]);
subset(i+””+arr[j],j+1,arr);

}

Find the all the lexical pair from the given array of strings.

lexical pairs

Vector<String> v = new Vector<String>();
Set<String> s = new HashSet<String>();
Boolean lexical = false,found = false;
System.out.println(“case 2”);

int lenght = v.size(),count = 0;

for (int i = 0; i < v.size(); i++) {
String source = v.get(i);

source = source.toLowerCase();
char[] sourceWord = source.toCharArray();
Arrays.sort(sourceWord);
source = new String(sourceWord);
//System.out.println(“source “+source);
count =0;
for (int j = i+1; j < v.size(); j++) {

String target = v.get(j);
target = target.toLowerCase();
char[] targetWord = target.toCharArray();
Arrays.sort(targetWord);
target = new String(targetWord);

if(source.equals(target)){
lexical = true;

System.out.print(v.get(i)+” “);
System.out.println(v.get(j));
continue;
// v.remove(v.get(j));

}

}
if(count>0)
System.out.println(“”);
}

if(!lexical){
System.out.println(“No such pairs”);
}

Given a matrix with each cell containing each number of candies, and a constraint that you can move only right or down, from the top left corner to the bottom right corner, find the path that gets you maximum candies.

Note: This result will print the all the possible path cost , you can fetch the path with maximum candies.

int matrix[][] = {{0,5,7},{7,9,1},{2,7,11}};
int rows = matrix.length,column = matrix.length;
System.out.println(“rows : “+rows );
System.out.println(“columns : “+column);
int TotalSum = 0,sum=0;

FindTheTotalSum(0,0,sum,rows,column,matrix);

}

private void FindTheTotalSum(int i, int j, int sum,int rows,int column,int[][] arr) {

if((i==column-1)&&(j==rows-1)){
System.out.println(sum+” sum of the path”);
}
sum = sum + arr[j][i];
if(i<column-1){
FindTheTotalSum(i+1, j, sum, rows, column,arr);
}
if(j<rows-1){
FindTheTotalSum(i, j+1, sum, rows, column,arr);
}

}

Stack implementation Algorithm

Stack Implementation

It works on first in last Out.

Variables

top =0;

//boundary value:- if stack has a limit;
if(top<limit){
top ++;
}else{
stack full
}

remove (pop)
if(top !=0){

take value from top
top–
}else{
stack Empty
}

Traversal

in order of first in

for (i = 1;i<=top;i++){
print element at i
}

WikiPedia Link  , refer for stack theory.

http://en.wikipedia.org/wiki/Stack_(abstract_data_type)