In this post, we will see how to find smallest and largest element in an array.

Problem:

You are given an array of numbers. You need to find smallest and largest numbers in the array.

Solution:

  • Initialise two variable largest and smallest with arr[0]
  • Iterate over array
    • If current element is greater than largest, then assign current element to largest.
    • If current element is smaller than smallest, then assign current element to smallest.
  • You will get smallest and largest element in the end.

Java code to find Smallest and Largest Element in an Array :

package org.arpit.java2blog;
/*
Java program to Find Largest and Smallest Number in an Array 
*/
public class FindLargestSmallestNumberMain {

      public static void main(String[] args) {
             
              //array of 10 numbers
              int arr[] = new int[]{12,56,76,89,100,343,21,234};
             
              //assign first element of an array to largest and smallest
              int smallest = arr[0];
              int largest = arr[0];
             
              for(int i=1; i< arr.length; i++)
              {
                      if(arr[i] > largest)
                              largest = arr[i];
                      else if (arr[i] < smallest)
                              smallest = arr[i];
                     
              }
              System.out.println("Smallest Number is : " + smallest);
              System.out.println("Largest Number is : " + largest);            
      }
}
When you run above program, you will get below output:
Largest Number is : 343
Smallest Number is : 12

I have started writing about the Java Certifications and how to prepare for the various topics related to OCAJP exams in my blog. In my previous post, I have published how to handle exceptions and few sample mock questions for StringBuilder class.
In this post I am going to explain write down few more practice questions for OCAJP exam. I would provide 5 sample practice questions for static keyword. The exam objective is:
Apply the static keyword to methods and fields.

You will be tested in the exam about difference between static variables and instance variables. If two objects are trying to modify the static and instance variables, What will be the expected output?. The static variables and its use are not just required for the certification preparation; this is one of the important concepts in core java that has to be well understood by the programmers. Before you are trying these sample questions, you can read my article about static keyword.

If you are looking for mock exams to practice OCAJP exam, you can try these free practice questions for OCAJP 8 exam.

Static Keyword Mock Questions

1. What is the output ?

public class StaticDemo {
            int num1 = 6;
            static int num2 = 10;

      public static void main(String args[]) {
            StaticDemo s1 = new StaticDemo();
            StaticDemo s2 = new StaticDemo();
            s1.num1 = 15;
            s1.num2 = 17;
            s2.num1 = 22;
            s2.num2 = 28;
            System.out.println(s1.num1 + " " + s1.num2 + " " + s2.num1 + " "+ s2.num2);

   }
}
A. 15 17 22 28
B. 15 17 22 17
C. 15 28 22 28
D. 22 17 22 28
E. 22 28 22 28
F. compile time error

2. Which of the following will compile when inserted in the following code? (Choose all that apply)

public class Demo {

final String exam1 = "O";
static String exam2 = "C";

{
// CODE SNIPPET 1
  
}
static {
// CODE SNIPPET 2
  
}

}

A. exam1 = "A"; instead of // CODE SNIPPET 1
B. exam 2 = "J"; instead of // CODE SNIPPET 1
C. exam 1 = "P"; instead of // CODE SNIPPET 2
D. exam 2 = "8"; instead of // CODE SNIPPET 2
E. compile time error.
F. Exception at run time.

3. What is the output of the program ?

public class StaticDemo {

static String n1= examName("O");{
     n1=examName("A");
  }
static{
      n1=examName("C");
}
 public static void main(String[] args) {
           StaticDemo sd = new StaticDemo();

  }

public static String examName(String s){
          System.out.println(s);
        return s;
   }
}
A. It prints O C A in that order when run
B. It prints C A O in that order when run
C. It prints O A C in that order when run
D. It prints C A O in that order when run
E. Compile time error.
F. Exception at run time.

4. Which of the lines will fail to compile ?

public class StaticDemo {

StaticDemo sd = new StaticDemo();
void method1() {
   method4();  // 1
   StaticDemo.method2(); // 2
   StaticDemo.method3(); // 3

}

  static void method2() {
 }

  void method3() {
   method1(); //4
   method2(); //5
   sd.method2(); //6
}

   static void method4() {
   }
}
A. 1
B. 2
C. 3
D. 4
E. 5
F. 6
G. Compile time error.

5. What is the output ?

public class StaticDemo {

int num1 = 3;
static int num2 = 5;

StaticDemo(int num1, int num2) {

   if (num2 < 30) {
    this.num2 = num2;
   }
     num1 = num1;
}

  public static void main(String args[]) {

         StaticDemo s1 = new StaticDemo(9, 10);
         StaticDemo s2 = new StaticDemo(12, 22);

         System.out.println(s1.num1 + " " + s1.num2 + " " + s2.num1 + " "+ s2.num2);

  }
}
A. 9 10 12 22
B. 9 22 12 22
C. 9 10 12 10
D. 3 22 3 22
E. Compile time error.

Answers 

1. Correct option : C
You have created two objects and s1,s2 are the references. s1.num1=15 assigns value 15 to num1 variable, It doesn’t updates the value in s2 reference. s1.num2=17 assigns value 17 to num2 variable , it updates the value in s2 reference also because num2 is a static variable. s2.num1=22 assigns value 22 to num1 variable, It doesn’t updates the value in s1 reference. s2.num2=28 assigns value 28 to num2 variable , it updates the value in s1 reference also because num2 is a static variable.
2. Correct options : B,D
Options A,C are incorrect because exam1 is a final variable . You can’t re assign value to a final variable. B is correct because instance block can access static variable and can assign value to it. D is correct because static block can access static variable and can assign value to it.\
3. Correct option : A
To answer this you need to remember Java program execution order. First static variable s1 will be declared and calls examName method which prints O and returns O to it . Next static block will be executed it also calls examName method which prints C and returns C to it . Object is creating . There is one instance block . It will be executed before object creation. It calls examName method which prints A and returns A to it .
4. Correct Option : C
C is correct option because you are not allowed to use class name to call instance method. Line 1, 5 are correct , you can directly call static method from instance method without class name or reference variable of same type.
5. Correct Option : D
num1 = num1; It is assigning value to the same constructor parameter. It doesn’t affect the num1 instance variable in s1, s2 references . So num1 value is 3 in both the references. this.num2 = num2; It changes the static variable num2 in both s1, s2 references. References

If you are preparing for the OCAJP certification exam, the following references would be much useful.
OCAJP 8 Exam Curriculum
OCAJP Forums
How to prepare for OCAJP Exam?
What are the good books available for OCAJP 8 exam?

In this post, we will see about trie data structure in java.

What is Trie :

Trie is data structure which stores data in such a way that it can be retrieved faster and improve the performance.

Some real time examples:

Trie can be used to implement :
Dictionary
Searching contact in mobile phone book. 

Trie data structure:

You can insert words in trie and its children linked list will represent its child nodes and isEnd defines if it is end for the word.
Example:
Lets say, you want to insert do, deal , dear , he , hen , heat etc.
Your trie structure will look like as below:

TrieNode will have following variables and method.
class TrieNode 
{
    char data; 
    boolean isEnd; 
    int count;  
    LinkedList<TrieNode> childList; 
 
    /* Constructor */
    public TrieNode(char c)
    {
        childList = new LinkedList<TrieNode>();
        isEnd = false;
        data = c;
        count = 0;
    }  
    public TrieNode getChild(char c)
    {
        if (childList != null)
            for (TrieNode eachChild : childList)
                if (eachChild.data == c)
                    return eachChild;
        return null;
    }
}
Each TrieNode have access to its children if present at all. It contains current data, count , isEnd and childList. isEnd is a boolean variable which represents if current Trie node is end of word or not.childList will have list of children for that TrieNode.

Algorithm for inserting word in Trie structure:

  • If word already exists, return it.
  • Make current node as root trie node
  • Iterate over each character(lets say c) of word.
  • get child trie nodes for current node
    • If child node exists and is equal to character c then make it current node and increment the count.
    • If child node does not exist, then create a new trie node with character c and add it to current node childList and change current node to newly created trie node.
  • When you reach at end of the word, make isEnd = true.
Java Code:
/* This function is used to insert a word in trie*/
    public void insert(String word)
    {
        if (search(word) == true) 
            return;        
        TrieNode current = root; 
        for (char ch : word.toCharArray() )
        {
            TrieNode child = current.getChild(ch);
            if (child != null)
                current = child;
            else 
            {
             // If child not present, adding it io the list
                 current.childList.add(new TrieNode(ch));
                 current = current.getChild(ch);
            }
            current.count++;
        }
        current.isEnd = true;
    }

Algorithm for searching a word in Trie data structure:

  • For each character of word , see if child node exists for it.
    • If child node does not exists, return false
  • If character exists, repeat above step
  • When you reach at end of the String and current.isEnd is true then return true else return false.
   /* This function is used to search a word in trie*/
    public boolean search(String word)
    {
        TrieNode current = root;  
        for (char ch : word.toCharArray() )
        {
            if (current.getChild(ch) == null)
                return false;
            else
                current = current.getChild(ch);
        }      
        if (current.isEnd == true) 
            return true;
        return false;
    }

Java code to implement Trie data structure

package org.arpit.java2blog;
/*
 *  Java Program to Implement Trie
 */
 
import java.util.*;
 
class TrieNode 
{
    char data; 
    boolean isEnd; 
    int count;  
    LinkedList<TrieNode> childList; 
 
    /* Constructor */
    public TrieNode(char c)
    {
        childList = new LinkedList<TrieNode>();
        isEnd = false;
        data = c;
        count = 0;
    }  
    public TrieNode getChild(char c)
    {
        if (childList != null)
            for (TrieNode eachChild : childList)
                if (eachChild.data == c)
                    return eachChild;
        return null;
    }
}
 
public class TrieDataStructure
{
    private TrieNode root;
 
     /* Constructor */
    public TrieDataStructure()
    {
        root = new TrieNode(' '); 
    }
    /* This function is used to insert a word in trie*/
    public void insert(String word)
    {
        if (search(word) == true) 
            return;        
        TrieNode current = root; 
        for (char ch : word.toCharArray() )
        {
            TrieNode child = current.getChild(ch);
            if (child != null)
                current = child;
            else 
            {
             // If child not present, adding it io the list
                 current.childList.add(new TrieNode(ch));
                 current = current.getChild(ch);
            }
            current.count++;
        }
        current.isEnd = true;
    }
    /* This function is used to search a word in trie*/
    public boolean search(String word)
    {
        TrieNode current = root;  
        for (char ch : word.toCharArray() )
        {
            if (current.getChild(ch) == null)
                return false;
            else
                current = current.getChild(ch);
        }      
        if (current.isEnd == true) 
            return true;
        return false;
    }
    /* This function is used to remove function from trie*/
    public void remove(String word)
    {
        if (search(word) == false)
        {
            System.out.println(word +" does not present in trie\n");
            return;
        }             
        TrieNode current = root;
        for (char ch : word.toCharArray()) 
        { 
            TrieNode child = current.getChild(ch);
            if (child.count == 1) 
            {
                current.childList.remove(child);
                return;
            } 
            else 
            {
                child.count--;
                current = child;
            }
        }
        current.isEnd = false;
    }
  
    public static void printAllWordsInTrie(TrieNode root,String s)
    {
      TrieNode current = root;
      if(root.childList==null || root.childList.size()==0)
       return;
      Iterator<TrieNode> iter=current.childList.iterator();
     while(iter.hasNext())
     {
      TrieNode node= iter.next();
      s+=node.data;
      printAllWordsInTrie(node,s);
      if(node.isEnd==true)
      { 
       System.out.print(" "+s);
       s=s.substring(0,s.length()-1);
      }
      else
      {
       s=s.substring(0,s.length()-1);
      }
     }
      
    }
    public static void main(String[] args)
    {            
        TrieDataStructure t = new TrieDataStructure();       
        t.insert("dear");
        t.insert("deal");
        t.insert("do");
        t.insert("he");
        t.insert("hen");
        t.insert("heat");
        
        System.out.println("hen present in trie : "+t.search("hen"));
        System.out.println("hear present in trie : "+t.search("hear"));
        System.out.println("deal present in trie : "+t.search("deal"));
        System.out.println("========================");
        System.out.println("Printing all word present in trie : ");
        printAllWordsInTrie(t.root,"");              
    }
}    
When you run above program, you will get below output
hen present in trie : true
hear present in trie : false
deal present in trie : true
========================
Printing all word present in trie : 
 dear deal do hen heat he

Sometimes, we may need to convert String to bytes Array but how to convert bytes array to String back.

toString method does not work correctly here as it just print bytes in String format.

You can use String's constructor to get String back.

Example:

package org.arpit.java2blog;

public class StringContentEqualsExample {
 public static void main(String[] args) {
  String str1 = "java2blog";
  byte[] bytes=str1.getBytes();
 
  System.out.println(bytes.toString());
  
  String origStr1=new String(bytes);
  System.out.println(origStr1);
  
 }
}

When you run above program, you will get below output:
[B@e1641c0
java2blog

Exceptions

I have started writing about the Java Certifications and how to prepare for the various topics related to OCAJP exams in my blog. In my previous post, I have published few sample mock questions for StringBuilder class.
In this post I am going to explain about the another OCAJP exam objective “Differentiate among checked exceptions, unchecked exceptions, and Errors”. This is exam objective 8.1 in both OCAJP 8 and OCAJP 7 exams. There is no difference between both the exams with respect to this objective.

OCA exam would test your knowledge on the exceptions that are available in Java SE 6 version. There is no revision of latest versions in the OCA exam. But, OCP exam covers the latest exception handling mechanism from the versions Java SE 7 & 8.
In this Post we would explain about exception hierarchy, difference between checked, unchecked exceptions and errors.
If you are looking for mock exams to practice OCAJP exam, you can try these free practice questions for OCAJP 8 exam.

What is Exception ?

  •  Java doc says “ An exception is an event, which occurs during the execution of a program, that disrupts the normal flow of the program's instructions.” 
  • The term “exception” means “exceptional condition” and is an occurrence that changes the normal program flow. 
  • A bunch of things can lead to exceptions, including hardware failures, resource exhaustion, and good old bugs. 
  • When an exception event occurs in Java , an exception is said to be “thrown”. 
  • The code that is responsible for doing something about the exception is called an “exception handler” and it “catches” the thrown exception. 
  • Every Exception will be thrown at runtime. 

Exceptions hierarchy


 Throwable

  • Throwable class is present in java.lang package. 
  • Throwable is the super class for all exception classes in Java. 
  • It has two direct sub classes such as Exception, Error(Of Course every exception class is directly or indirectly sub class of Throwable ). 
  • It has some methods which are to print exceptions details as per application requirement. 

Exception

  • Exception is the class present in java.lang package. 
  • This class doesn’t have it’s own methods , it inherited methods from Throwable class. 
  • All sub classes of this class are considered as checked Exceptions(except RuntimeException and it’s sub classes). 

RuntimeException

  •  RuntimeException is the class present in java.lang package. 
  •  It is sub class of Exception class. 
  •  This class is also doesn’t have it’s own methods , it inherited methods from Throwable class.  Because Throwable is indirectly super class of RuntimeException. 
  •  All sub classes of this class are considered as unchecked Exceptions. 

Error

  • Error is the class present in java.lang package. 
  • It is sub class of Throwable class. 
  • This class is also doesn’t have it’s own methods , it inherited methods from Throwable class. Because Throwable is indirectly super class of RuntimeException. 
  • All sub classes of this class are considered as unchecked errors. 

Checked Exceptions

  • If a class is a subclass of Exception class directly or indirectly and should not be subclass of RuntimeException class, it is a checked exception. 
  • Why the name checked, because these exceptions can be detected at compile time. 
  • Of course checked exceptions thrown at runtime,It is mandatory that Java code requires to declare or handle them at compile time otherwise the code doesn’t compile .
  • These are caused by unexpected conditions outside control of code (e.g. database down, file I/O error, wrong input, etc). 
  • These are thrown programmatically. 
  • These are recoverable errors.
  • For Example IOException is a checked exception, it occurs when you are try to open a file which is not existed in that location. 
  • You can recover from this exception by putting the file in the same location. 

OCAJP checked exceptions

FileNotFoundException thrown programmatically when code tries to reference a file that does not exist
IOException Thrown programmatically when there’s a problem reading or writing a file.
For the OCA exam, you only need to know that these are checked exceptions. Also keep in mind that FileNotFoundException is a subclass of IOException, although the exam will remind you of that fact if it comes up. You’ll see these two exceptions in more detail on the OCP exam.

Unchecked Exceptions

  • If a class is a subclass of RuntimeException class directly or indirectly, it is a unchecked exception.
  • Why the name unchecked , because these are not detected at compile time. So, It is not mandatory that Java code requires to declare or handle them. 
  • These are also thrown at run time. 
  • These are thrown by JVM. 
  • These are also recoverable errors.
  • For Example : when you call method on reference variable which is null causes NullPointerException. 
  • You can recover from this exception , by checking reference is null or not before method on that reference. 

OCAJP unchecked Exceptions

ArithmeticException
 • It is Thrown by the JVM when code attempts to divide by zero.
Example :
 int b= 9;
 int c = b/0;
Running this code results in the following output: Exception in thread "main" java.lang.ArithmeticException: / by zero

ArrayIndexOutOfBoundsException

  • It is thrown by the JVM when code uses an illegal index to access an array. 
  • Example :
        int[] a = new int[2]; 
        System.out.println(a[-1])
    
  • This is a problem because there’s no such thing as a negative array index. Running this code givess the following output: Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1 

 ClassCastException

  • It is thrown by the JVM when an attempt is made to cast an exception to a subclass of which it is not an instance 
  • Example :
     
               String type = "OCAJP8";
               Object obj = type;
               Integer number = (Integer) obj;
    
  • The compiler sees a cast from Object to Integer. This could be okay. The compiler doesn’t realize there’s a String in that Object. When the code runs, it gives the following output: Exception in thread "main" java.lang.ClassCastException: java.lang.String cannot be cast to java.lang.Integer 

IllegalArgumentException

  • It is thrown by the programmer to indicate that a method has been passed an illegal or inappropriate argument. 
  • Example :
    public static void setCount(int count)
    {
           if (count < 0)
                   throw new IllegalArgumentException("cont must not be negative");
           this.count = count;
     }
  • The program throws an exception when it’s not happy with the parameter values. The output looks like this: Exception in thread "main" java.lang.IllegalArgumentException: count must not be negative 

 NullPointerException

  • It is thrown by the JVM when there is a null reference where an object is required. 
  • Example :
  •  
          String name;
          public void printLength() throws NullPointerException 
          {
                 System.out.println(name.length());
          }
    
  • Running this code results in this output: Exception in thread "main" java.lang.NullPointerException 

NumberFormatException

It is thrown by the programmer when an attempt is made to convert a string to a numeric type but the string doesn’t have an appropriate format.
Example :
 
           Integer.parseInt("OCA");
The output looks like this: Exception in thread "main" java.lang.NumberFormatException: For input string:"OCA"

Errors

  • If a class is a subclass of Error class directly or indirectly,it is an error.
  • For Errors, It is not mandatory that Java code requires to declare or handle them. If you catch there won’t be compile time error. But you shouldn’t catch it.
  • These are thrown by JVM.
  • These are unrecoverable errors.
  • For Example when you try to create infinite objects you will get OutOfMemoryError .
  • You can’t recover from these errors.

 ExceptionInInitializerError

  • It is thrown by the JVM when a static initializer throws an exception and doesn’t handle it. 
  • Example :
     
           static {
           int[] c = new int[3];
           int num = c[-1];
           }
    
           public static void main(String[] args) { }
    
  •  This code gives information about two exceptions: Exception in thread "main" java.lang.ExceptionInInitializerError Caused by: java.lang.ArrayIndexOutOfBoundsException: -1
  • We get the ExceptionInInitializerError because the error happened in a static initializer.
  • That information alone wouldn’t be particularly useful in fixing the problem. Therefore, Java also tells us the original cause of the problem: the ArrayIndexOutOfBoundsException that
  • We need to fix the ExceptionInInitializerError is an error because Java failed to load the whole class. This failure prevents Java from continuing.So the errors are unrecoverable. 

StackOverflowError

  • It is thrown by the JVM when a method calls itself too many times (this is called infi nite recursion because the method typically calls itself without end). 
  • Example :
     
         public static void call(int n) 
         {
                  call(8);
         }
    
  • The output contains this line: Exception in thread "main" java.lang.StackOverflowError
  • Since the method calls itself, it will never end. Eventually, Java runs out of room on the stack and throws the error. This is called infinite recursion. 

NoClassDefFoundError 

 It is thrown by the JVM when a class that the code uses is available at compile time but not runtime. This error won’t show up in code on the exam—you just need to know that it is an error.

Difference between checked exception, unchecked exception and errors 

Parameter
Checked Exception
Unchecked Exception
Error
How to recognise
sub class of Exception class
sub class of RuntimeException class
sub class of Error class
Good to 
catch
Yes
Yes
No
Is Program required to handle or declared
Yes
No
No
Thrown by
Programatically
JVM
JVM
Recoverable
Yes

Yes
No
Example
IOException
FileNotFoundException etc

NullPointerException
ClassCastException
etc
StackOverFlowError
OutOfMemoryError
etc
 For the OCAJP exam preparation, for this exam objective you have to concentrate on the below areas.

Conclusion 

• What are common exception classes?
• How they occur?
• When they occur?
• How will it be thrown?
Also practice lot of sample mock questions to get familiar with the concepts. That is very important for you to get the confidence for attending the real exam.
Good luck for your exam preparation!!

References 

If you are preparing for the OCAJP certification exam, the following references would be much useful.
OCAJP 8 Exam Curriculum
OCAJP Forums
How to prepare for OCAJP Exam?
What are the good books available for OCAJP 8 exam?

Problem:

From Wikipedia :
In computer science, the Largest sum contiguous subarray is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.

Solution :

There are multiple solution to solve this problem:

Solution 1:

Use two loops and try each combination of array elements to find maximum sum.
Time complexity : O(N^2)

Solution 2:

Kadane 's algoritm
I have discussed Kadane 's algorithm in previous post. You can refer it.
Time complexity : O(N)

Solution 3:

Dynamic Programming:
You can use dynamic programming to solve this problem.
Lets say array be arr[] and maximum sum upto index i is maxSum(i)
Logic which can be used for dynamic programming:
maxSum(i) = Max of (maxSum(i-1) + a[i] , a[i])
So it can be define as
Max sum at index i is maximum of (max sum upto i-1 + current element , current element)
Java code  :
public int dynamicProgramForMaxSubArray(int[] arr) {
  int[] result = new int[arr.length];
  result[0]=arr[0];
  for (int i = 1; i < arr.length; i++) {
   result[i]=Math.max(result[i-1]+arr[i], arr[i]);
  }
   int maxSumArray = result[0];
         for (int j = 1; j <result.length ; j++) {
             if(maxSumArray<result[j])
              maxSumArray = result[j];
         }

  return maxSumArray;
 }
Time complexity : O(N)

Java Program to find largest sum contiguous subarray:

package org.arpit.java2blog;
public class MaximumSubArrayMain {
 
 /* Dynamic programming algorithm to find largest sum continuous subarray
  */
 public int dynamicProgramForMaxSubArray(int[] arr) {
  int[] result = new int[arr.length];
  result[0]=arr[0];
  for (int i = 1; i < arr.length; i++) {
   result[i]=Math.max(result[i-1]+arr[i], arr[i]);
  }
   int maxSumArray = result[0];
         for (int j = 1; j <result.length ; j++) {
             if(maxSumArray<result[j])
              maxSumArray = result[j];
         }

  return maxSumArray;
 }
 public static void main(String args[]) {
  int arr[] = { 1, 8, -3, -7, 2, 7, -1, -9 };
  MaximumSubArrayMain maxSum = new MaximumSubArrayMain();
 System.out.println("Largest sum continuous subarray is " + maxSum.dynamicProgramForMaxSubArray(arr));
 }
}
When you run above program, you will get below output:
Largest sum continuous subarray is  9

Kadane algorithm is a famous algorithm to solve maximum subarray problem.

Maximum subArray problem: 

From Wikipedia :
In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.

Kadane 's Algorithm can be used to solve maximum sub array problem

Kadane's algorithm:

  • Initialize maxSoFar= 0 and maxEndingHere = 0 
  • Iterate over each element of the array 
    • maxEndingHere = maxEndingHere + a[i] 
    • if(maxEndingHere < 0) 
      •  maxEndingHere = 0 
    • if(maxSoFar < maxEndingHere) 
      •  maxSoFar = maxEndingHere 
    • return maxSoFar
Java Code:
// Kadane's Algorithm
public int kandaneForMaxSubArray(int[] arr) {
  int maxEndHere = 0;
  int maxSoFar = 0;
  for (int i = 0; i < arr.length; i++) {
   maxEndHere += arr[i];
   if (maxEndHere < 0) {
    maxEndHere = 0;
   }
   if (maxSoFar < maxEndHere) {
    maxSoFar = maxEndHere;
   }
  }
  return maxSoFar;
 }
Above algorithm won't work if all elements of array are negative. We will make small changes to algorithm to make it work for negative numbers for too.

Modified Kadane's algorithm:

  • Initialize maxSoFar= arr[0] and maxEndingHere = arr[0] 
  • Iterate over each element of the array 
    • maxEndingHere =Max of (arr[i], maxEndHere+arr[i])
    • if(maxSoFar < maxEndingHere) 
      •  maxSoFar = maxEndingHere 
    • return maxSoFar
Java code:
/* Modified Kadane's algorithm
 * If you make small modification to above algorithm
 * It will work for negative numbers too
*/
 public int kandaneForMaxSubArrayForNegativ(int[] arr) {
  int maxEndHere = arr[0];
  int maxSoFar = arr[0];
  for(int i=1;i<arr.length;i++){
   maxEndHere = Math.max(arr[i], maxEndHere+arr[i]);
   maxSoFar = Math.max(maxSoFar,maxEndHere);
  }
  return maxSoFar;
 }

Kadane Algorithm in java

package org.arpit.java2blog;
public class MaximumSubArrayMain {
 
 /* Kadane algorithm
  * It won't work when all elements of array are negative
  */
 public int kandaneForMaxSubArray(int[] arr) {
  int maxEndHere = 0;
  int maxSoFar = 0;
  for (int i = 0; i < arr.length; i++) {
   maxEndHere += arr[i];
   if (maxEndHere < 0) {
    maxEndHere = 0;
   }
   if (maxSoFar < maxEndHere) {
    maxSoFar = maxEndHere;
   }
  }
  return maxSoFar;
 }

/* Modified Kadane's algorithm
 * If you make small modification to above algorithm
 * It will work for negative numbers too
*/
 public int kandaneForMaxSubArrayForNegativ(int[] arr) {
  int maxEndHere = arr[0];
  int maxSoFar = arr[0];
  for(int i=1;i<arr.length;i++){
   maxEndHere = Math.max(arr[i], maxEndHere+arr[i]);
   maxSoFar = Math.max(maxSoFar,maxEndHere);
  }
  return maxSoFar;
 }

 public static void main(String args[]) {
  int arr[] = { 1, 8, -3, -7, 2, 7, -1, 9 };
  MaximumSubArrayMain maxSum = new MaximumSubArrayMain();
  System.out.println("Maximum subarray is  " + maxSum.kandaneForMaxSubArray(arr));
  int arrNeg[] = { -10, -8, -3, -7, -2, -7, -3, -9 };
  System.out.println("Maximum Subarray when all elements are negative : " + maxSum.kandaneForMaxSubArrayForNegativ(arrNeg));
 }
}
When you run above program, you will get below output:
Maximum subarray is  17
Maximum Subarray when all elements are negative : -2

Selection sort is an in place comparison sorting algorithm. It is very simple to implement but it does not go well with large number of inputs.

Selection sort algorithm :

  • Find the minimum element in the list.
  • Swap minimum element with current element.
  • Repeat the whole process until array is fully sorted.
Below visualization will make it more clear

Java program to implement Selection sort:

package org.arpit.java2blog;

import java.util.Arrays;

public class SelectionSortMain {
 
    public static int[] selectionSort(int[] arr){
         
        for (int i = 0; i < arr.length - 1; i++)
        {
            int index = i;
            for (int j = i + 1; j < arr.length; j++)
                if (arr[j] < arr[index]) 
                    index = j;
      
            int smallerNumber = arr[index];  
            arr[index] = arr[i];
            arr[i] = smallerNumber;
        }
        return arr;
    }
     
    public static void main(String a[]){
         
        int[] arr = {40,10,-30,45,39,32};
        System.out.println("Before Sorting : ");
        System.out.println(Arrays.toString(arr));
        arr = selectionSort(arr);
        System.out.println("===================");
        System.out.println("After Sorting : ");
        System.out.println(Arrays.toString(arr));
    }
}
When you run above program, you will get below output:
Before Sorting : 
[40, 10, -30, 45, 39, 32]
===================
After Sorting : 
[-30, 10, 32, 39, 40, 45]

Time complexity: 

Best case : O(N^2)
Average case : O(N^2)
Worst case : O(N^2) 

Shell sort is in place comparison based sorting algorithm. It is generalization of insertion sort. It was invented by Donald shell.
It allows to sort elements which are far apart. In case of insertion sort, comparison happens between only adjacent elements but in shell sort, it avoid comparing adjacent elements until last steps. Last step of shell sort is ultimately insertion sort.
In short, it improves insertion sort by comparison and exchange elements that are far away.
Shell sort uses a sequence that can be referred as increment sequence. Shell sort makes multiple passes over array and sort number of equally sized array using insertion sort.

Java program to implement shell sort:

package org.arpit.java2blog;

import java.util.Arrays;

public class ShellSortMain {
 public static void main(String[] args) {
  int[] array = { 22, 53, 33, 12, 75, 65, 887, 125, 37, 977 };
  System.out.println("Before Sorting : ");
  System.out.println(Arrays.toString(array));
  System.out.println("===================");
  System.out.println("After Sorting : ");
  array = shellsort(array);
  System.out.println(Arrays.toString(array));
 }

 private static int[] shellsort(int[] array) {

  // first part uses the Knuth's interval sequence
  int h = 1;
  while (h <= array.length / 3) {
   h = 3 * h + 1; // h is equal to highest sequence of h<=length/3
       // (1,4,13,40...)
  }

  // next part
  while (h > 0) { // for array of length 10, h=4

   // This step is similar to insertion sort below
   for (int i = 0; i < array.length; i++) {

    int temp = array[i];
    int j;

    for (j = i; j > h - 1 && array[j - h] >= temp; j = j - h) {
     array[j] = array[j - h];
    }
    array[j] = temp;
   }
   h = (h - 1) / 3;
  }
  return array;
 }

}
When you run above program, you will get below output:
Before Sorting : 
[22, 53, 33, 12, 75, 65, 887, 125, 37, 977]
===================
After Sorting : 
[12, 22, 33, 37, 53, 65, 75, 125, 887, 977]
Time complexity:
Best case: O(n)
Average case: Depends on gaps
Worst case : o(nlog2n)

Quicksort or partition-exchange sort, is a sorting algorithm, which is using divide and conquer algorithm.
In quick sort, we first choose a pivot and divide into two sublists,one will contain elements lower than pivot and other will have elements greater than pivot.

Quick sort algorithm:

Lets say array is arr[]
  • Choose a pivot, it is generally mid element of the list.
  • Initialise two index variable , left=0 and right=arr.length-1
  • Increment left variable until you get element higher than pivot. 
  • Decrement right variable until you get element lesser than pivot
  • swap arr[left] and arr[right] 
  • Recursively sort sublists(sublist with less than pivot, sublist greater than pivot) using above algorithm.
  • In the end , you will get sorted array.

Java program to implement quick sort:

package org.arpit.java2blog;

import java.util.Arrays;

public class QuickSortMain {
     
    private static int array[];

    public static void sort(int[] arr) {
         
        if (arr == null || arr.length == 0) {
            return;
        }
        array = arr;
        quickSort(0, array.length-1);
    }
 
    private static void  quickSort(int left, int right) {
         
        int i = left;
        int j = right;
        // find pivot number, we will take it as mid
        int pivot = array[left+(right-left)/2];
    
        while (i <= j) {
            /**
             * In each iteration, we will increment left until we find element greater than pivot
             * We will decrement right until we find element less than pivot
             */
            while (array[i] < pivot) {
                i++;
            }
            while (array[j] > pivot) {
                j--;
            }
            if (i <= j) {
             exchange(i, j);
                //move index to next position on both sides
                i++;
                j--;
            }
        }
        // call quickSort() method recursively
        if (left < j)
            quickSort(left, j);
        if (i < right)
            quickSort(i, right);
    }
 
    private static void exchange(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
     
    public static void main(String a[]){
        int[] input = {33,21,45,64,55,34,11,8,3,5,1};
        System.out.println("Before Sorting : ");
        System.out.println(Arrays.toString(input));
        sort(input);
        System.out.println("==================");
        System.out.println("After Sorting : ");
        System.out.println(Arrays.toString(array));
        
    }
}
Before Sorting : 
[33, 21, 45, 64, 55, 34, 11, 8, 3, 5, 1]
==================
After Sorting : 
[1, 3, 5, 8, 11, 21, 33, 34, 45, 55, 64]
Time complexity : 
Best Case : O(n log n)
Average Case : O(n log n)
Worst Case : O(n^2)

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
In this post , we will see how to implement Queue using Linked List in java.
Queue is abstract data type which demonstrates First in first out (FIFO) behaviour. We will implement same behaviour using Array.
Although java provides implementation for  all abstract data types such as Stack , Queue and LinkedList but it is always good idea to understand basic data structures and implement them yourself.
Please note that LinkedList implementation of Queue is dynamic in nature.
There are two most important operations of Queue:
enqueue : It is operation when we insert element into the queue.
dequeue : It is operation when we remove element from the queue. Read more at

Java Program to implement Queue using Linked List:

package org.arpit.java2blog;
public class QueueUsingLinkedListMain
{
  private Node front, rear; 
  private int currentSize; // number of items
 
  //class to define linked node
  private class Node
  { 
    int data;
    Node next;
  }
 
  //Zero argument constructor
  public QueueUsingLinkedListMain()
  {
    front = null;
 rear = null;
 currentSize = 0;
  }
 
  public boolean isEmpty()
  {
    return (currentSize == 0);
  }
 
  //Remove item from the beginning of the list.
  public int dequeue()
  {
    int data = front.data;
    front = front.next;
    if (isEmpty()) 
    {
      rear = null;
    }
    currentSize--;
    System.out.println(data+ " removed from the queue");
    return data;
  }
 
  //Add data to the end of the list.
  public void enqueue(int data)
  {
    Node oldRear = rear;
    rear = new Node();
    rear.data = data;
    rear.next = null;
    if (isEmpty()) 
    {
      front = rear;
    }
    else 
    {
      oldRear.next = rear;
    }
    currentSize++;
    System.out.println(data+ " added to the queue");
  }
  public static void main(String a[]){
  
   QueueUsingLinkedListMain queue = new QueueUsingLinkedListMain();
  queue.enqueue(6);
  queue.dequeue();
  queue.enqueue(3);
  queue.enqueue(99);
  queue.enqueue(56);
  queue.dequeue();
  queue.enqueue(43);
  queue.dequeue();
  queue.enqueue(89);
  queue.enqueue(77);
  queue.dequeue();
  queue.enqueue(32);
  queue.enqueue(232);
 }
}
When you run above program, you will get below output:
6 added to the queue
6 removed from the queue
3 added to the queue
99 added to the queue
56 added to the queue
3 removed from the queue
43 added to the queue
99 removed from the queue
89 added to the queue
77 added to the queue
56 removed from the queue
32 added to the queue
232 added to the queue

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
In this post , we will see how to implement Queue using Array in java.
Queue is abstract data type which demonstrates First in first out (FIFO) behavior. We will implement same behavior using Array.
Although java provides implementation for  all abstract data types such as Stack , Queue and LinkedList but it is always good idea to understand basic data structures and implement them yourself.
Please note that Array implementation of Queue is not dynamic in nature.
There are two most important operations of Queue:
enQueue : It is operation when we insert element into the queue.
deQueue : It is operation when we remove element from the queue. Read more at

Java Program to implement Queue using Array:

package org.arpit.java2blog;

public class QueueUsingArrayMain {
 
 private int capacity;
 int queueArr[];
 int front;
 int rear ;
 int currentSize = 0;
 
public QueueUsingArrayMain(int sizeOfQueue){
  this.capacity = sizeOfQueue;
  front = 0;
  rear = -1;
  queueArr = new int[this.capacity];
 }

 /**
  * this method is used to add element in the queue
  * @param data
  */
 public void enqueue(int data) {
  if (isFull()) {
   System.out.println("Queue is full!! Can not add more elements");
  } else {
   rear++;
   if(rear == capacity-1){
    rear = 0;
   }
   queueArr[rear] = data;
   currentSize++;
   System.out.println(data+ " added to the queue");
  }
 }

 /**
  * This method removes an element from the front of the queue
  */
 public void dequeue() {
  if (isEmpty()) {
   System.out.println("Queue is empty!! Can not dequeue element");
  } else {
   front++;
   if(front == capacity-1){
    System.out.println(queueArr[front-1]+" removed from the queue");
    front = 0;
   } else {
    System.out.println(queueArr[front-1]+" removed from the queue");
   }
   currentSize--;
  }
 }

 /**
  * This method is use to check if element is full or not
  * @return boolean
  */
 public boolean isFull(){
  if (currentSize == capacity){
   return true;
  }
  return false;
 }
 
 /**
  * This method is use to check if element is empty or not
  * @return
  */
 public boolean isEmpty(){
 
  if (currentSize == 0){
   return true;
  }
  return false;
 }
 
 public static void main(String a[]){
  
  QueueUsingArrayMain queue = new QueueUsingArrayMain(5);
  queue.enqueue(6);
  queue.dequeue();
  queue.enqueue(3);
  queue.enqueue(99);
  queue.enqueue(56);
  queue.dequeue();
  queue.enqueue(43);
  queue.dequeue();
  queue.enqueue(89);
  queue.enqueue(77);
  queue.dequeue();
  queue.enqueue(32);
  queue.enqueue(232);
 }
}
When you run above program, you will get below output:
6 added to the queue
6 removed from the queue
3 added to the queue
99 added to the queue
56 added to the queue
3 removed from the queue
43 added to the queue
99 removed from the queue
89 added to the queue
77 added to the queue
56 removed from the queue
32 added to the queue
232 added to the queue

Counting sort is special sorting technique used to sort elements between specific range. Lets say elements belong to range 1 to K , then Counting sort can be used to sort elements in O(N) times.
Basic idea of counting sort to find number of elements less than X, so X can be put to its correct position.

Steps for Counting Sort:

  • Take an array to store count of each elements. Lets say array elements contain 1 to K then initialize count array with K.
  • Now add elements of count array, so each elements store summation of its previous elements.
  • Modified count array stores position of elements in actual sorted array.
  • Iterate over array and put element in correct sequence based on modified count array and reduce the count by 1.

Java program for counting sort:

package org.arpit.java2blog;

import java.util.Arrays;

public class CountingSortMain {

 public static void main(String[] args) {
  System.out.println("Before Sorting : ");
  int arr[]={1,4,7,3,4,5,6,3,4,8,6,4,4};
  System.out.println(Arrays.toString(arr));
  arr=countingSort(arr);
  System.out.println("=======================");
  System.out.println("After Sorting : ");
  System.out.println(Arrays.toString(arr));
 }

    static int[] countingSort(int arr[])
    {
        int n = arr.length;
 
        // The result will store sorted array
        int result[] = new int[n];
 
       // Initialize count array with 9 as array contains elements from range 1 to 8.
        int count[] = new int[9];
        for (int i=0; i<9; ++i)
            count[i] = 0;
 
        // store count of each element in count array
        for (int i=0; i<n; ++i)
            ++count[arr[i]];
 
        // Change count[i] so that count[i] now contains actual
        // position of this element in output array
        for (int i=1; i<=8; ++i)
            count[i] += count[i-1];
 
        for (int i = 0; i<n; ++i)
        {
         result[count[arr[i]]-1] = arr[i];
            --count[arr[i]];
        }

        return result;
    }
   
}
When you run above program, you will get below output:
Before Sorting : 
[1, 4, 7, 3, 4, 5, 6, 3, 4, 8, 6, 4, 4]
=======================
After Sorting : 
[1, 3, 3, 4, 4, 4, 4, 4, 5, 6, 6, 7, 8]
Time Complexity= O(N)
I would suggest to try to debug the program to understand it better.

In this post, we will see how to implement heap sort in java.
I will divide heap sort in multiple parts to make it more understandable.
  • What is heap?
  • Understanding complete binary tree
  • Binary heaps
  • Types of heaps
  • Heapifying an element
  • Steps for heap Sort

What is heap?

A heap is a tree with some special properties, so value of node should be greater than or equal to(less than or equal to in case of min heap) children of the node and tree should be complete binary tree.

Binary heaps

Binary heaps are those heaps which can have up to 2 children. We will use binary heaps in our next few sections.

Understanding complete binary tree:

Complete binary tree is a binary tree whose leaves are at h or h-1 level where h is height of the tree.
Index of left child= 2*(index of its parent)+1
Index of right child= 2*(index of its parent)+2
Complete Binary tree

Types of heaps

There are two types of heap.
  • Max heap
  • Min heap
Max heap : It is binary heap where value of node is greater than left and right child of the node.
Min heap : It is binary heap where value of node is lesser than left and right child of the node.

Heapifying an element:

Once we create a heap , it may not satisfy heap property. In order to make it heap again, we need to adjust locations of the heap and this process is known as heapifying the elements.
In order to create a max heap, we will compare current element with its children and find the maximum, if current element is not maximum then exchange it with maximum of left or right child.
Heapifying elements


Java code for heapifying element at location i :
     public static void heapify(int[] arr, int i,int size) { 
      int left = 2*i+1;
      int right = 2*i+2;
      int max;
      if(left <= size && arr[left] > arr[i]){
       max=left;
      } else {
       max=i;
      }
 
      if(right <= size && arr[right] > arr[max]) {
       max=right;
      }
      // If max is not current node, exchange it with max of left and right child
      if(max!=i) {
         exchange(arr,i, max);
         heapify(arr, max,size);
      }
   }

Steps for heap sort:

  • Represent array as complete binary tree.
    • Left child will be at 2*i+1 th location
    • Right child will be at 2*i+2 th location.
  • Build a heap.
    • All the leaf nodes already satisfy heap property, so we don't need to heapify them.
    • Last leaf node will be present at (n-1)th location, so parent of it will be at (n-1)/2 th location, hence (n-1)/2 will be location of last non leaf node.
    • Iterate over non leaf nodes and heapify the elements.
  • After building a heap, max element will be at root of the heap. We will exchange it with (n-1)th location, so largest element will be at proper place and remove it from the heap by reducing size of n.
  • When you exchange largest element, it may disturb max heap property, so you need to again heapify it.
  • Once you do above steps until no elements left in heap, you will get sorted array in the end.

Java code for heap sort:

package org.arpit.java2blog;
import java.util.*;
 
public class HeapSortMain {
 
   public static void buildheap(int []arr) {
      
    /*
     * As last non leaf node will be at (arr.length-1)/2 
     * so we will start from this location for heapifying the elements
     * */
    for(int i=(arr.length-1)/2; i>=0; i--){
     heapify(arr,i,arr.length-1);
      }
   }
 
   public static void heapify(int[] arr, int i,int size) { 
      int left = 2*i+1;
      int right = 2*i+2;
      int max;
      if(left <= size && arr[left] > arr[i]){
       max=left;
      } else {
       max=i;
      }
 
      if(right <= size && arr[right] > arr[max]) {
       max=right;
      }
      // If max is not current node, exchange it with max of left and right child
      if(max!=i) {
         exchange(arr,i, max);
         heapify(arr, max,size);
      }
   }
 
   public static void exchange(int[] arr,int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t; 
   }
 
   public static int[] heapSort(int[] arr) {
     
      buildheap(arr);
      int sizeOfHeap=arr.length-1;
      for(int i=sizeOfHeap; i>0; i--) {
         exchange(arr,0, i);
         sizeOfHeap=sizeOfHeap-1;
         heapify(arr, 0,sizeOfHeap);
      }
      return arr;
   }
 
   public static void main(String[] args) {
      int[] arr={1,10,16,19,3,5};
      System.out.println("Before Heap Sort : ");
      System.out.println(Arrays.toString(arr));
      arr=heapSort(arr);
      System.out.println("=====================");
      System.out.println("After Heap Sort : ");
      System.out.println(Arrays.toString(arr));
   }
}
When you run above program, you will get below output:
Before Heap Sort : 
[1, 10, 16, 19, 3, 5]
=====================
After Heap Sort : 
[1, 3, 5, 10, 16, 19]

In this post , we will see how to convert sorted LinkedList to balanced binary search tree.
There are two ways to do it.

Solution 1:

It is very much similar to convert sorted array to BST. Find middle element of linked list and make it root and do it recursively.
Time complexity : o(nlogn).

Solution 2:

This solution will follow bottom up approach rather than top down.
  • We need to find length of linked list 
  • We will first create left subtree recursively using n/2 nodes.
  • We will create root node and connect left subtree to the root node.
  • Similarly create right subtree recursively and connect root to right subtree.

Java Program to convert sorted LinkedList to balanced BST:

package org.arpit.java2blog;

import org.arpit.java2blog.BinarySearchTreeMain.TreeNode;

public class SortedLinkedListToBSTMain {

 private Node head;
 
 private static class Node {
  private int value;
  private Node next;

  Node(int value) {
   this.value = value;

  }
 }

 public static class TreeNode {
  int data;
  TreeNode left;
  TreeNode right;

  TreeNode(int data) {
   this.data = data;
  }
 }

 public static void preOrder(TreeNode root) {
  if (root == null)
   return;
  System.out.print(root.data + " ");
  preOrder(root.left);
  preOrder(root.right);
 }
 
 public void addToTheLast(Node node) {

  if (head == null) {
   head = node;
  } else {
   Node temp = head;
   while (temp.next != null)
    temp = temp.next;

   temp.next = node;
  }
 }

 public void printList(Node head) {
  Node temp = head;
  while (temp != null) {
   System.out.format("%d ", temp.value);
   temp = temp.next;
  }
  System.out.println();
 }

 // Find length of linked list using iterative method
 public  int lengthOfLinkedList()
 {
  Node temp=head;
  int count = 0;
  while(temp!=null)
  {
   temp=temp.next;
   count++;  
  }
  return count;
 }
 
 public  TreeNode convertSortedLinkedListToBST(int n)
 {
   /* Base Case for recursion*/
        if (n <= 0) 
            return null;
 
        /* Recursively creating the left subtree */
        TreeNode left = convertSortedLinkedListToBST(n / 2);
 
        /* Create a root node*/
        TreeNode root = new TreeNode(head.value);
 
        // Set pointer to left subtree
        root.left = left;
        head = head.next;
        /* Create right subtree with remaining nodes*/
        root.right = convertSortedLinkedListToBST(n - n / 2 - 1);
 
        return root;
 }
 public static void main(String[] args) {
  SortedLinkedListToBSTMain list = new SortedLinkedListToBSTMain();
  // Creating a linked list
  Node head = new Node(10);
  list.addToTheLast(head);
  list.addToTheLast(new Node(20));
  list.addToTheLast(new Node(30));
  list.addToTheLast(new Node(40));
  list.addToTheLast(new Node(50));
  list.addToTheLast(new Node(60));
  list.addToTheLast(new Node(70));
  list.addToTheLast(new Node(80));
  list.addToTheLast(new Node(90));
  System.out.println("Printing linked list :");
  list.printList(head);
  int n =list.lengthOfLinkedList();
  
  TreeNode bst=list.convertSortedLinkedListToBST(n);
  System.out.println("---------------");
  System.out.println("Pre order traversal of binary search tree :");
  preOrder(bst);

 }

}
When you run above program, you will get below output:
Printing linked list :
10 20 30 40 50 60 70 80 90 
---------------
Pre order traversal of binary search tree :
50 30 20 10 40 80 70 60 90 
Time complexity : o(N).

In this post ,  we will see how to convert sorted array to balanced binary search tree.

Algorithm:

You might know that inorder traversal of binary search tree results in sorted array. We will use this property to convert sorted array to balanced binary search tree, so middle element of array or sub array will always be root for that array or subarray.
  • Initialise two variables start and end with 0 and arr.length -1.
  • Find middle element of array using start and end.
  • Make middle element root element of tree.
  • Recursively traverse left subtree, find middle and make it root node of left subtree 
  • Recursively traverse right subtree, find middle and make it root node of right subtree.

Java code to convert sorted array to balanced binary search tree:

package org.arpit.java2blog;

public class BinarySearchTreeMain {
 public static class TreeNode {
  int data;
  TreeNode left;
  TreeNode right;

  TreeNode(int data) {
   this.data = data;
  }
 }

 public static void preOrder(TreeNode root) {
  if (root == null)
   return;
  System.out.print(root.data + " ");
  preOrder(root.left);
  preOrder(root.right);
 }

 public static void main(String[] args) {

  // Creating a binary search tree
  int arr[]={10,20,30,40,50,60,70,80,90};
  TreeNode rootNode = createBinarySearchTreeFromSortedArray(arr,0,arr.length-1);  
  
  System.out.println("Preorder traversal of created binary search tree :");
  preOrder(rootNode);

 }

 public static TreeNode createBinarySearchTreeFromSortedArray(int[] arr,int start,int end) {
    if (start > end) {
             return null;
         }
  
         /* Get the middle element and make it root */
         int mid = (start + end) / 2;
         TreeNode node = new TreeNode(arr[mid]);
  
         /* Recursively construct the left subtree and make it
          left child of root */
         node.left = createBinarySearchTreeFromSortedArray(arr, start, mid - 1);
  
         /* Recursively construct right subtree and make right child of the root */
         node.right = createBinarySearchTreeFromSortedArray(arr, mid + 1, end);
          
         return node;
 }
}
When you run above program, you will get below output:
Preorder traversal of created binary search tree :
50 20 10 30 40 70 60 80 90 

Problem :

Given an array of positive integer and given value X, find Contiguous sub array whose sum is equal to X.
For example:
arr[]={14, 12, 70, 15, 99, 65, 21, 90}; 
X =97.
Sum found between index 1 to 3
Elements are 12, 17 and 15

Solution:

Solution 1: 

Check all sub arrays and if current sum is equal to X, return. This will require two loops and if currentSum is greater than X tben try another sub array.
Java code:
static void findSubArraySumEqualToX(int arr[], int X) {
  int currentSum;
  for (int i = 0; i < arr.length; i++) {
   currentSum = arr[i];
   // try all subarrays starting with 'i'
   for (int j = i + 1; j <= arr.length; j++) {
    if (currentSum == X) {
     int endIndexForContArray = j - 1;
     System.out.println("Sum found between indexes " + i + " and " + endIndexForContArray);
     for (int k = i; k <= endIndexForContArray; k++) {
      System.out.print(arr[k]+" ");
     }
     return;
    }
    if (currentSum > X || j == arr.length)
     break;
    currentSum = currentSum + arr[j];
   }
  }

  System.out.println("No subarray found");
  return;
 }
Time Complexity : O(N^2)

Solution 2: 

Lets say array is arr[] and given sum is X.
  • Iterate over array arr[]. 
  • If currentSum is less than X then add current element to currentSum.
  • If currentSum is greater than X , it means we need to remove starting elements to make currentSum less than X.
  • If CurrentSum is equal to X, we got the continuous sub array, print it.
Java Code:
 public static void findSubArraySumEqualToXOptimized(int arr[], int X) {
  int currentSum = arr[0];
  int start = 0;

  for (int i = 1; i <= arr.length; i++) {
   // If currentSum is more than the sum, start removing starting elements unless you get currentSum is less than X
   while (currentSum > X && start < i - 1) {
    currentSum = currentSum - arr[start];
    start++;
   }

   // If currentSum becomes equal to sum, then print the index
   if (currentSum == X) {
    int endIndexForContArray = i - 1;
    System.out.println("Sum found between indexes " + start + " and " + endIndexForContArray);
    System.out.println("Printing Array values : ");
    for (int j = start; j <= endIndexForContArray; j++) {
     System.out.print(arr[j]+" ");
    }
    return;
   }

   // Add this element to currentSum
   if (i < arr.length)
    currentSum = currentSum + arr[i];
  }
Time Complexity : O(N) 

Java program to find the Contiguous Subarray with Sum to a Given Value in an array :

package org.arpit.java2blog;

public class FindSumSubArrayMain {
 public static void main(String[] args) {

  int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };

     findSubArraySumEqualToX(arr, 33);
     System.out.println("\n======================");
  findSubArraySumEqualToXOptimized(arr, 33);
 }

 static void findSubArraySumEqualToX(int arr[], int X) {
  int currentSum;
  for (int i = 0; i < arr.length; i++) {
   currentSum = arr[i];
   // try all subarrays starting with 'i'
   for (int j = i + 1; j <= arr.length; j++) {
    if (currentSum == X) {
     int endIndexForContArray = j - 1;
     System.out.println("Sum found between indexes " + i + " and " + endIndexForContArray);
     for (int k = i; k <= endIndexForContArray; k++) {
      System.out.print(arr[k]+" ");
     }
     return;
    }
    if (currentSum > X || j == arr.length)
     break;
    currentSum = currentSum + arr[j];
   }
  }

  System.out.println("No subarray found");
  return;
 }

 public static void findSubArraySumEqualToXOptimized(int arr[], int X) {
  int currentSum = arr[0];
  int start = 0;

  for (int i = 1; i <= arr.length; i++) {
   // If currentSum is more than the sum, start removing starting elements unless you get currentSum is less than X
   while (currentSum > X && start < i - 1) {
    currentSum = currentSum - arr[start];
    start++;
   }

   // If currentSum becomes equal to sum, then print the index
   if (currentSum == X) {
    int endIndexForContArray = i - 1;
    System.out.println("Sum found between indexes " + start + " and " + endIndexForContArray);
    System.out.println("Printing Array values : ");
    for (int j = start; j <= endIndexForContArray; j++) {
     System.out.print(arr[j]+" ");
    }
    return;
   }

   // Add this element to currentSum
   if (i < arr.length)
    currentSum = currentSum + arr[i];
  }

 }

}
When you run above program , you will get below output:
Sum found between indexes 6 and 7
10 23 
======================
Sum found between indexes 6 and 7
Printing Array values : 
10 23 

Problem :

Given an array of 0's and 1's in random order , you need to separate 0's and 1's in an array.
For example:
arr[] = {0,1,0,0,1,1,1,0,1}
Array after separating odd and even numbers :
{0,0,0,0,1,1,1,1,1}

Solution :

Solution 1:

  • Count number of 0's in the array. Lets say we get X 0's
  • Once we get the count, put X 0's in the array and put (n-X) 1's in the latter part of array.
Java code:
public static int[] separate0s1sSolution1(int arr[])
 {
  int count=0;
  for (int i = 0; i < arr.length; i++) {
   if(arr[i]==0)
   {
    count++;
   }
  }
  for (int i = 0; i < count; i++) {
   arr[i]=0;
  }
  for (int i = count; i < arr.length; i++) {
   arr[i]=1;
  }
  return arr;
 }
Time Complexity : O(N)

Solution 2:

Algorithm: 
Lets say array is arr[]
  • Initialise two index variable , left=0 and right=arr.length-1
  • Increment left variable until you get 1's.
  • Decrement right variable until you get 0's
  • If left < right, swap arr[left] and arr[right]
  • In the end, you will see that you have 0's on left side and 1's on right side.
Java code:
public static int[] separate0s1sSolution2(int arr[])
 {
  for (int i = 0; i < arr.length; i++) {
   int left=0;
   int right=arr.length-1;
   while(arr[left]==0)
   {
    left++;
   }
   while(arr[right]==1)
   {
    right--;
   }
   
   if(left<right)
   {
    int temp=arr[left];
    arr[left]=arr[right];
    arr[right]=temp;
   }
  }
  return arr;
 }

Java code to separate odd and even numbers in an array :

package org.arpit.java2blog;

public class Separate0s1sMain {

 public static void main(String[] args) {
  int arr[]={0,1,0,0,1,1,1,0,1};
  System.out.println("Original Array: ");
  for (int i = 0; i < arr.length; i++) {
   System.out.print(arr[i]+" ");
  }
  arr=separate0s1sSolution1(arr);
  System.out.println("\n===========================");
  System.out.println("Solution 1");
  System.out.println("\nArray after separating 0's and 1's : ");
  for (int i = 0; i < arr.length; i++) {
   System.out.print(arr[i]+" ");
  }
  System.out.println("\n===========================");
  System.out.println("Solution 2");
  arr=separate0s1sSolution2(arr);
  System.out.println("\nArray after separating 0's and 1's : ");
  for (int i = 0; i < arr.length; i++) {
   System.out.print(arr[i]+" ");
  } 
 }
 
 
 public static int[] separate0s1sSolution1(int arr[])
 {
  int count=0;
  for (int i = 0; i < arr.length; i++) {
   if(arr[i]==0)
   {
    count++;
   }
  }
  for (int i = 0; i < count; i++) {
   arr[i]=0;
  }
  for (int i = count; i < arr.length; i++) {
   arr[i]=1;
  }
  return arr;
 }
 public static int[] separate0s1sSolution2(int arr[])
 {
  for (int i = 0; i < arr.length; i++) {
   int left=0;
   int right=arr.length-1;
   while(arr[left]==0)
   {
    left++;
   }
   while(arr[right]==1)
   {
    right--;
   }
   
   if(left<right)
   {
    int temp=arr[left];
    arr[left]=arr[right];
    arr[right]=temp;
   }
  }
  return arr;
 }

}
when you run above program, you will get below output:
Original Array: 
0 1 0 0 1 1 1 0 1 
===========================
Solution 1

Array after separating 0's and 1's : 
0 0 0 0 1 1 1 1 1 
===========================
Solution 2

Array after separating 0's and 1's : 
0 0 0 0 1 1 1 1 1 

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
In this post, we will see how to find minimum element in sorted and rotated array.

Problem:

You are given an sorted and rotated array as below:
int arr[]={16,19,21,25,3,5,8,10};
If you note that array is sorted and rotated. You need to find minimum element in above array in o(log n) time complexity. You can assume that duplicates are not allowed in the array.

Solution:

You can use variant of binary search algorithm to solve above problem. You can use a property that if you divide array into two sorted sub arrays ({16,19,21,25},{3,5,8,10} ), one will be sorted and other will have minimum element

Algorithm:

  • Compute mid i.e low+high/2.
  • Check if a[mid...high] is sorted
    • Minimum lies in left part, so low=mid+1;
  • Else
    • Minimum lies in right part, so high=mid

Java program to find minimum element in a sorted and rotated array :

Create a class named 
MinimumElementSortedAndRotatedArrayMain.java.
package org.arpit.java2blog;
public class MinimumElementSortedAndRotatedArrayMain {

 public static void main(String[] args) {
  int arr[]={16,19,21,25,3,5,8,10};
  System.out.println("Minimum element in the array : "+findMinimumElementRotatedSortedArray(arr,0,arr.length-1,5));
 }
 public  static  int findMinimumElementRotatedSortedArray(int[] arr,int low,int high,int number)
 {
  int mid;
  while(low<high)
  {
   mid=low + ((high - low) / 2);
   
   if(arr[mid] > arr[high])
   {
    low=mid+1;
   }
   else 
   {
    high=mid;
   }
  }
  return arr[low];
 }
}
When you run above program, you will get below output:
Minimum element in the array : 3

Given array of integers, find Maximum difference between two elements such that larger element appears after the smaller number
For example:
int arr[]={14, 12, 70, 15, 95, 65, 22, 30};
Max Difference =95-12 = 83

Algorithm:

Lets say we have array arr[] of stock prices.
We will track two variable :minElementTillNow and maxDifference.
  • minElementTillNow will be initialise to arr[0].
  • Iterate over  arr[]
  • If current element is greater than minElementTillNow 
    • calculate difference.
    • If difference is greater than maxDifference then update the maxDifference.
  • If current element is lesser than minElementTillNow
    • update minElementTillNow with current element.
  • We will get maxDifference in the end.
public static int calculateMaxDifferenceBetweenTwoElements(int[] arr)
 {
  int minElementTillNow=arr[0];
  int maxDifference=Integer.MIN_VALUE;
  for (int i = 0; i < arr.length; i++) {
   int difference=0;
   if(arr[i] >minElementTillNow)
   {
    difference=arr[i]-minElementTillNow;
    if(difference > maxDifference)
    {
     maxDifference=difference;
    }
   }
   else
   {
    minElementTillNow=arr[i];
   }
  }
  return maxDifference;
 }

Java Program to find maximum difference between two elements :

package org.arpit.java2blog;

public class MaxDifferenceMain {

 public static void main(String[] args) {
  int arr[]={14, 12, 70, 15, 95, 65, 22, 30};
  System.out.println("Maximum difference between two elements : "+calculateMaxDifferenceBetweenTwoElements(arr));

 }
 public static int calculateMaxDifferenceBetweenTwoElements(int[] arr)
 {
  int minElementTillNow=arr[0];
  int maxDifference=Integer.MIN_VALUE;
  for (int i = 0; i < arr.length; i++) {
   int difference=0;
   if(arr[i] >minElementTillNow)
   {
    difference=arr[i]-minElementTillNow;
    if(difference > maxDifference)
    {
     maxDifference=difference;
    }
   }
   else
   {
    minElementTillNow=arr[i];
   }
  }
  return maxDifference;
 }

}
When you run above program, you will get below output:
Maximum difference between two elements : 83

Problem :

Given an array of integers, you need to segregate odd and even numbers in an array.
Please note : Order of elements can be changed.
For example:
arr[] = {12, 17, 70, 15, 22, 65, 21, 90}
Array after separating odd and even numbers :
{12, 90, 70, 22, 15, 65, 21, 17}

Algorithm: 

Lets say array is arr[]
  • Initialise two index variable , left=0 and right=arr.length-1
  • Increment left variable until you get odd number
  • Decrement right variable until you get even number.
  • If left < right, swap arr[left] and arr[right]
  • In the end, you will see that you have even numbers on left side and odd numbers on right side.

Java code to separate odd and even numbers in an array :

package org.arpit.java2blog;

public class SeparateOddEvenMain {

 public static void main(String[] args) {
  
  int arr[]={12, 17, 70, 15, 22, 65, 21, 90};
  System.out.println("Original Array: ");
  for (int i = 0; i < arr.length; i++) {
   System.out.print(arr[i]+" ");
  }
  arr=separateEvenOddNumbers(arr);
  System.out.println("\nArray after separating even and odd numbers : ");
  for (int i = 0; i < arr.length; i++) {
   System.out.print(arr[i]+" ");
  }
 }
 public static int[] separateEvenOddNumbers(int arr[])
 {
  
  for (int i = 0; i < arr.length; i++) {
   int left=0;
   int right=arr.length-1;
   while(arr[left]%2==0)
   {
    left++;
   }
   while(arr[right]%2==1)
   {
    right--;
   }
   
   if(left<right)
   {
    int temp=arr[left];
    arr[left]=arr[right];
    arr[right]=temp;
   }
  }
  return arr;
 }
}
when you run above program, you will get below output:
Original Array: 
12 17 70 15 22 65 21 90 
Array after separating even and odd numbers : 
12 90 70 22 15 65 21 17 

Problem:

We need to print all the leaders present in the array. Element is the leader if it is greater than right side of elements.
For example:
arr[]={14, 12, 70, 15, 99, 65, 21, 90}
Here 99 and 90 are leader elements

Solution:

Solution 1:

Use two loops. Outer loop to iterate over array elements and inner loop to check for right elements of the array. If current element is greater than right elements than it is a leader.
Java code:
public static void findLeadersInAnArrayBruteForce(int arr[])
 {
  System.out.println("Finding leaders in an array using brute force : ");
  for (int i = 0; i < arr.length; i++) {
   boolean isLeader=true;
   for (int j = i+1; j < arr.length; j++) {
    if(arr[i] <= arr[j])
    { 
     isLeader=false;
     break;
    }    
   }
   if(isLeader)
    System.out.print(arr[i]+" ");
  }
 }
Time complexity : o(N^2)

Solution 2:

Lets find more optimized solution
We will use property that rightmost element is always a leader.
  • We will start from rightmost element and track max. 
  • Whenever we get new max, that element is a leader.
Java code:
public static void findLeadersInAnArray(int arr[])
 {
  System.out.println("Finding leaders in an array : ");
  int rightMax=arr[arr.length-1];
  // Rightmost will always be a leader
  System.out.print(rightMax+" ");
  for (int i = arr.length-2; i>=0; i--) {
   if(arr[i] > rightMax)
   {
    rightMax=arr[i];
    System.out.print(" "+rightMax);
   }
  }
 }
Time complexity : o(N)

Java Program to find leaders in the array:

package org.arpit.java2blog;

public class FindLeadersInArrayMain {

 public static void main(String[] args) {
  int arr[]={14, 12, 70, 15, 99, 65, 21, 90};
  findLeadersInAnArrayBruteForce(arr);
  System.out.println("\n==================");
  findLeadersInAnArray(arr);
 }
 
 public static void findLeadersInAnArrayBruteForce(int arr[])
 {
  System.out.println("Finding leaders in an array using brute force : ");
  for (int i = 0; i < arr.length; i++) {
   boolean isLeader=true;
   for (int j = i+1; j < arr.length; j++) {
    if(arr[i] <= arr[j])
    { 
     isLeader=false;
     break;
    }    
   }
   if(isLeader)
    System.out.print(arr[i]+" ");
  }
 }
 
 public static void findLeadersInAnArray(int arr[])
 {
  System.out.println("Finding leaders in an array : ");
  int rightMax=arr[arr.length-1];
  // Rightmost will always be a leader
  System.out.print(rightMax+" ");
  for (int i = arr.length-2; i>=0; i--) {
   if(arr[i] > rightMax)
   {
    rightMax=arr[i];
    System.out.print(" "+rightMax);
   }
  }
 }

}
When you run above program, you will get below output:
Finding leaders in an array using brute force
99 90 
==================
Finding leaders in an array : 
90  99

 

Java tutorial for beginners Copyright © 2012