These are frequently asked java coding interview questions in 2025.

If you want to practice and improve data structure and algorithm programs, this post will be very helpful to you. I will recommend you to try it yourself first and then check the solution.

String

Question 1 : How to reverse a String in java? Can you write a program without using any java inbuilt methods?

Solution: There are many ways to do it, some of them are:

• Using for loop
• Using recursion
• Using StringBuffer

Please refer to the solution at reverse a String in java

Question 2 : Write a java program to check if two Strings are anagram in java?

Solution: Two string are anagrams if they have same characters but in different order. For example: Angel and Angle are anagrams
There are few ways to check if Strings are anagrams. Some of them are:

1. Using String methods
2. Using array.sort

Check solution at check if two Strings are anagram in java.

Question 3 : Write a program to check if String has all unique characters in java?

Solution: Here are some ways to check if String contains all unique characters

• By using HashSet
• Using indexOf and lastIndexOf methods of String
• By Using ascii value of characters.

Please refer to complete solution at check if String has all unique characters.

Question 4 : How to check if one String is rotation of another String in java?

Solution: Let’s say you want to check whether str1 and str2 is rotation of one another or not.

1. Create a new String with str3= str1 + str1
2. Check if str3 contains str2 or not.
3. if str3 contains str2 then str2 is rotation of str1 else it is not

You can find complete solution at check if one String is rotation of another in java.

Question 5 : How to find duplicate characters in String in java?

Solution:  Here is a solution to find duplicate characters in String.

1. Create a HashMap and character of String will be inserted as key and its count as value.
2. If Hashamap already contains char,increase its count by 1, else put char in HashMap.
3. If value of Char is more than 1, that means it is duplicate character in that String.

Please refer to solution at program to find duplicate characters in a String.

Question 6 : Find first non repeated character in String in java?

Solution: There are may ways to find it.
Some of them are:

• Using LinkedHashMap
• Using indexOf and lastIndexOf methods.

Please find complete solution at find first non repeated character in  a String.

Question 7 : Find all substrings of String in java?

Solution: Java program to find all substrings of a String.
For example: If input is "abb"  then output should be "a", "b","b", "ab", "bb", "abb"
We will use String class’s subString method to find all subString.
Please refer to complete solution at find all subStrings of String.

Question 8 : Find length of String without using any inbuilt method in java?

Solution: You can use try catch block for catching StringIndexOutOfBoundException and when this exception aries, you can simply return i(Index at which you will get the exception)
Please refer to complete solution at find length of String without inbuilt methods.

Question 9 : Write a program to print all permutations of String in java?

Solution: Take out first character of String and insert into different places of permutations of remaining String recursively. Please find complete solution at how to find all permutations of String in java.

Array

You may be asked lot of java coding interview questions on Array. You can practice following coding questions on Array to ace coding interview.

Question 10 : Write java Program to Find Smallest and Largest Element in an Array.

You are given an integer array containing 1 to n but one of the number from 1 to n in the array is missing. You need to provide an optimum solution to find the missing number. Number can not be repeated in the arry.
For example:

int[] arr1={7,5,6,1,4,2};
Missing numner : 3
int[] arr2={5,3,1,2};
Missing numner : 4

Solution : Java Program to Find Smallest and Largest Element in an Array

Question 11 : Find missing number in the array.

You are given an integer array containing 1 to n but one of the number from 1 to n in the array is missing. You need to provide optimum solution to find the missing number. Number cannot be repeated in the arry.
For example:

int[] arr1={7,5,6,1,4,2};
Missing numner : 3
int[] arr2={5,3,1,2};
Missing numner : 4

Solution : Find missing number in the array.

Question 12 : Search an element in rotated and sorted array.

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 search an element in above array in o(log n) time complexity.
Solution : Search element in rotated and sorted array

Question 13 : Find minimum element in a sorted and rotated array.

You are given an sorted and rotated array as below:

int arr[]={16,19,21,25,3,5,8,10};
Minimum element in the array : 3

If you note that array is sorted and rotated. You need to i an element in above array in o(log n) time complexity.
Solution : Find minimum element in a sorted and rotated array

Question 14: Find second largest number in an array

You are given an sorted and rotated array as below:
For example:

int[] arr1={7,5,6,1,4,2};
Second largest element in the array : 6

Solution : java program to find second largest number in an array.

Question 15 : Find the number occurring odd number of times in an array

You are given a array of integer. All numbers occur even number of times except one. You need to find the number which occurs odd number of time. You need to solve it with o(n) time complexity and o(1) space complexity.
For example:

int array[] = new int[]{20, 40, 50, 40, 50, 20, 30, 30, 50, 20, 40, 40, 20};
Number which occurs odd number of times is : 50

Solution : java program to find number occurring odd number of times in an array.

Question 16 : Find minimum number of platforms required for railway station

You are given arrival and departure time of trains reaching to a particular station. You need to find minimum number of platforms required to accommodate the trains at any point of time.

For example:

arrival[] = {1:00, 1:40, 1:50, 2:00, 2:15, 4:00}
departure[] = {1:10, 3:00, 2:20, 2:30, 3:15, 6:00}
No. of platforms required in above scenario = 4

Please note that arrival time is in chronological order.

Solution : Find minimum number of platforms required for railway station.

Question 17 : Find a Pair Whose Sum is Closest to zero in Array

Given array of +ve and -ve integers ,we need to find a pair whose sum is closed to Zero in Array.
For example:

array[]={1,3,-5,7,8,20,-40,6};
The pair whose sum is closest to zero :  -5 and 6

Solution : Find a Pair Whose Sum is Closest to zero in Array in java.

Question 18 : Given a sorted array and a number x, find the pair in array whose sum is closest to x

Given a sorted array, we need to find a pair whose sum is closed to number X in Array.
For example:

array[]={-40,-5,1,3,6,7,8,20};
The pair whose sum is closest to 5 :  1 and 3

Solution : Find a Pair Whose Sum is Closest to X in Array in java.

Question 19 : Find all pairs of elements from an array whose sum is equal to given number

Given a  array,we need to find all pairs whose sum is equal to number X.
For example:

array[]={ -40, -5, 1, 3, 6, 7, 8, 20 };
Pair of elements whose sum is equal to 15 :  7, 8 and -5, 20

Solution : Find all pairs of elements from an array whose sum is equal to given number .

Question 20: 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 0 and 1 numbers :
{0,0,0,0,1,1,1,1,1}

Solution : Separate 0s and 1s in array.

Question 21 : Separate odd and even numbers in an array

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}

Solution : Separate 0s and 1s in array.

Question 22 : Given an array containing zeroes, ones and twos only. Write a function to sort the given array in O(n) time complexity.

For example:

Input :
[1, 2, 2, 0, 0, 1, 2, 2, 1]

Output :
[0, 0, 1, 1, 1, 2, 2, 2, 2]

Solution : Sort an array of 0s, 1s and 2s.

Question 23 : Find local minima in array

A local minima is less than its neighbours

For example:

Input :

int [] arr = {10, 5, 3, 6, 13, 16, 7};
Output: 2

int []arr = {11,12,13,14};
Output: 11

int []arr = {10};
Output: 10

int []arr = {8,6};
Output: 6

Question 24 : Sliding window maximum in java

Given an Array of integers and an Integer k, Find the maximum element of from all the contiguous subarrays of size K.

For example:

Input :
Input : int[] arr = {2,6,-1,2,4,1,-6,5}
int k = 3
output : 6,6,4,4,4,5

Solution : Find the local minima in array.

Question 25 : Count number of occurrences (or frequency) of each element in a sorted array

Given a Sorted Array of integers containing duplicates. Find the frequency of every unique element present in the array.
Frequency is defined as the number of occurrence of any element in the array.

For example :

Input :
Input:
int[] arr = {1, 1, 1, 3, 3, 4, 5, 5, 6, 6};
Output:
Frequency of 1 is : 3
Frequency of 3 is : 2
Frequency of 4 is : 1
Frequency of 5 is : 2
Frequency of 6 is : 2

Solution : Count number of occurrences (or frequency) of each element in a sorted array.

Question 26 : Find subarrays with given sum in an array.

Given an Array of non negative Integers and a number. You need to print all the starting and ending indices of Subarrays having their sum equal to the given integer.
For example :

Input :
Input-int[] arr = {2, 3, 6, 4, 9, 0, 11};
int num = 9
Output-
starting index : 1, Ending index : 2
starting index : 5, Ending index : 5
starting index : 5, Ending index : 6

Solution : Find subarrays with given sum in an array.

Question 27 : Find peak element in the array.

Peak Element is the element of the array which is GREATER THAN / EQUAL TO its neighbours, that is, for an element at i th index, the neighbour elements at index i-1 & i+1 must be greater than equal to element at i th position.
Solution : Find peak element in the array.

Question 28 : Find leaders in an array.

We need to print all the leaders present in the array. Element is the leader if it is greater than right side of elements.

arr[]={14, 12, 70, 15, 99, 65, 21, 90}
Here 99 and 90 are leader elements

For example:
Solution : Find leaders in an array.

Question 29 : Count 1’s in sorted Binary Array.

Print number of 1’s in a given sorted Binary Array.
For example :

Input :
int[] arr = {0,0,0,1,1,1,1};
output : 4
int[] arr = {0,0,1};
output : 1

Solution : Count 1’s in sorted Binary Array.

Question 30 : Find first repeating element in an array of integers.

Find the first repeating element in array of integers.
For example :

Input :
Input: array[] = {10, 7, 8, 1, 8, 7, 6}
Output: 7 [7 is the first element actually repeats]

Solution : Find first repeating element in an array of integers.

Question 31 : Check if Array Elements are Consecutive.

Given an array, we need to check if array contains consecutive elements.
For example :

Input: array[] = {5, 3, 4, 1, 2}
Output: true
As array contains consecutive elements from 1 to 5
Input: array[] = {47, 43, 45, 44, 46}
Output: true
As array contains consecutive elements from 43 to 47
Input: array[] = {6, 7, 5, 6}
Output: false
As array does not contain consecutive elements.

Solution : Check if Array Elements are Consecutive.

Question 32 : Permutations of array in java.

Given array of distinct integers, print all permutations of the array.
For example :

array : [10, 20, 30]

Permuations are :

[10, 20, 30]
[10, 30, 20]
[20, 10, 30]
[20, 30, 10]
[30, 10, 20]
[30, 20, 10]

Solution : Permutations of array in java.

Question 33 : Rotate an array by K positions.

For example :

N=6 and k=2
If Arr[] = {1, 2, 3, 4, 5, 6} and k=2
then rotated array will be  {5, 6, 1, 2,  3,  4}

Solution : Rotate an array by K positions.

Question 34 : Stock Buy Sell to Maximize Profit.

Given an array of integers representing stock price on single day, find max profit that can be earned by 1 transaction.
So you need to find pair (buyDay,sellDay) where buyDay < = sellDay and it should maximise the profit.
For example :

int arr[]={14, 12, 70, 15, 99, 65, 21, 90};
Max profit can be gain by buying at 1th day(0 based indexing) and sell at 4th day.
Max profit = 99-12 =87

Solution : Stock Buy Sell to Maximize Profit.

Question 35 : Find maximum difference between two elements such that larger element appears after the smaller number.

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

Solution : Maximum difference between two elements such that larger element appears after the smaller number.

Question 36 : Search in a row wise and column wise sorted matrix.

Given row wise and column wise sorted matrix ,we need to search element with minimum time complexity.
Solution : Search in a row wise and column wise sorted matrix.

Question 37 : Largest sum contiguous subarray.

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 : Largest sum contiguous subarray.

Question 38 : Find the Contiguous Subarray with Sum to a Given Value in an array.

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 : Find the Contiguous Subarray with Sum to a Given Value in an array.

Question 39 : Longest Common Prefix in an array of Strings in java.

Given an array of positive integer and given value X, find Contiguous sub array whose sum is equal to X.
For example :

String[] strArr={"java2blog","javaworld","javabean","javatemp"};
So Longest common prefix in above String array will be “java” as all above string starts with “java”.

Solution : Longest Common Prefix in an array of Strings in java.

Question 40 : Find all subsets of set (power set) in java.

Given a set of distinct integers, arr, return all possible subsets (the power set).
For example :

Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

Solution : Find all subsets of set in java.

Stack

Question 41:  Implement a stack using array.

You need to implement Stack using array. You need to write push and pop methods to demonstrate Stack behavior(Last In First Out).
Solution : Java Program to implement stack using array.

Question 42: Implement a stack using Linked List.

You need to implement Stack using Linked List. You need to write push and pop methods to demonstrate Stack behavior(Last In First Out).
Solution  : Java Program to implement stack using Linked List

Question 43:  Implement a stack using two queues.

You need to use two queues to implement stack behavior.You need to write push and pop methods to demonstrate Stack behavior(Last In First Out).
Solution : Java Program to implement stack using two queues

Question 44 : Sort an stack using another stack

You need to sort an stack using another stack. You can use push and pop operation of stack to do so,
Solution : Sort a stack using another stack.

Queue

Question 45:  Implement Queue using Array in java.

You need to use array to implement queue.
Solution : Implement Queue using Array in java

Question 46:  Implement a stack using two queues .

You need to use Linked list to implement queue.
Solution : Java Program to implement queue using linked list

Linked List

Question 47 : Implement singly linked list in java.

You need to implement singly linked list data structures.You need to write simple program to demonstrate insert , delete operations.

Solution : Java program to implement singly linked list in java.

Question 48: How to reverse linked list in java.

You need to write iterative and recursive solution to reverse linked list.
Solution : Java program to reverse linked list in java.

Question 49: How to find middle element of linked list.

You need to write java program to find middle element of linked list in most optimize way.

Solution : Java program to find middle element of linked list.

Question 50 : How to find nth element from end of linked list .

You need to write java program to find nth  element of linked list in most optimize way.
In question 6, Node 7 is 3rd from last of linked list.
Solution : How to find nth element from end of linked list.

Question 51 : How to detect a loop in linked list. If linked list has loop, find the start node for the loop.

You need to write a java program to detect whether any loop exists in linked list and if loop exists , you need to find start node for the linked list.
Solution : How to detect loop in linked list.
How to find start node of loop in linked list.

Question 52: How to check if linked list is palindrome or not?

A palindrome is a word, phrase, number, or other sequence of symbols or elements that reads the same forward or reversed. For example: 12121 is palindrome as it reads same forward or reversed. madam is also a palindrome . So we need write java programs to check if linked list is palindrome or not.
Solution : Java program to check if linked list is palindrome.

Question 53 :  Find intersection of two linked lists?

Given two singly linked lists, find if two linked lists intersect. If they intersect, find intersection point.

Solution  : Intersection of two linked list

Question 54 :  How to reverse a linked list in pairs?

You need to write a java program to reverse linked list in pairs.

Solution  : Java program to reverse linked list in pair.

Question 55 :  Implement Doubly linked list in java?

You need to write a java program to implement doubly linked list in java.

Solution  : Doubly Linked List in java

Binary Tree

Question 56 : How can you traverse binary tree?

There are three ways to traverse binary tree.

• PreOrder
• InOrder
• PostOrder.

Question 57 : Write an algorithm to do level order traversal of binary tree?

You need to write java program to do level order traversal of binary tree. You can use queue data structure to do level order traversal.

Solution : Level order traversal of binary tree.

Question 58 :  Write an algorithm to do spiral order traversal of binary tree?

You need to write java program to do spiral level order traversal of binary tree

Solution : Sprial order or zigzag traversal of binary tree.

Question 59 : How can you print leaf nodes of binary tree?

You need to write java program to print all leaf nodes of binary tree.

Leaf nodes for above binary tree will be 5 , 30 , 55 ,70
Solution : Print leaf nodes of binary tree.

Question 60 : How to count leaf nodes of binary tree.

You need to write java program to count leaf nodes of binary tree.
Count of Leaf nodes for binary tree used in Question 15 are 5.
Solution : Count leaf nodes of binary tree.

Question 61 : How to print all paths from root to leaf in binary tree.

You need to write a program to print all paths from root to leaf.

Solution : Print all paths from root to leaf in binary tree.

Question 62 : How to find level of node in binary tree

Given a node, you need to find level of a node. For example : Level of node will 3 for node 70 used in Question 14.
Solution: Find level of node in binary tree.

Question 63 : How to find maximum element in binary tree.

You need to write a java program to find maximum element in binary tree.
Solution : Find maximum element in binary tree.

Question 64 : How to find lowest common ancestor(LCA) in binary tree.

You need to write a program to find LCA in binary tree.

Solution: Program to find LCA in binary tree.

Question 65 : How to do boundary traversal of binary tree.

Write a java program to do boundary traversal of binary tree as shown in below image.

Solution : Boundary traversal of binary tree.

Question 66 : How to print vertical sum of binary tree?

You need to find sum of nodes which lies in same column.

Solution : How to print vertical sum of binary tree.

Question 67 : Count subtrees with Sum equal to target in binary tree?

Given a Binary tree and an integer. You need to find the number of subtrees having the sum of all of its nodes equal to given Integer, that is, Target sum.

Solution : Count subtrees with Sum equal to target in binary tree.

Binary Search tree

Question 68 : What is binary search tree?

Binary search tree is a special type of binary tree which have following properties.

• Nodes which are smaller than root will be in left subtree.
• Nodes which are greater than root will be right subtree.
• It should not have duplicate nodes
• Both left and right subtree also should be binary search tree.

Question 69 : Can you write algorithm to insert a node in binary search tree.

Solution : Insert node in binary search tree

Question 70 : Can you write algorithm to delete a node in binary search tree.

Solution : Delete node in binary search tree

Question 71 :  How can you find minimum and maximum elements in binary search tree?

Solution : Leftmost and rightmost nodes of binary search tree are minimum and maximum nodes respectively
Minimum and maximum elements in binary search tree.

Question 72 : How to find lowest common ancestor(LCA) in binary search tree.

You need to write a program to find LCA in binary search tree.

Solution: Program to find LCA in binary search tree.

Question 73 : Find inorder successor in a Binary search Tree

You need to write a program to find inorder successor in a Binary search tree.

Solution: Inorder Successor in a Binary Search Tree

Question 74 : Convert sorted array to balanced BST

Solution: Convert sorted sorted array to balanced BST

Question 75 : Convert sorted Linked List to balanced BST

Solution: Convert sorted Linked List to balanced BST

Question 76 : Check if a binary tree is binary search tree or not in java

Solution: Check if a binary tree is binary search tree or not in java

Sorting

Question 77 : Write an algorithm to implement bubble sort?

Solution : Bubble sort in java

Question 78 : Write an algorithm to implement insertion sort sort?

Solution : Insertion sort in java

Question 79 : Write an algorithm to implement selection sort sort?

Solution : Selection sort in java

Question 80 : Can you write algorithm for merge sort and also do you know complexity of merge sort?

Solution : Merge sort in java

Question 81 : Do you know how to implement Heap sort?

Solution : implement Heap sort in java

Question 82 : Implement quick sort in java?

Solution : implement Quick sort in java

Question 83 : Implement shell sort in java?

Solution : implement Shell sort in java

Question 84 : Implement Counting sort in java?

Solution : implement Counting sort in java

Question 85 : What is binary search? Can you write an algorithm to find an element in sorted array using binary search?

Solution :Binary search algorithm in java

Graph

Question 86 : Write algorithm to do depth first search in a graph.

Solution : Depth first search in java

Question 87 : Write algorithm to do breadth first search in a graph.

Solution : breadth first search in java

Question 88 : Explain Dijkstra algorithm from source to all other vertices.

Solution : Dijkstra’s algorithm in java

Question 89 : Explain Bellman Ford algorithm to find shortest distance

Solution : Bellman ford algorithm in java

Question 90 : Explain Kruskal’s algorithm for finding minimum spanning tree

Solution : Kruskal’s algorithm

Dynamic Programming

Question 91 : Given two String, find longest common substring.

Solution: Longest common substring in java.

Question 92 : Given two Strings A and B. Find the length of the Longest Common Subsequence (LCS) of the given Strings.

Solution: Longest common subsequence in java

Question 93 : Given a matrix, we need to count all paths from top left to bottom right of MxN matrix. You can either move down or right.

Solution: Count all paths in matrix

Question 94 : Edit Distance Problem in java

Given two strings string1 and string2, String1 is to be converted into String2 with the given operations available in the minimum number of steps. Using any one of the given operations contributes to the increment of steps by one.

Allowed Operations are :
(i) Remove : This operation allows the Removal any one character from String.
(ii) Insert : This operation allows the Insertion of one character at any spot in the String.
(iii) Replace : This operation allows the replacement of any one character in the string with
any other character.

Solution: Edit distance problem in java.

Question 95: Coin change problem in java

Given an Amount to be paid and the currencies to pay with. There is infinite supply of every currency using combination of which, the given amount is to be paid. Print the number of ways by which the amount can be paid.

Solution: Coin change problem in java

Question 96 : Minimum number of jumps to reach last index

Solution: Minimum number of jumps to reach last index.

Miscellaneous

Question 97 : What is an algorithm and how to calculate complexity of algorithms.

Solution : How to calculate Complexity of algorithm

Question 98 : Implement trie data structure in java.

Solution : Implement trie data structure in java.

Question 99 : Count Factorial Trailing Zeroes in java.

Solution : Count Factorial Trailing Zeroes in java

Question 100 : Largest Rectangular Area in a Histogram.

Solution : Count Largest Rectangular Area in a Histogram

Question 101 : Check for balanced parentheses in an expression in java.

Solution : check for balanced parentheses in an expression in java.

Question 102 : What is Memoization.

Solution :
Memoization ensures that method does not execute more than once for same inputs by storing the results in the data structure(Usually Hashtable or HashMap or Array).
Memoization example in java

This is all about java coding interview questions. Please do comment if you want to add any new questions to above list.
You may also like:

• Core java interview questions
• Java Collections interview questions
• Java String interview questions
• OOPs interview questions in java
• Java Multithreading interview questions
• Exceptional handling interview questions in java
• Java Serialization interview questions in java
• web services interview questions
• restful web services interview questions
• Spring interview questions
• Hibernate interview questions

Let us understand this statement with some Sample inputs:

Input: String = "java2blog" K = 3
Output: 2
Explanation: The Substrings with length K=3 for the Given String are: "jav" , "ava", "va2", "a2b", "2bl", "blo", "log". Out of which the Substring "ava" has the maximum number of vowels i.e. 2.

Input: String = "looijk" K = 3
Output: 3 (Substring "ooi" has Maximum Vowel Letters).

Now, we will discuss different approaches to solve the problem and analyze their complexities.

Approach – 1 Generate All Substrings Using substring() Method

• Basically, we will iterate throughout the length of the String and generate [all substrings](https://java2blog.com/find-all-substrings-of-string-in-java/ “all substrings”) of the given length K using the substring() method present in String class of java.lang package.
• We Keep a Variable maxVowels which will be used to track the Maximum Vowels for a substring. So, For each substring, we count the number of Vowels in it and update the maxVowels.
• To count the number of vowels in a substring, we implement countVowelsInSubstring(), a method which given a substring will return the count of Vowels in it.

Let us look at the code for this approach:

public class MaxVowelsSubstring
{
  static int maxVowelsInSubstring(String s,int k)
  {
      int n = s.length();
      int maxVowels = 0;
      // we iterate till n-k th position of the string 
      for(int i = 0;i < n - k ;i++)
      {
        // We generate the substring of length k using substring().  
        String sub_s = s.substring(i,i+k);
        //then count the vowels in the substring
        int vowels = countVowelsInSubstring(sub_s);
        // update maxVowels if current vowels is greater.
        maxVowels = Math.max(maxVowels,vowels);

      }

      return maxVowels;
  }

  static int countVowelsInSubstring(String s)
  {
      int countVowels = 0;
      for(int i=0; i<s.length();i++)
      {
          //get current char
          char ch = s.charAt(i);
          // check if it is a vowel and increment count.              
          if(ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' )
          countVowels++;
      }
      return countVowels;
  }

  public static void main(String args[])
  {
      String str = "java2blog";
      int k = 3;
      int result = maxVowelsInSubstring(str,k);

      System.out.println("The Maximum Vowels present in the Substring of size "+k+" is : "+result);
  }

}

Output:

The Maximum Vowels present in the Substring of size 3 is : 2

Time Complexity: Generating a Substring of size K using substring() method takes O(K) time and we do this for N-K characters taking total O( (N-K) * K ) time. Now, for each substring of size K, we count the vowels in it which takes total O( K * K) = O(K2) time, so the Overall [time complexity](https://java2blog.com/introduction-to-complexity-of-algorithm/ “time complexity”) will be : O( N*K -K2 + K2) = O(N * K). This is a naïve solution for this problem.

Approach – 2 Using Sliding Window Method (Linear Time Solution)

The intention behind this approach is to give a Linear Runtime Solution(O(n)) to this problem. For this, we are going to use the idea of the Sliding Window Method. We follow these steps:

• At first, we will calculate the number of vowels in the first window of size K i.e. from the index 0 to K-1 as countVowels. We have a variable maxVowels that keeps track of the maximum number of vowels in a window.
• If the First Window has vowels we update the maxVowels. Then we start traversing from index K throughout the length of the String and calculate the vowels in each window. Consider the String "java2blog" the vowels present at different windows of the string is shown below:

• We use the idea of prefix array, after getting the vowels in 1st window, we start from the index K, if the character at index K is a vowel we increment the countVowels and if the character at the index i - k is a Vowel we decrement countVowels by 1. This step ensures the window slides to the right in every iteration.
• Finally, we update the maxVowels for each window that we process.

Now, let us have a look at the implementation of above approach in Code:

public class MaxVowelsSubstring
{
  static boolean isVowel(char ch)
  {
    if(ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u')
        return true;
    return false;
  }

  static int maxVowelsInSubstring(String s,int k)
  {
    int countVowels=0;  //Maintains overall count of vowels
    // Count vowels in First Window
    for(int i=0;i<k;i++)
    {
        if(isVowel(s.charAt(i)))
            countVowels++;
    }

    int maxVowels = 0;
    // Update maxVowels for first window.
    if(maxVowels< countVowels)
        maxVowels = countVowels;

    for(int i=k;i<s.length();i++)
    {
        if(isVowel(s.charAt(i)))          // check if current char is a vowel.    
            countVowels++;

        if(isVowel(s.charAt(i-k)))      // check if starting of previous window was a vowel
            countVowels--;

        maxVowels = Math.max(maxVowels,countVowels);   // update maxVowels for each window.
    }

    return maxVowels;
  }

  public static void main(String args[])
  {
      String str = "java2blog";
      int k = 3;
      int result = maxVowelsInSubstring(str,k);

      System.out.println("The Maximum Vowels present in the Substring of size "+k+" is : "+result);
  }

}

Output:

The Maximum Vowels present in the Substring of size 3 is : 2

Time Complexity: Basically, We slide the window throughout the length of string, N, and traverse each character only once. For each character, we check whether it is a Vowel which is an O(1) operation. So the Time Complexity of this approach is O(N) and gives an optimal solution to the problem.

That’s all about maximum number of vowels in a substring of Given Length, you can try the code with different examples considering all edge cases.

Basically, we need to determine the first and last occurrence of a duplicate key element in the Array. Consider this array for example:

Here, we can see an array of size 10 with duplicate elements 5 and 7. If we want to know the first and last occurrence of element 5, it will be at index 3 and 4 respectively. Similarly, for element 7, the first and last occurrence is at position/index 5 and 7 respectively.

Input: Array = {2,3,4,5,5,7,7,7,9,11}, target = 7
Output: 5,7                          // Comma separated Index of First and Last Occurrence.

Input: Array = {5,6,6,6,7,8,8,10}, target = 8
Output: 5,6

Now let us look at our approaches to solve this problem.

Approach 1 (Using Linear Search)

In this method, we will follow these steps:

• At first, we will traverse the array from the beginning or start index of the array. As soon as we get the target element, we store its index. This will indicate the first occurrence position of the target element. Then, we break out of the loop and stop traversing.
• Now, to get the last index, we will start traversing from the end index of the array and as soon as we get the target element, we store its index. This will indicate the last occurrence of the element. Then, we simply print those indices.

Let us look at the code for this method:

import java.util.*;

public class Example
{

  static void findFirstAndLastPosition(int arr[],int n,int target)
  {
     // We initialize first and last as -1 if the target is not present in the array.
      int first = -1;
      int last = -1;

      for(int i=0;i<n;i++)
      {
          if(arr[i] == target)
          {
              first = i;
              break;
          }
      }

      for(int i=n-1;i>=0;i--)
      {
          if(arr[i] == target)
          {
              last = i;
              break;
          }
      }

      System.out.println("The First occurrence of "+target+" at index : "+first+" and the Last occurrence is at index : "+last);
  }

  public static void main(String args[])
  {
   int arr[] = new int[]{2,3,4,5,5,7,7,7,9,11};
   int n = arr.length;

   int target = 7;
   findFirstAndLastPosition(arr,n,target);

  }

}

Output:

The First occurrence of 7 at index : 5 and the Last occurrence is at index : 7

Time Complexity: Here we perform a Linear Search to get the indexes if the the first occurrence is at second last element then we have to traverse the whole array. So, the overall runtime is O(n).

Approach 2 (Using Modified Binary Search-Optimal)

The idea or purpose of this approach is to minimize the runtime of the above method by using and modifying the Binary Search Algorithm. The breakdown of this approach is shown below:

• Basically, We implement two functions:
  1. findStartingIndex(Array,target) -> To get the Starting Index or First Occurrence of Target element.
  2. findEndingIndex(Array,target) -> To get the Ending Index or Last Occurrence of Target element.

• Now, for findStartingIndex() method, we will search the target by performing a modified binary search. We calculate mid = (low + high) / 2 (low =0 and high = Array_Size – 1). As the array is sorted, for each value of mid we need to perform operations based on three conditions.
  1. If(Arr[mid] >= target) -> This means if the element at index mid is greater than target element, then to get closer to target we need to update high = mid - 1 and search in the left half of the array. If the element is equal to target then also we need to update high, this will ensure we get as close as possible to the First Occurrence of the target.
  2. If the first condition does not hold true, it means the element is smaller than target, so we update low = mid + 1 and expand our search to the right half of the array.
  3. If(Arr[mid] == target) -> If we get the element at index mid equal to target, we store its index as a possible solution and continue our search until low<=high.
• Similarly for findEndingIndex() method, we search the target by making some changes. The algorithm remains the same as the method discussed above only the conditions need to be changed.
  1. If(Arr[mid] <= target) -> If the element at index mid is smaller than target, then to get closer to target we update low = mid + 1, instead of high and continue searching in the right half of array. If the element is equal then also we update low and get close to the Last occurrence of the target.
  2. If the first condition is not true, we update high = mid -1 and search in the left half of array as element at mid is greater than the target.
  3. If(Arr[mid] == target) -> If the element is equal, we store its index and continue these steps until low<=high.

Let us look at the implementation of above approach:

import java.util.*;

public class Example
{
  //finds Starting Index or First occurrence of target.
  static int findStartingIndex(int arr[],int n,int target)
  {
      int low = 0;
      int high = n-1;
      int index = -1;

      while(low <= high)
      {
      // Calculate mid value.      
      int mid = (low+high)/2;

      //Condition 1
      if(arr[mid]>=target)
      {
          high = mid-1;
      }
      // Condition 2 : When arr[mid] < target
      else
      {
          low = mid+1; 
      }
      // Condition 3
      if(arr[mid] == target)
      {
          index = mid;
      }

      }

      return index;
  }

  //finds Last occurrence of target.
  static int findEndingIndex(int arr[],int n,int target)
  {
      int low = 0;
      int high = n-1;
      int index = -1;

      while(low <= high)
      {
      // Calculate mid value.      
      int mid = (low+high)/2;

      //Condition 1
      if(arr[mid]<=target)
      {
          low = mid+1;
      }
      // Condition 2 : When arr[mid] > target
      else
      {
          high = mid-1; 
      }
      // Condition 3
      if(arr[mid] == target)
      {
          index = mid;
      }

      }

      return index;
  }

  static void findFirstAndLastPosition(int arr[],int n,int target)
  {
      int first = findStartingIndex(arr,n,target);
      int last = findEndingIndex(arr,n,target);
      System.out.println("The First occurrence of "+target+" at index : "+first+" and the Last occurrence is at index : "+last);
  }

  public static void main(String args[])
  {
   int arr[] = new int[]{5,6,6,6,7,8,8,10};
   int n = arr.length;

   int target = 8;
   findFirstAndLastPosition(arr,n,target);

  }

}

Output:

The First occurrence of 8 at index : 5 and the Last occurrence is at index : 6

Time complexity: We used Binary Search to get the first and last occurrence of the target element. We know binary search has runtime O(log n). Henceforth, the calls for findStartingIndex() and findEndingIndex() methods take O(log n) time each. So, the overall complexity is O(log n + log n) = O(log n). This is an optimal approach for this problem.

That’s all about Search for a range Leetcode – Find First and Last Position of Element in Sorted Array.

It is recommended to first learn Infix to postfix conversion before proceeding with this.

Now, let us have a quick recap. Infix Expressions are expressions where operators are written between every pair of operands and are of the form : x op y . Postfix Expressions are mathematical expressions where an operator is followed for every pair of operands and are of form : a b op . op is the operator, a and b are operands.

For Example: For the Postfix Expression: ABC-* , The Equivalent Infix will be A*(B - C).

Algorithm for Postfix to Infix in Java

1. We traverse the given Postfix expression from left to right. We will use a single stack Infix which stores operands and at the end will hold our resultant Infix Expression.
2. For each character, we will take two decisions:
   1. If the Character is a Operand we push it into Infix Stack.
   2. If the Character is a Operator, we pop two elements from the Stack, add last element with the operator and concatenate it with the first element and push the result back to the Infix Stack again for future evaluation.
3. At the time of adding a part of evaluated expression we enclose them within Parentheses to determine the order of operations.
4. When we traverse the whole string at the end, we will be left with only one value in our stack, which will be our Infix Expression.
   

Let us understand this with an example. Consider the Postfix expression : ABC- * D / .

Let us evaluate the given expression. We take decisions when we encounter Operator or Operands. The steps are:

• Step 1: We start iterating through each character (ignoring the spaces). At i=0, char = ‘A’ an Operand. We push it into Infix stack. At i=1 and i=2 char = ‘B’ and ‘C’ respectively, we push them into Infix stack. The stack looks like:

  

• Step 2: We continue, at i=3, char = ‘-‘ , an Operator we follow Step 2 Case 2, pop two elements from stack and add them with operator , we enclose the total expression within parentheses. Then, push the result back into stack. The stack now is :

  

• Step 3: At i=4, we get char = ‘*’, an operator . So we repeat the above step and the Infix stack is now:

  

• Step 4: At i=5, we get char = ‘D’ an operand we push it into stack.

  

• Step 5: Finally at i=6, char =’/’, we perform Step 2 again by popping the two remaining elements and the Infix stack now is :

  

The Infix stack at last contains our resultant infix Expression which is : (( A * (B - C)) / D).

Implementation for Postfix to Infix in Java

Let us now look at the implementation of above in JAVA:

import java.util.*;

class PostfixToInfix
{

static boolean isOperand(char ch)
{
  // we check for uppercase and lowercase alphabets.
  if(ch >= 'a' && ch <= 'z') 
   return true;

  else if(ch >= 'A' && ch <= 'Z')
   return true;

  return false;                 // if not an Operand return false;
}

// converts postfix to infix and returns the expression
static String convertToInfix(String postfix)
{
  Stack<String> inFix = new Stack<>();

  for (int i = 0; i < postfix.length(); i++)
  {
    char ch = postfix.charAt(i);

    if (isOperand(ch))
    {
    // Push operands to stack.    
    inFix.push(ch + "");
    }

    // Step 2: Evaluate part of the expression and push it again to stack.
    else
    {
    String op1 = inFix.pop();

    String op2 = inFix.pop();

    inFix.push("(" + op2 + ch + op1 + ")");
    }
  }

  return inFix.pop();
}

public static void main(String args[])
{
  String postfix = "ABC-*D/";
  System.out.println("The Postfix Expression is: "+ postfix);
  String result = convertToInfix(postfix);
  System.out.println("The Infix Expression is : "+result);
}

}

Output:

The Postfix Expression is: ABC-*D/
The Infix Expression is : ((A*(B-C))/D)

Let us look at the Time Complexity for this code. The time complexity is O(n), where n is the length of Postfix Expression.

So that’s all about Convert Postfix to Infix in Java. You can try out this code with different examples.

It is recommended to first go through Infix to postfix conversion for better understanding.

Let us understand what we mean by Prefix and Postfix Expression.

Prefix Expression is an expression where operators precede the operands. In simpler terms, the operators appear before the operands in the expression. They are of form : op X Y, op is operator and X,Y are operands. For Example: +AB is a Prefix Expression for Infix: A+B.

Postfix Expressions re of the form X Y op, where operators come after operands. For Example: AB+ is the Postfix for Infix: A+B.

We need to convert Prefix to Postfix so for the Prefix Expression : + / AB * CD , the Infix will be : (A / B) + (C * D). Then on converting this infix the resultant Postfix Expression will be : AB/ CD* + .

Now, to convert Prefix expression into Postfix, we can try first converting the Prefix into Infix notation then convert the result into Postfix. But, we can do this in a single step by directly converting the Prefix into Postfix. Let us look at the Algorithm.

Algorithm for prefix to postfix

1. We will start traversing the Prefix Expression from Right to Left, unlike what we did in Infix to Postfix Conversion. We will use a single Stack Postfix which will hold the operands and a part of evaluated Postfix expression. When we reach the end ( at i = -1) , the stack will hold the resultant Postfix expression.
2. For each character we encounter, we consider two cases:
   1. f the Character is a Operand we push it into the Postfix Stack.
   2. If the Character is a Operator we pop two elements from the Stack, add two elements together followed with the operator and push the result back to the Postfix Stack again for future evaluation. This will be the part of total Postfix.
3. When we come to end of the String traversing from Right (Length-1) to Left (0) , at i=-1 we stop and at the at the end the Postfix stack contain only one value, which will be the resultant Postfix Expression.

Now, let us understand this algorithm with an example. Consider the Prefix expression : /+AB-CD. The Infix for this is : ((A + B) / (C – D)).

Let us evaluate the given expression step by step. We take decisions when we encounter Operator or Operands. The steps are:

• Step 1: We start iterating from the end of the string (length – 1 = 7 – 1 = 6 ) to start index. At i=6, we have char = ‘D’, an operand so we push it into the Postfix Stack. At i=5, we have char = ‘C’, we push it into the stack. The Postfix stack now is:

  

• Step 2: We continue iteration at i=4, char = ‘-‘ , an operator, so we pop two operands from stack and add them with the operator in the same order. We then push the result (CD-) into the Postfix stack again for future evaluation. The stack now is:

  

• Step 3: Now at i=3, we have char = ‘B’, and at i=2, we have char = ‘A’, since both are operands so we push them into stack one by one . The Postfix stack is now:

  

• Step 4: At i=1, char = ‘+’, an Operator. So we perform Step 2 again by popping and adding the two elements with the operator and then push the result (AB+) back to stack. The Postfix stack now looks :

  

• Step 5: Finally At i=0, we get char =’/’, an Operator so we pop both the operands (AB+ and CD-) and add it with the operator. We stop iteration as we reached index 0. The Postfix stack at the end now contains our resultant Postfix Expression which is :

  

Implementation for Prefix to postfix conversion in java

Let us look at the implementation of the above example in JAVA:

import java.util.*;

class PrefixToPostfix 
{

  // check if character is operator or not
  static boolean isOperator(char ch)
  {
    if(ch == '+' || ch == '-' || ch == '*' || ch == '/')
    return true;

    return false;
  }

  // Convert prefix to Postfix expression
  static String convertPrefixToPostfix(String prefix)
  {
    Stack<String> postFix = new Stack<>();

    // length of prefix expression
    int n = prefix.length();

    // reading from right to left
    for (int i = n - 1; i >= 0; i--)
    {
      char ch= prefix.charAt(i);

      // check if symbol is operator
      if (isOperator(ch))
      {
      // pop two operands from stack
      String first = postFix.pop();

      String second = postFix.pop();

      // concat the operands and operator to form Postfix
      String temp_postFix = first + second + ch;

      // Push the partly evaluated postfix back to stack
      postFix.push(temp_postFix);
      }

      // if symbol is an operand
      else 
      { 
      // push the operand to the stack
      postFix.push(ch + "");
      }
    }

    // stack contains only the Postfix expression
    return postFix.pop();
  }

  public static void main(String args[])
  {
    String prefix = "/+AB-CD";      // Infix is : (A+B) / (C-D).
    System.out.println("The Prefix Expression is: "+prefix);
    String result = convertPrefixToPostfix(prefix);
    System.out.println("The Equivalent Postfix is : "+ result);  

    System.out.println();

    prefix = "*+AB/-CDE";          // Infix is : (A+B) * ((C-D)/E).
    System.out.println("The Prefix Expression is: "+prefix);
    result = convertPrefixToPostfix(prefix);
    System.out.println("The Equivalent Postfix is : "+ result);  

  }

}

Output:

The Prefix Expression is: /+AB-CD
The Equivalent Postfix is : AB+CD-/

The Prefix Expression is: *+AB/-CDE
The Equivalent Postfix is : AB+CD-E/*

We have implemented two examples. Now let us look at the Time Complexity of our approach.

Time complexity

Time Complexity: As we traverse the whole input string once and the stack operations require constant time, the overall time complexity is O(n), n is the length of Prefix Expression.

So that’s all about how to convert Prefix to postfix in java. You can try with different examples and execute this code for better understanding.

Let us quickly look into Infix and Postfix expression:

Infix expressions are the expression where operators are written in between every pair of operands. It is the usual way to write an expression. For Ex: An expression like A + B is Infix.

Postfix expressions are the expressions where operands precede operators. Here operators are written after operands. The Expression AB+ is Postfix and is the Postfix representation of the above shown A+B. The evaluation order is from left to right.

Why we use Postfix expression?

The expressions we (humans) write are Infix Expression, but for the machines to understand these expression they need to be converted. The compiler scans an expression from left to right. If an infix expression such as A*(B+C) is provided, the compiler will scan the expression to evaluate B+C then scan again to multiply the result with A. This results in multiple scanning. So, it is recommended to use Postfix notations which for the given expression is: ABC+* . A compiler can then easily evaluate the result in one go.

Now how is the conversion done? We will look into the algorithm for this along with an example.

Conversion Algorithm

We will use two Stacks : One for Operators (Character), One for Operands (String). The Operand stack will contain the resultant Postfix expression after traversing string. The Infix expression will be given as a String input. We will take decisions when we encounter Parentheses, Operators and Operands. So the steps are:

• Step 1: We will iterate throughout the String length. For each character, there are three cases to consider :

  1. 1. If the Current character is a Operand.
  2. 2. If the character is a Open or Close Parentheses.
  3. 3. If the character is an Operator.

• Step 2: If the Character at each iteration is a Operand. We simply push it into the operand or Postfix stack.

• Step 3: If the character encountered is : '(' , i.e. Opening Parentheses, we push it into Operator Stack.

• Step 4: Now, if we encounter ')' i.e. Closing Parenthesis, we are going to pop the elements out of Operator Stack until we get the opening '('. For each operator we pop its two operands and process them.

• Step 5: The process for each operator is : We pop two elements from Postfix or operand Stack we concatenate them in reverse order with its operator and add the result again to Postfix stack for future evaluation until we get the total Postfix expression.

• Step 6: Now if we get an Operator as the current character, we check whether the precedence of current operator is lower than the operator present at top of the stack. If the condition is true, we pop the operator present at the top and process its operands following Step 5. Then we push the current operator into the stack.

• Step 7: At last after traversing the whole string if still we are left with any operators we pop them and continue Step 5 until the Operator Stack is empty. At last, the Postfix stack will have only one element which will be our resultant Postfix Expression.

Note: The Precedence of * and / are equal and higher than + and - operation.

Let us understand this Algorithm with an example:

Consider the Infix : A * (B-C) / D + E
We take 2 Stacks: Operator and Postfix, and do the following steps:

1. We start iterating through each character (ignoring the spaces). At i=0, char = ‘A’ an Operand. We push it into Postfix stack. At i=1, char = ‘*’ an operator, we push it into operator stack. The stacks look like:

2. We continue at i=2, char = ‘(‘ , an opening parenthesis we push it into operator stack, at i=3, char =’B’ we push it into Postfix stack . At i=4, char = ‘-‘ we push it into Operator stack, at i=5, char = ‘C’ we push into the Postfix stack. The stacks now look like:

3. We continue iterating, at i=6; char =’)’ i.e. a Closing Parenthesis, so now we follow Step 4 and Step 5 of the algorithm . We pop elements from operator stack until we get the Opening Parenthesis. Then, we pop two elements from Postfix stack (C and B), concatenate them in reverse order with the operator in reverse order (BC-) and add the result into the Postfix stack again. Then we pop ‘)’. The stacks now look like :

4. Then at i=7, char = /, an operator, we need to add it to our Operator stack but before doing it we check whether there is an operator in the stack with precedence higher or equal to current operator . There is * operator in stack with precedence equal to / ,so we process it following Step 5. Then push / operator. So we pop * and add it with operands (A and BC- ) using Step 5. The stacks now look like :

5. We continue, at i=8, char =D, we push it into Postfix stack. At i=9, we have + operator, we again check the stack for any operator with greater precedence. / has higher precedence, so we process it first like shown above using Step 5 then push + into the Stack. The stacks now are:

6. Finally at i=10, we have char = E, so we push it in the postfix stack.

7. Now this is an important point, After traversing the string if there are still any operators left in the stack, we process them repeating Step 5 until we get the final expression. In this case, after iterating the string the + is still remaining in Operator Stack. After processing the last operator the stacks now look like :

Note: The Postfix stack at last will hold the Postfix expression and will be the only element.

Implementation

Now let us look at the implementation code in JAVA:

import java.util.*;
public class InfixtoPostfix
{

public static int precedence(char ch)
{
 if(ch=='+' || ch=='-')
 return 1;

 else if(ch=='*' || ch=='/')
 return 2;                       // * and / divide have higher precedence.

  return 0;
}

public static String convertToPostfix(String exp)
{
 Stack<Character> operators = new Stack<>();
 Stack<String> postFix = new Stack<>();

 for(int i=0;i<exp.length();i++)
 {
  char ch=exp.charAt(i);         // current character.

  if(ch=='(')
   operators.push(ch);

  else if((ch>='a' && ch<='z') || (ch>='A' && ch<='Z'))
   postFix.push(ch+"");

  else if(ch==')')
  {
   while(operators.peek()!= '(')
   {
    // STEP 5 of Algorithm.    
    char op = operators.pop();

    String first = postFix.pop();          // get the two operands.
    String second = postFix.pop();

    String new_postFix = second+first+op;  // add them in reverse order.

    postFix.push(new_postFix);     // push the result to postFix stack again.
   }

   operators.pop();     // pop '(' from stack.   
  }

      // We do the same thing if we get an operator as the current character.

  else if(ch=='+' || ch=='-' || ch== '*' || ch== '/')
  {
  // check precedence of each operator with top of the stack and process them.
   while(operators.size()>0 && operators.peek()!='(' && precedence(ch) <= precedence(operators.peek()))
   {
   char op = operators.pop();

   String first = postFix.pop();
   String second = postFix.pop();

   String new_postFix = second+first+op;

   postFix.push(new_postFix);
   }

  operators.push(ch);
  }
 }

 // If the operator stack still has some elements in it process them too Repeat Step 5.
 while(operators.size()>0)
 {
  char op = operators.pop();

  String first = postFix.pop();
  String second = postFix.pop();

  String new_postFix = second+first+op;

  postFix.push(new_postFix);
  }

  return postFix.pop();         // return resultant Postfix.
}

public static void main(String args[])
{
  // We pass Uppercase Infix
  String infixExpression = "A*(B-C)/D+E";
  System.out.println("The Infix Expression is: "+infixExpression);
  String result = convertToPostfix(infixExpression);
  System.out.println("The Postfix of the given Infix Expression is: "+result);

  System.out.println();

  //We also check for Lowercase Infix
  infixExpression = "a*(b-c+d)/e";
  System.out.println("The Infix Expression is: "+infixExpression);
  result = convertToPostfix(infixExpression);
  System.out.println("The Postfix of the given Infix Expression is: "+result);

}
}

Output:

The Infix Expression is: A*(B-C)/D+E
The Postfix of the given Infix Expression is: ABC-*D/E+

The Infix Expression is: a*(b-c+d)/e
The Postfix of the given Infix Expression is: abc-d+*e/

This the output for the above discussed example and a sample. Let us look into the the time complexity of our approach.

Time Complexity: We do a single traversal of the string to convert it into Postfix expression so the time complexity is O(n) , n is the length of Infix Expression.

That’s all about how to convert infix to postfix in java. You can try out this with various examples and execute this code for a clear idea.

Data structure is a way of storing and organizing data. Data structure provide a way to process and store data efficiently.

For example:

Imagine you have pile of books on the table and you are going to read these books one by one from the top. Can you think of any data structure which can simulate with this?
Yes, you can simply use stack to store the books, so it can be accessed in Last in first out fashion.

In this post, I am going to cover list of all important data structures in java which you can easily implement.

Array

Array is linear data structure which stores fixed number of similar elements. Array can store primitive data types as well as object but it should be of same kind. This is one of most used data structures in java.

Declare and initialize array in java

You can declare a String array as below:

String[] strArr=new String[10];

Here,
String is data type
strArr is variable name
10 is size of the array

You can also initialize array as below:

String[] strArr={"One","Two","Three"};

Advantages of array

• You can randomly access array elements using index
• It can represent multiple elements of same type with single name
• You can implement various data strucures such as LinkedList, Stack and Queue using Array

Disadvantages of array

• You need to know number of elements in advance.
• You can not modify array once its size is defined
• Insertion and deletion are quite costly operation in array as you need to shift elements.

Example

Here is an example program of an array.

package org.arpit.java2blog;

import java.util.Arrays;
public class StringArrayMain {

    public static void main(String[] args) {
        String[] strArr = {"One","Two","Three"};

        System.out.println("Array elements are:");
        // Iterate over array
        for (int i=0;i

Output:

Array elements are:

One

Two

Three

====================

Printing array elements using Arrays.toString():

====================

[One, Two, Three]



        

          import_contacts

        

Array practice programs

There are many java tricky  interview programs that can be asked in interview.
You should practice these java interview programs on array.

Find smallest and largest element in array
Find second largest number in array
Find missing number in an array
Separate 0’s and 1’s in array
Separate odd even numbers in java
Sort array of 0’s, 1’s and 2’s in java
Find number occurring odd number of times in array
Minimum numbers of platforms required for railway station in java
Find pair whose sum is closest to zero in array in java
Find pair whose sum is closest to X in array in java
Find all pairs of elements whose sum is equal to given number
Search element in row wise and column wise sorted matrix
Stock buy and sell to maximize profit.
Find local minima in array
Find leader in array
Find subarray with given sum
Sliding window maximum
Find peak element in array
Permutations of array in java
Subsets of set
Rotate array by K positions
Largest sum contiguous subarray
search an element in a sorted and rotated arraybinary in java
Minimum element in a sorted and ratated array in java
Minimum jumps required to reach end of array


Stack
Stack is abstract data type which depicts Last in first out (LIFO) behavior.

Stack implementation using Array
package org.arpit.java2blog.datastructures;

/**
 * @author Arpit Mandliya
 */
public class MyStack {
    int size;
    int arr[];
    int top;

    MyStack(int size) {
        this.size = size;
        this.arr = new int[size];
        this.top = -1;
    }

    public void push(int element) {
        if (!isFull()) {
            top++;
            arr[top] = element;
            System.out.println("Pushed element:" + element);
        } else {
            System.out.println("Stack is full !");
        }
    }

    public int pop() {
        if (!isEmpty()) {
            int topElement = top;
            top--;
            System.out.println("Popped element :" + arr[topElement]);
            return arr[topElement];

        } else {
            System.out.println("Stack is empty !");
            return -1;
        }
    }

    public int peek() {
        if(!this.isEmpty())
            return arr[top];
        else
        {
            System.out.println("Stack is Empty");
            return -1;
        }
    }

    public boolean isEmpty() {
        return (top == -1);
    }

    public boolean isFull() {
        return (size - 1 == top);
    }

    public static void main(String[] args) {
        MyStack myStack = new MyStack(5);
        myStack.pop();
        System.out.println("=================");
        myStack.push(100);
        myStack.push(90);
        myStack.push(10);
        myStack.push(50);
        System.out.println("=================");
        myStack.pop();
        myStack.pop();
        myStack.pop();
        System.out.println("=================");
    }
}

Output:

Stack is empty !

=================

Pushed element:100

Pushed element:90

Pushed element:10

Pushed element:50

=================

Popped element :50

Popped element :10

Popped element :90

=================

Stack implementation using LinkedList
package org.arpit.java2blog.datastructures;

public class StackUsingLinkedList {
    private Node head; // the first node

    // nest class to define linkedlist node
    private class Node {
        int value;
        Node next;
    }

    public StackUsingLinkedList() {
        head = null;
    }

    // Remove value from the beginning of the list to simulate stack
    public int pop() throws LinkedListEmptyException {
        if (head == null) {
            throw new LinkedListEmptyException();
        }
        int value = head.value;
        head = head.next;
        return value;
    }

    // Add value to the beginning of the list to simulate stack
    public void push(int value) {
        Node prevHead = head;
        head = new Node();
        head.value = value;
        head.next = prevHead;
    }

    public static void main(String args[])
    {
        StackUsingLinkedList sll=new StackUsingLinkedList();
        sll.push(200);
        sll.push(150);
        sll.push(80);
        sll.push(90);
        sll.push(600);
        sll.push(175);
        System.out.println("Removed element from LinkedList: "+sll.pop());
        System.out.println("Removed element from LinkedList: "+sll.pop());
        sll.push(100);
        System.out.println("Removed element from LinkedList: "+sll.pop());
        printList(sll.head);
    }
    public static void printList(Node head) {
        Node temp = head;
        while (temp != null) {
            System.out.format("%d ", temp.value);
            temp = temp.next;
        }
        System.out.println();
    }
}

/**
 *
 * Throw LinkedListEmptyException if LinkedList is empty
 */

class LinkedListEmptyException extends RuntimeException {
    private static final long serialVersionUID = 1L;

    public LinkedListEmptyException() {
        super();
    }

    public LinkedListEmptyException(String message) {
        super(message);
    }
}

Output:

Removed element from LinkedList: 175

Removed element from LinkedList: 600

Removed element from LinkedList: 100

90 80 150 200

Implementation

 Java Program to implement stack using array.
Java Program to implement stack using Linked List
 Java Program to implement stack using two queues

Practice Programs
Sort a stack using another stack.
Queue
Queue is abstract data type which depicts First in first out (FIFO) behavior.

Queue implementation using array
package org.arpit.java2blog.datastructures;

public class MyQueue {

    private int capacity;
    int queueArr[];
    int front;
    int rear;
    int currentSize = 0;

    public MyQueue(int size) {
        this.capacity = size;
        front = 0;
        rear = -1;
        queueArr = new int[this.capacity];
    }

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

    /**
     * Method for checking if Queue is full
     *
     * @return
     */
    public boolean isFull() {
        if (currentSize == capacity) {
            return true;
        }
        return false;
    }

    /**
     * Method for checking if Queue is empty
     *
     * @return
     */
    public boolean isEmpty() {

        if (currentSize == 0) {
            return true;
        }
        return false;
    }

    public static void main(String a[]) {

        MyQueue myQueue = new MyQueue(6);
        myQueue.enqueue(1);
        myQueue.dequeue();
        myQueue.enqueue(30);
        myQueue.enqueue(44);
        myQueue.enqueue(32);
        myQueue.dequeue();
        myQueue.enqueue(98);
        myQueue.dequeue();
        myQueue.enqueue(70);
        myQueue.enqueue(22);
        myQueue.dequeue();
        myQueue.enqueue(67);
        myQueue.enqueue(23);
    }
}

Output:

1 added to the queue

1 removed from the queue

30 added to the queue

44 added to the queue

32 added to the queue

30 removed from the queue

98 added to the queue

44 removed from the queue

70 added to the queue

22 added to the queue

32 removed from the queue

67 added to the queue

23 added to the queue

Queue implementation using LinkedList
package org.arpit.java2blog.datastructures;

public class QueueUsingLinkedList
{
    private Node front, rear;
    private int currentSize; // size

    //Node data structure
    private class Node
    {
        int data;
        Node next;
    }

    //constructor
    public QueueUsingLinkedList()
    {
        front = null;
        rear = null;
        currentSize = 0;
    }

    public boolean isEmpty()
    {
        return (currentSize == 0);
    }

    //Remove item from the beginning of the list to simulate Queue
    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 to simulate Queue
    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[]){

        QueueUsingLinkedList queueUsingLinkedList = new QueueUsingLinkedList();
        queueUsingLinkedList.enqueue(60);
        queueUsingLinkedList.dequeue();
        queueUsingLinkedList.enqueue(10);
        queueUsingLinkedList.enqueue(20);
        queueUsingLinkedList.enqueue(40);
        queueUsingLinkedList.dequeue();
        queueUsingLinkedList.enqueue(70);
        queueUsingLinkedList.dequeue();
        queueUsingLinkedList.enqueue(80);
        queueUsingLinkedList.enqueue(100);
        queueUsingLinkedList.dequeue();
        queueUsingLinkedList.enqueue(150);
        queueUsingLinkedList.enqueue(50);
    }
}

Output:

60 added to the queue

60 removed from the queue

10 added to the queue

20 added to the queue

40 added to the queue

10 removed from the queue

70 added to the queue

20 removed from the queue

80 added to the queue

100 added to the queue

40 removed from the queue

150 added to the queue

50 added to the queue

Implementation

 Implement queue using arrays
 Implement queue using linked list

LinkedList
Singly LinkedList

In singly linked list, Node has data and pointer to next node. It does not have pointer to the previous node. Last node ‘s next points to null, so you can iterate over linked list by using this condition.
package org.arpit.java2blog.datastructures;

class Node {
    public int data;
    public Node next;

    public void displayNodeData() {
        System.out.println("{ " + data + " } ");
    }
}

public class MyLinkedList {
    private Node head;

    public boolean isEmpty() {
        return (head == null);
    }

    // Method for inserting node at the start of linked list
    public void insertFirst(int data) {
        Node newHead = new Node();
        newHead.data = data;
        newHead.next = head;
        head = newHead;
    }

    // Method for deleting node from start of linked list
    public Node deleteFirst() {
        Node temp = head;
        head = head.next;
        return temp;
    }

    // Method used to delete node after provided node
    public void deleteAfter(Node after) {
        Node temp = head;
        while (temp.next != null && temp.data != after.data) {
            temp = temp.next;
        }
        if (temp.next != null)
            temp.next = temp.next.next;
    }

    // Method used to insert at end of LinkedList
    public void insertLast(int data) {
        Node current = head;
        while (current.next != null) {
            current = current.next; // we'll loop until current.next is null
        }
        Node newNode = new Node();
        newNode.data = data;
        current.next = newNode;
    }

    // Method for printing Linked List
    public void printLinkedList() {
        System.out.println("Printing LinkedList (head --> last) ");
        Node current = head;
        while (current != null) {
            current.displayNodeData();
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String args[])
    {
        MyLinkedList myLinkedlist = new MyLinkedList();
        myLinkedlist.insertFirst(50);
        myLinkedlist.insertFirst(60);
        myLinkedlist.insertFirst(70);
        myLinkedlist.insertFirst(10);
        myLinkedlist.insertLast(20);
        myLinkedlist.printLinkedList();
        // Linked list will be
        // 10 -> 70 ->  60 -> 50 -> 20

        System.out.println("=========================");
        System.out.println("Delete node after Node 60");
        Node node=new Node();
        node.data=60;
        myLinkedlist.deleteAfter(node);
        // After deleting node after 1,Linked list will be
        // 10 -> 70 -> 60 -> 20

        System.out.println("=========================");
        myLinkedlist.printLinkedList();
    }
}

Output:

Printing LinkedList (head –> last)

{ 10 }

{ 70 }

{ 60 }

{ 50 }

{ 20 } 

=========================

Delete node after Node 60

=========================

Printing LinkedList (head –> last)

{ 10 }

{ 70 }

{ 60 }

{ 20 }

Doubly LinkedList

In doubly linked list, Node has data and pointers to next node and previous node.You can iterate over linkedlist either in forward or backward direction as it has pointers to prev node and next node. This is one of most used data structures in java.
package org.arpit.java2blog.datastructures;

class Node {
    public int data;
    public Node next;
    public Node prev;

    public void displayNodeData() {
        System.out.println("{ " + data + " } ");
    }
}

public class MyDoublyLinkedList {

    private Node head;
    private Node tail;
    int size;

    public boolean isEmpty() {
        return (head == null);
    }

    // Method to insert a node at the start of linked list
    public void insertFirst(int data) {
        Node newNode = new Node();
        newNode.data = data;
        newNode.next = head;
        newNode.prev=null;
        if(head!=null)
            head.prev=newNode;
        head = newNode;
        if(tail==null)
            tail=newNode;
        size++;
    }

    // Method to insert a node at the start of linked list
    public void insertLast(int data) {
        Node newNode = new Node();
        newNode.data = data;
        newNode.next = null;
        newNode.prev=tail;
        if(tail!=null)
            tail.next=newNode;
        tail = newNode;
        if(head==null)
            head=newNode;
        size++;
    }
    // used to delete node from start of Doubly linked list
    public Node deleteFirst() {

        if (size == 0)
            throw new RuntimeException("Doubly linked list is already empty");
        Node temp = head;
        head = head.next;
        head.prev = null;
        size--;
        return temp;
    }

    // Method to delete node from last of Doubly linked list
    public Node deleteLast() {

        Node temp = tail;
        tail = tail.prev;
        tail.next=null;
        size--;
        return temp;
    }

    // Method to delete node after particular node
    public void deleteAfter(Node after) {
        Node temp = head;
        while (temp.next != null && temp.data != after.data) {
            temp = temp.next;
        }
        if (temp.next != null)
            temp.next.next.prev=temp;
        temp.next = temp.next.next;

    }

    // Method to print Doubly Linked List forward
    public void printLinkedListForward() {
        System.out.println("Printing Doubly LinkedList (head --> tail) ");
        Node current = head;
        while (current != null) {
            current.displayNodeData();
            current = current.next;
        }
        System.out.println();
    }

    // Method to print Doubly Linked List forward
    public void printLinkedListBackward() {
        System.out.println("Printing Doubly LinkedList (tail --> head) ");
        Node current = tail;
        while (current != null) {
            current.displayNodeData();
            current = current.prev;
        }
        System.out.println();
    }

    public static void main(String args[])
    {
        MyDoublyLinkedList mdll = new MyDoublyLinkedList();
        mdll.insertFirst(50);
        mdll.insertFirst(60);
        mdll.insertFirst(70);
        mdll.insertFirst(10);
        mdll.insertLast(20);
        mdll.printLinkedListForward();
        mdll.printLinkedListBackward();

        System.out.println("================");
        // Doubly Linked list will be
        // 10 ->  70 -> 60 -> 50 -> 20

        Node node=new Node();
        node.data=10;
        mdll.deleteAfter(node);
        mdll.printLinkedListForward();
        mdll.printLinkedListBackward();
        // After deleting node after 1,doubly Linked list will be
        // 20 -> 10 -> 60-> 50
        System.out.println("================");
        mdll.deleteFirst();
        mdll.deleteLast();

        // After performing above operation, doubly Linked list will be
        //  60 -> 50
        mdll.printLinkedListForward();
        mdll.printLinkedListBackward();
    }
}

Output:

Printing Doubly LinkedList (head –> tail)

{ 10 }

{ 70 }

{ 60 }

{ 50 }

{ 20 } 

Printing Doubly LinkedList (tail –> head)

{ 20 }

{ 50 }

{ 60 }

{ 70 }

{ 10 } 
================

Printing Doubly LinkedList (head –> tail)

{ 10 }

{ 60 }

{ 50 }

{ 20 } 
Printing Doubly LinkedList (tail –> head)

{ 20 }

{ 50 }

{ 60 }

{ 10 } 
================

Printing Doubly LinkedList (head –> tail)

{ 60 }

{ 50 } 
Printing Doubly LinkedList (tail –> head)

{ 50 }

{ 60 }

Implementation

Implement singly linked list in java
Implement Doubly linked list in java



        

          import_contacts

        

LinkedList Practice Programs


How to reverse a linked list in java
How to reverse a linked list in pairs
How to find middle element of linked list in java
How to detect a loop in linked list in java
Find start node of loop in linkedlist
How to find nth element from end of linked list
How to check if linked list is palindrome in java
Add two numbers represented by linked list in java
Find intersection of two Linked Lists


Binary tree
A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child
Example of binary tree:

package org.arpit.java2blog.datastructures;

import java.util.Stack;

public class BinaryTree {

    public static class Node
    {
        int data;
        Node left;
        Node right;
        Node(int data)
        {
            this.data=data;
        }
    }

    // Recursive Solution
    public void preorder(Node root) {
        if(root !=  null) {
            //Pre order traversal
            System.out.printf("%d ",root.data);
            preorder(root.left);
            preorder(root.right);
        }
    }

    // Iterative solution
    public void preorderIter(Node root) {

        if(root == null)
            return;

        Stack s = new Stack();
        s.push(root);

        while(!s.empty()){

            Node n = s.pop();
            System.out.printf("%s ",n.data);

            if(n.right != null){
                s.push(n.right);
            }
            if(n.left != null){
                s.push(n.left);
            }

        }

    }

    public static void main(String[] args)
    {
        BinaryTree bi=new BinaryTree();
        // Creating a binary tree
        Node rootNode=createBinaryTree();
        System.out.println("Using Recursive solution:");

        bi.preorder(rootNode);

        System.out.println();
        System.out.println("-------------------------");
        System.out.println("Using Iterative solution:");

        bi.preorderIter(rootNode);
    }

    public static Node createBinaryTree()
    {

        Node rootNode =new Node(30);
        Node node20=new Node(50);
        Node node10=new Node(60);
        Node node30=new Node(80);
        Node node60=new Node(90);
        Node node50=new Node(100);
        Node node70=new Node(110);

        rootNode.left=node20;
        rootNode.right=node60;

        node20.left=node10;
        node20.right=node30;

        node60.left=node50;
        node60.right=node70;

        return rootNode;
    }
}

Output:

Using Recursive solution:

30 50 60 80 90 100 110

————————-

Using Iterative solution:

30 50 60 80 90 100 110

Implementation
Binary tree in java


        

          import_contacts

        

Binary tree practice programs


Binary tree in java
Binary tree preorder traversal
Binary tree postorder traversal
Binary tree inorder traversal
Binary tree level order traversal
Binary tree spiral order traversal
Binary tree reverse level order traversal
Binary tree boundary traversal
Print leaf nodes of binary tree
Count leaf nodes in binary tree
get maximum element in binary tree
Print all paths from root to leaf in binary tree
Print vertical sum of binary tree in java
Get level of node in binary tree in java
Lowest common ancestor(LCA) in binary tree in java


Binary Search tree
Binary search tree is a special type of binary tree which have following properties.

Nodes which are smaller than root will be in left subtree.
Nodes which are greater than root will be right subtree.
It should not have duplicate nodes
Both left and right subtree also should be binary search tree.


package org.arpit.java2blog.datastructures;

public class MyBinarySearchTree {
    public static class Node
    {
        int data;
        Node left;
        Node right;
        Node(int data)
        {
            this.data=data;
        }
    }

    public static boolean search(Node root, Node nodeToBeSearched)
    {
        if(root==null)
            return false;
        if(root.data== nodeToBeSearched.data)
        {
            return true;
        }
        boolean result=false;

        if(root.data > nodeToBeSearched.data)
            result=search(root.left,nodeToBeSearched);
        else if(root.data < nodeToBeSearched.data)
            result= search(root.right,nodeToBeSearched);

        return result;
    }

    public static Node insert(Node root, Node nodeToBeInserted)
    { if(root==null) {
        root=nodeToBeInserted; return root;
    } if(root.data > nodeToBeInserted.data)
    {
        if(root.left==null)
            root.left=nodeToBeInserted;
        else
            insert(root.left,nodeToBeInserted);
    }
    else if(root.data < nodeToBeInserted.data)
        if(root.right==null)
            root.right=nodeToBeInserted;
        else
            insert(root.right,nodeToBeInserted);
        return root;
    }

    public static void inOrder(Node root)
    {
        if(root==null)
            return;
        inOrder(root.left);
        System.out.print(root.data+" ");
        inOrder(root.right);
    }
    public static void main(String[] args)
    {
        // Create binary search tree
        Node rootNode=createBinarySearchTree();
        Node node55=new Node(55);
        boolean result=search(rootNode,node55);
        System.out.println("Searching for node 55 : "+result);
        System.out.println("---------------------------");
        Node node13=new Node(13);
        Node root=insert(rootNode,node13);
        System.out.println("Inorder traversal of binary tree after adding 13:");
        inOrder(root);

    }

    public static Node createBinarySearchTree()
    {
        Node rNode =new Node(40);
        Node node20=new Node(20);
        Node node10=new Node(10);
        Node node30=new Node(30);
        Node node60=new Node(60);
        Node node50=new Node(50);
        Node node70=new Node(70);
        Node node5=new Node(5);
        Node node55=new Node(55);

        insert(null,rNode);
        insert(rNode,node20);
        insert(rNode,node10);
        insert(rNode,node30);
        insert(rNode,node60);
        insert(rNode,node50);
        insert(rNode,node70);
        insert(rNode,node5);
        insert(rNode,node55);
        return rNode;
    }

}

Output:

Searching for node 55 : true

—————————

Inorder traversal of binary tree after adding 13:

5 10 13 20 30 40 50 55 60 70

Implementation
Binary search tree in java


        

          import_contacts

        

Binary search tree Practice programs


Binary search tree in java
Delete node from binary search tree
Minimum and maximum elements in binary search tree
LCA of binary search tree
inorder successor in binary search tre
Conver sorted array to balanced BST
Convert sorted Linked List to balanced BST
Convert sorted Linked List to balanced BST
Check if a binary tree is binary search tree or not in java


Trie
Trie is data structure which is used to store in such a way that data can be retrieved faster.

Some real time examples:

Trie can be used to implement Dictionary.
We can put words in Trie and its children linkedlist will have its child nodes.

Let’s say you want to insert do, deal , dear , he , hen , heat etc.
Here is the trie representation of the data:

package org.arpit.java2blog.datastructures;

/*
 *  Java Program to Implement Trie
 */

import java.util.*;

class TrieNode
{
    char data;
    boolean isEnd;
    int count;
    LinkedList childList;

    /* Constructor */
    public TrieNode(char c)
    {
        childList = new LinkedList();
        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 Trie
{
    private TrieNode root;

    /* Constructor */
    public Trie()
    {
        root = new TrieNode(' ');
    }
    /* Method for inserting words from trie*/
    public void insert(String word)
    {
        if (search(word) == true)
            return;
        TrieNode tempCurr = root;
        for (char ch : word.toCharArray() )
        {
            TrieNode child = tempCurr.getChild(ch);
            if (child != null)
                tempCurr = child;
            else
            {
                // If child not present, adding it io the list
                tempCurr.childList.add(new TrieNode(ch));
                tempCurr = tempCurr.getChild(ch);
            }
            tempCurr.count++;
        }
        tempCurr.isEnd = true;
    }
    /* Method for searching words in Trie*/
    public boolean search(String word)
    {
        TrieNode tempCurr = root;
        for (char ch : word.toCharArray() )
        {
            if (tempCurr.getChild(ch) == null)
                return false;
            else
                tempCurr = tempCurr.getChild(ch);
        }
        if (tempCurr.isEnd == true)
            return true;
        return false;
    }
    /* Method for removing words from trie*/
    public void remove(String word)
    {
        if (search(word) == false)
        {
            System.out.println(word +" does not present in trien");
            return;
        }
        TrieNode tempCurr = root;
        for (char ch : word.toCharArray())
        {
            TrieNode child = tempCurr.getChild(ch);
            if (child.count == 1)
            {
                tempCurr.childList.remove(child);
                return;
            }
            else
            {
                child.count--;
                tempCurr = child;
            }
        }
        tempCurr.isEnd = false;
    }

    public static void displayWordsInTrie(TrieNode root, String str)
    {
        TrieNode tempCurr = root;
        if(root.childList==null || root.childList.size()==0)
            return;
        Iterator iter=tempCurr.childList.iterator();
        while(iter.hasNext())
        {
            TrieNode trieNode= (TrieNode) iter.next();
            str+=trieNode.data;
            displayWordsInTrie(trieNode,str);
            if(trieNode.isEnd==true)
            {
                System.out.print(" "+str);
                str=str.substring(0,str.length()-1);
            }
            else
            {
                str=str.substring(0,str.length()-1);
            }
        }

    }
    public static void main(String[] args)
    {
        Trie t = new Trie();
        t.insert("apple");
        t.insert("ape");
        t.insert("goat");
        t.insert("goa");
        t.insert("apt");

        System.out.println("go present in trie : "+t.search("go"));
        System.out.println("goa present in trie : "+t.search("goa"));
        System.out.println("appl present in trie : "+t.search("ape"));
        System.out.println("========================");
        System.out.println("Displaying all word present in trie : ");
        displayWordsInTrie(t.root,"");
    }
}

Output:

go present in trie : false

goa present in trie : true

appl present in trie : true

========================

Displaying all word present in trie :

 apple ape apt goat goa

Implementation
Trie data structure in java
Heap
A min heap is complete binary tree based data structure in which value of root node is less than or equal to value of child nodes.

Implementation
package org.arpit.java2blog.datastructures;

import java.util.Arrays;
public class MinHeap
{
    int Heap[];
    int size;
    int capacity;

    public MinHeap(int size)
    {
        this.capacity = size;
        this.size = 0;
        Heap = new int[size];
    }

    int parent(int i)
    {
        return (i - 1)/2;     //returns the parent node index for ith node
    }

    int leftChild(int i)
    {
        return (2 * i) + 1;              //returns the left child index.
    }

    int rightChild(int i)
    {
        return (2 * i) + 2;              //return the right child index.
    }

    boolean isLeaf(int i)   //checks if ith node is leaf node or not.
    {
        if (rightChild(i) >= size || leftChild(i) >= size)
            return true;

        return false;
    }

    /* Method to insert node in MinHeap

     */
    void insert(int data)
    {
        if (size >= capacity)
            return;

        Heap[size] = data;
        int tempCurr = size;

        while (Heap[tempCurr] < Heap[parent(tempCurr)])
        {
            swap(tempCurr, parent(tempCurr));
            tempCurr = parent(tempCurr);
        }
        size++;
    }

    //removes and returns the minimum element or the root from the heap
    int extractMinimum()
    {
        int min = Heap[0];
        Heap[0] = Heap[--size];
        minHeapify(0);
        System.out.print("\nThe Min Heap after Removing node is :");

        for(int i=0;i Heap[leftChild(i)] || Heap[i] > Heap[rightChild(i)])
            {
                if(Heap[leftChild(i)] < Heap[rightChild(i)])
                {
                    swap(i, leftChild(i));
                    minHeapify(leftChild(i));
                }
                else
                {
                    swap(i, rightChild(i));
                    minHeapify(rightChild(i));
                }

            }
        }

    }

    // builds the min-heap using the minHeapify
    public void minHeap()
    {
        // we call until size/2 cause parent nodes present till that index.
        for (int i = (size-1)/2; i >= 0; i--)
        {
            minHeapify(i);
        }
    }

    //Prints the contents of heap
    public void printHeap()
    {
        for (int i = 0; i < (size / 2); i++)
        {
            if(i==0)
                System.out.print("Root : "+ Heap[i]);
            else
                System.out.print("Parent : " + Heap[i]);

            if (leftChild(i) < size)
                System.out.print(" Left : " + Heap[leftChild(i)]);

            if (rightChild(i) < size)
                System.out.print(" Right : " + Heap[rightChild(i)]);

            System.out.println();
        }
    }

    // swaps two nodes of the heap
    void swap(int x, int y)
    {
        int temp;
        temp = Heap[x];
        Heap[x] = Heap[y];
        Heap[y] = temp;
    }

    //Driver Code to test above methods.
    public static void main(String[] args)
    {

        // Creating a Min heap of capacity 6.
        MinHeap heap = new MinHeap(6);

        heap.insert(100);
        heap.insert(200);
        heap.insert(500);
        heap.insert(700);
        heap.insert(800);
        heap.insert(900);

        // then build the Min Heap
        heap.minHeap();
        System.out.println("The Min Heap is : "+     Arrays.toString(heap.Heap));

        // Get Minimum Operation
        System.out.println("\nThe Min Value in the heap : " + heap.getMinimum());
        System.out.println();

        heap.printHeap();

        // Extract Minimum Operation
        System.out.println("Extracted Minimum Node in the heap : " + heap.extractMinimum());
        System.out.println();

        // Finally print heap to check deleted item.
        heap.printHeap();

    }
}

Output:

The Min Heap is : [100, 200, 500, 700, 800, 900]

The Min Value in the heap : 100
Root : 100 Left : 200 Right : 500

Parent : 200 Left : 700 Right : 800

Parent : 500 Left : 900
The Min Heap after Removing node is :200 700 500 900 800

Extracted Minimum Node in the heap : 100
Root : 200 Left : 700 Right : 500

Parent : 700 Left : 900 Right : 800

Graph

 Graph is a data structure for storing connected data
 It contains group of vertices and edges
 Graph can be of two types: Directed and undirected
 It contains group of vertices and edges
 Graph can be disjoint or connected and there are various algorithms such as depth first search to find this out.


Implementation
package org.arpit.java2blog.datastructures;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class GraphMain
{

    static class Node
    {
        int data;
        boolean visited;
        List neighbours;

        Node(int data)
        {
            this.data=data;
            this.neighbours=new ArrayList<>();

        }
        public void addneighbours(Node neighbourNode)
        {
            this.neighbours.add(neighbourNode);
        }
        public List getNeighbours() {
            return neighbours;
        }
        public void setNeighbours(List neighbours) {
            this.neighbours = neighbours;
        }
    }

    // Recursive DFS
    public  void recursiveDFS(Node node)
    {
        System.out.print(node.data + " ");
        List neighbours=node.getNeighbours();
        node.visited=true;
        for (int i = 0; i < neighbours.size(); i++) {
            Node n=neighbours.get(i);
            if(n!=null && !n.visited)
            {
                recursiveDFS(n);
            }
        }
    }

    // Iterative DFS using stack
    public  void iterativeDFS(Node node)
    {
        Stack stack=new  Stack();
        stack.add(node);
        while (!stack.isEmpty())
        {
            Node element=stack.pop();
            if(!element.visited)
            {
                System.out.print(element.data + " ");
                element.visited=true;
            }

            List neighbours=element.getNeighbours();
            for (int i = 0; i < neighbours.size(); i++) {
                Node n=neighbours.get(i);
                if(n!=null && !n.visited)
                {
                    stack.add(n);
                }
            }
        }
    }

    public static void main(String arg[])
    {

        Node node40 =new Node(40);
        Node node10 =new Node(10);
        Node node20 =new Node(20);
        Node node30 =new Node(30);
        Node node60 =new Node(60);
        Node node50 =new Node(50);
        Node node70 =new Node(70);

        node40.addneighbours(node10);
        node40.addneighbours(node20);
        node10.addneighbours(node30);
        node20.addneighbours(node10);
        node20.addneighbours(node30);
        node20.addneighbours(node60);
        node20.addneighbours(node50);
        node30.addneighbours(node60);
        node60.addneighbours(node70);
        node50.addneighbours(node70);

        GraphMain gm = new GraphMain();

        System.out.println("Iterative DFS traversal ");
        gm.iterativeDFS(node40);

        System.out.println();

        // Resetting the visited flag for nodes
        node40.visited=false;
        node10.visited=false;
        node20.visited=false;
        node30.visited=false;
        node60.visited=false;
        node50.visited=false;
        node70.visited=false;

        System.out.println("Recursive DFS traversal ");
        gm.recursiveDFS(node40);
    }
}

Output:

Iterative DFS traversal

40 20 50 70 60 30 10

Recursive DFS traversal

40 10 30 60 70 20 50

 Inbuild data structures in java
There are lot of good data structures provided by Java language.
Here are few important ones:


        

          import_contacts

        

String

String is most used data structure in java. There are lot of java interview programs on String which can be asked in interview.

How to reverse String in java
How to check if two Strings are angrams
Find length of String without using java inbuilt length method
Find all substrings of String in java
Find First non repeated character in a String
Java Program to check Palindrome String
Why String is immutable in java
Find duplicate characters in String
Longest common prefix in array of Strings


HashMap

 HashMap is used to store key value pairs
 HashMap is neither synchronized nor thread safe.
 HashMap does not allow duplicate keys
 HashMap is unordered collection and does not give guarantee for specific order

package org.arpit.java2blog;

import java.util.HashMap;
public class HashMapMain {

    public static void main(String[] args) {
        HashMap map = new HashMap();
        // Putting key-values pairs in HashMap
        map.put(1, "One");
        map.put(2, "Two");
        map.put(3, "Three");
        map.put(4, "Four");

        System.out.println(map);
    }
}

Output:

{1=One, 3=Three, 2=Two, 4=Four}

LinkedHashMap

 LinkedHashMap implements Map interface and extends HashMap class
 LinkedHashMap maintains insertion order for key value pair
 LinkedHashMap does not allow duplicate keys
 LinkedHashMap uses double linked list to maintain insertion order

package org.arpit.java2blog;

import java.util.HashMap;
public class LinkedHashMapMain {

    public static void main(String[] args) {
        Map map = new LinkedHashMap();
        // Putting key-values pairs in HashMap
        map.put(1, "One");
        map.put(2, "Two");
        map.put(3, "Three");
        map.put(4, "Four");

        System.out.println(map);
    }
}

Output:

{1=One, 2=Two, 3=Three, 4=Four}

ArrayList

 ArrayList is resizable array which can dynamically grow 
 It uses array as internal data structure and increses its size by half when its size is increased
 ArrayList is not synchronized
 ArrayList implements List interface

package org.arpit.java2blog.datastructures;

import java.util.ArrayList;

public class ArrayListMain {
    /*
     * @author : Arpit Mandliya
     */
    public static void main(String[] args) {
        ArrayList list = new ArrayList<>();
        list.add("One");
        list.add("Two");
        list.add("Three");
        list.add("Four");

        System.out.println("ArrayList:");

        for (String str : list) {
            System.out.println(str);
        }
    }
}

Output:

ArrayList:

One

Two

Three

Four

LinkedList

 Java LinkedList class used doubly linked list to store the elements
 LinkedList maintains insertion order
 It is not synchronized
 Manipulation is quite fast in LinkedList as no shifting is required
 LinkedList can be Stack, Queue or LinkedList

import java.util.LinkedList;
import java.util.Iterator;

public class LinkedListMain {
    /*
     * @author : Arpit Mandliya
     */
    public static void main(String[] args) {
        LinkedList list = new LinkedList<>();
        list.add("One");
        list.add("Two");
        list.add("Three");
        list.add("Four");

        System.out.println("LinkedList:");

        Iterator it=list.iterator();  
        while(it.hasNext()){  
            System.out.println(it.next());  
        }  
    }
}

Output:

LinkedList:

One

Two

Three

Four

HashSet

 https://java2blog.com/how-hashset-works-in-java/ implements Set interface and it does not allow duplicate elements
 HashSet does not maintain insertion order
 It is not synchronized and not thread safe

package org.arpit.java2blog.datastructures;

import java.util.HashSet;
import java.util.Iterator;

public class HashSetMain {
    /*
     * @author : Arpit Mandliya
     */
    public static void main(String[] args) {
        HashSet set = new HashSet<>();
        set.add("One");
        set.add("Two");
        set.add("One");
        set.add("Three");
        set.add("Two");

        System.out.println("HashSet:");

        Iterator it=set.iterator();
        while(it.hasNext()){
            System.out.println(it.next());
        }
    }
}

Output:

HashSet:

One

Two

Three

As you can see, duplicate Strings are removed from the HashSet.

That’s all about Data structures in Java.
]]>
					
					https://java2blog.com/data-structures-java/feed/
			0
		
		
			
		
		
		https://java2blog.com/minimum-number-jumps-reach-last-index/?utm_source=rss&utm_medium=rss&utm_campaign=minimum-number-jumps-reach-last-index
					https://java2blog.com/minimum-number-jumps-reach-last-index/#respond
		
		
		Thu, 18 Apr 2019 16:25:04 +0000
				
		
		
		https://java2blog.com/?p=7386

					
										
If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.
In this post, we will see how to find Minimum Number of Jumps to reach last Index.

Problem
Given an array A of positive integers possibly zeroes, every index indicating the maximum length of a jump that can be made from this index. The length of a jump can vary from 1 to A[index].

If value on any index is zero, this means that you can not move forward from this index.

Find the minimum number of jumps required to reach the last index. If the answer is not possible for any case, print “Not Possible”.
Input :

int[] A = { 2, 3, 1, 1, 4 }

Output :

2
Input :

int[] A = { 2, 0, 0, 1, 4 }
Output :

Not Possible

Solution
APPROACH – I :

A basic brute force solution can be achieved by using a recursive approach and making calls to every possible reachable index from the current index.

Now, what does that mean?

We are given the array where each index contains the length of the maximum jumps that can be made from that index.

For eg if A[i] = x, this means that from index ‘i’ we can jump to index  i+0,  i+1,  i+2 … i+x  and obviously only if these indices are in bounds.
Here making a call is equivalent to a jump for which we need to keep a jump variable in the function call and increment it in every recursive call made.
The base case condition will be, when the current index in the function call is eventually the end index. In the base case we compare the number of jumps made to reach this end index with the global minimum variable update it if the current number of jumps made to reach end index is less than the previously global minimum jump and return from the current call. If the current index becomes greater than the last index, then return from the current call as this is not the result we are looking for.

Steps:

Start from index zero and initialize the number of jumps made variable to 0.
Now for every index that is, in every call, start a loop from 1 to value at current index in the given array indicating the lengths of jump to be made in the next call. Make the function call with current index incremented by the length of jump and number of jumps by 1.
When in base case, that is, when the current index in the call is equal to the last index, compare the number of jumps with the global min jumps variable, update it if the number of jumps made in this call is less than the previously global minimum jump and return from the current call.

Here we will be using reactive recursive calls, so when the current index in the call is greater than the last index, we simply return from the call without doing any comparisons.

Time Complexity Discussion:

For an array of length n, at every index ‘i’ we are making A[i] jumps which in the worst case can be equal to n. Hence, there can be a total of ‘n’ potential calls from all the ‘n’ indices, therefore the worst time complexity of this solution is O(n^n).
package Backtracking;

public class minJumpsArr {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] A = { 2, 3, 1, 1, 4 };
        /*current index and number of jumps are zero initially*/
        solve(0, A, 0);

        if(minJumps == (int) 1e9 + 1)
        {
            /*if the min jumps is still infinity, this means it has
             * never been updated that is, we did not reach the end
             * index even once, hence answer is not possible in this
             * case*/
            System.out.println("Not Possible");
        }
        else {
            System.out.println(minJumps);
        }

    }

    /* global min variable to store the minimum number of
     * jumps required to reach last index.*/
    public static int minJumps = (int) 1e9 + 1;

    public static void solve(int currIdx, int[] a, int jumps) {
        /* base case : Case 1 - if current index is equal to last
         * index (destination) update the global min jumps if the
         * current number of jumps is lesser and return. 
         * Case 2 - if current index is greater than the last index,
         * simply return because this is not the result we are looking for*/
        if (currIdx >= a.length - 1) {
            if (currIdx == a.length - 1) {
                minJumps = Math.min(minJumps, jumps);
            }
            return;
        }
        /*maximum length of any jump that can be made from this index*/
        int reachableIdxs = a[currIdx];

        /* recursive calls for all lengths of jump varying from 1 to max
         * length and incrementing number of jumps by 1 in every call */
        for (int jumpLength = 1; jumpLength <= reachableIdxs; jumpLength++) {
            solve(currIdx + jumpLength, a, jumps + 1);
        }
    }
APPROACH 2 :
In the above recursive solution, we can clearly see a lot of redundant calls, therefore for the reduction of the number of calls and eventually for reduced time complexity, we can use Dynamic programming approach.

For any index ‘i’ we can actually store the minimum number of jumps required to reach this index and then from here we can calculate the same for all the reachable indices from this index ‘i’ (‘reachable indices’ term is explained in the previous approach).
Now for any current index, the minimum number of jumps required to reach any ‘reachable index’ from start(‘0’ th index) is minimum jumps required to reach this current ‘i’th index from start(‘0’ th index) + 1 (to reach index ‘i+x’ directly from index ‘i’) , that is,

minJumps[i+x] = minJumps[i] + 1

Where, x can be 1, 2, 3…A[i]
Possibly We will be reaching the same index more than once with different number of jumps, but we want the minimum value, therefore, we update any minJumps[i] only if the current number of jumps required to reach ‘i’ is less then the current value at minJumps[i]

Time Complexity Discussion :

Again in this approach, from any index ‘i’ we are calculating minimum number of jumps of all the reachable indices by visiting all the reachable indices from any index, which can be ‘n’ in a worst case, and we are doing this for all n indices.

Therefore, the time complexity of this algorithm is O(n^2).
import java.util.Arrays;

public class minJumpsArr {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] A = { 2, 0, 1, 1, 4 };

        int ans = solveDP(A);
        if(ans == Integer.MAX_VALUE)
        {
            /* if the min jumps for the last index is still infinity,
             * this means it has never been updated that is, we did
             * not reach the end index even once, hence answer is not
             * possible in this case*/
            System.out.println("Not Possible");
        }
        else {
            System.out.println(ans);
        }

    }

    public static int solveDP(int[] a) {
        int[] minJumps = new int[a.length];
        /*
         * initialize min Jumps for every index to infinity
         * as the minimum value is to  be calculated for
         * every index
         */
        Arrays.fill(minJumps, Integer.MAX_VALUE);
        /* minimum jumps required to reach the very first index is zero */
        minJumps[0] = 0;

        /*calculating min jumps for every index */
        for (int i = 0; i < a.length; i++) {
            /* maximum length of jump from this index or the maximum
             * reachable index from this index*/
            int maxJump = a[i];
            for (int j = 1; j <= maxJump; j++) {
                /*visiting all the reachable index*/
                int reachableIdx = i + j;
                /* updating the minimum jumps required for every reachable
                 * index but only if the reachable index is in bounds and
                 * the intermediate index from which we are making jump to
                 * this reachable index must also be reachable from zeroth
                 * index*/
                if (reachableIdx < a.length && minJumps[i] != Integer.MAX_VALUE) {
                    /* min jumps for every reachable index is min jumps for this
                     * intermediate index 'i' + 1 ( for the jump from intermediate
                     * index to this reachable index) */
                minJumps[reachableIdx] = Math.min(minJumps[reachableIdx], minJumps[i] + 1);
                }
            }
        }
        /*finally return the minimum jumps required to reach last index*/
        return minJumps[a.length-1];
    }
Before moving on to the next approach, just think if we could do better by using a greedy approach and making greedy coices for next index to jump on, rather than exploring all the possibilities using Dynamic programming.
Approach – III :

Yes we can definitely solve the given problem more efficiently by adopting a greedy approach.

The basic strategy would be to keep the track of Maximum reachable index the whole time which will eventually be updated frequently as we move through the given array and as soon as we reach this Maximum reachable index, we increment our number of jumps.
For this, we maintain 2 variables which stores the value of current index and Maximum reachable index. The very first thing we do after reaching any index is update the value of Maximum reachable index by comparing it with current Index + A[current Index] (indicating the maximum length of any jump that can be made from here) and we upadate Maximum reachable index value if value of current Index + A[current Index] is greater than Maximum reachable index. That is,

MaxReachable = max( MaxReachable,  current Index + A[current Index])

One point to reconsider is, What if after the updation of this Maximum reachable index its value is less than or equal to current Index?

Well, this the case where we can not move from this current position and hence we can never reach the end index, therefore, in this case we simply return -1, indicating that no answer is possible in this case.

Now, we need to think about the correctness of our greedy approach again.
Can simply incrementing number of jumps when the value of current index is equal to max reachable index, always yield the correct answer everytime? 
The answer would be a No, as max reachable index is getting updated and incremented by a value of A[current index] every time, this way value of current index can never be equal to max reachable index except for the case when the answer for a case isn’t possible.

For making our approach perfect, we can take another variable which keeps the track of current reachable index, and instead of incrementing the value of jump when current index is equal to Max reachable index, we will increment jump when the current Index becomes equal to current reachable, and at this moment we update the current reachable to max reachable index also.

Time Complexity Discussion :

We visit every index exactly once and keep updating the declared variables as we traverse the given array having ‘n’ elements. Therefore, the worst time complexity of this algorithm is O(n) where n is the size of the given array.
public class minJumpsArr {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] A = { 2, 3, 1, 1, 4 };

        int ans = jump(A);
        if(ans == -1)
        {
            System.out.println("Not Possible");
        }
        else {
            System.out.println("Minimum jumps required : " + ans);
        }

    }

    public static int jump(int[] a) {
        /*three variable as discussed in the editorial*/
        int maxReachable = 0;
        int jumps = 0;
        int currReachable = 0;
        /*exploring every index in the given array */
        for (int currIdx = 0; currIdx < a.length; currIdx++) {

            /*updating max reachable index every time we visit a new index*/
            maxReachable = Math.max(maxReachable, currIdx + a[currIdx]);

            /* as we have already considered the max jump length at this
             * index and if max reachable index is still equal to or
             * less than current index, then we can move forward from
             * this index therefore answer is not possible in this case*/
            if (maxReachable <= currIdx) {
                return -1;
            }

            /*if current index is equal to the current reachable, increment
             * jumps required and update current reachable*/
            if (currIdx == currReachable) {
                jumps++;
                currReachable = maxReachable;
            }
        }
        return jumps;
    }
That’s all about the Minimum Number of Jumps to reach last Index.
]]>
					
					https://java2blog.com/minimum-number-jumps-reach-last-index/feed/
			0
		
		
			
		
		
		https://java2blog.com/sort-array-of-0s-1s-and-2s/?utm_source=rss&utm_medium=rss&utm_campaign=sort-array-of-0s-1s-and-2s
					https://java2blog.com/sort-array-of-0s-1s-and-2s/#comments
		
		
		Thu, 28 Mar 2019 17:52:09 +0000
				
		
		https://java2blog.com/?p=7225

					
										
If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.
In this post, we will see how to sort an array of 0s, 1s and 2s.We have already seen a post on sort 0s and 1s in an array.
Problem
Given an array containing zeroes, ones and twos only. Write a function to sort the given array in O(n) time complexity.
Input :

[1, 2, 2, 0, 0, 1, 2, 2, 1]

Output :

[0, 0, 1, 1, 1, 2, 2, 2, 2]


Solution
APPROACH – I :

A very basic approach to solve this problem can be keeping the count of number of zeroes, ones and twos in the given array and then manipulate the given array in accordance with the frequency of every number. This approach is a bit inspired by counting sort. No matter what the initial value of that particular index is, we first put all the zeroes we have in the array starting from index zero, then put all the ones and after that put all the twos.
Steps:

1.) Traverse the given array once and keep incrementing the count of the number encountered.

2.) Now Traverse the array again starting from index zero and keep changing the value of the element on current index first exhaust all the zeroes then ones and finally all the twos.
This way we have a sorted array where all the zeroes are in starting followed by all the ones and then in last section we have all the twos in a time complexity of O(n).

But the major drawback of this approach is, we have to traverse the given array twice once for counting the number of zeroes, ones and twos and second one for manipulating the array to make it sorted, which can be done only in a single pass.

package Arrays;

    public class sort012 {

    public static void main(String[] args) {

        int[]a = {1,0,2,0,0,1,2,2,1};
        sort(a);
        for(int val : a)
        {
            System.out.println(val + " ");
        }

    }
    /*Function to sort the given array*/
    public static void sort(int[]a)
    {
        /* array to keep the count of 0s, 1s, 2s*/
        int[]freq = new int[3];

        /* traverse the given array for filling the
         * frequency array*/
        for(int val : a)
        {
            freq[val]++;
        }
        /*pointer to traverse the given array again*/
        int pointer = 0;
        for(int i=0;i<freq.length;i++)
        {
            /* loop to exhaust the number of 0s, 1s, 2s*/
            while(freq[i]-->0)
            {
                /*at the current pointer plot the current number*/ 
                a[pointer]=i;
                /*increment the pointer*/
                pointer++;
            }
        }
    }
APPROACH – II :

This algorithm is called as Dutch national flag algorithm or Three way partitioning in which elements of similar type are grouped together and their collective groups are also sorted in a the correct order.

Now we have three types of elements to be sorted, therefore, we divide the given array in four sections out of which 3 sections are designated to zeroes, Ones and twos respectively and one section is unknown or the section which is left to be explored. Now for traversing in these sections we need 3 pointers as well which will virtually divide the given array in four segments.

Let us name these pointers as low, mid and high.
Now we can tell the starting and ending points of these segments.

Segment-1 : zeroes

This will be a known section containing only zeroes with a range of [0, low-1].
Segment-2: Ones

This will also be a know section containing only ones with a range of [low, mid-1].
Segment-3 : Unexplored

This will be an unknown section as the elements in this sections are yet to be explored and hence it can contain all types of element that is, zeroes, ones and twos. Range of this segment will be [mid, high]
Segment-4 : Twos

This will be the last and known area containing only twos having the range of [high+1, N] where N is the length of the given array or basically the last valid index of the given array.

Steps used in this Algorithm to sort the given array in a single pass :
(i) Initialize the low, mid and high pointers to, low = 0, mid = 0, high = N

(ii) Now, run a loop and do the following until the mid pointer finally meets high pointer.As the mid pointer moves forward we keep putting the element at mid pointer to its right position by swapping that element with the element at pointers of respective sections.

(iii) CASE – I : If the element at mid, that is, A[mid] == 0, this means the correct position of this element is in the range [0, low-1], therefore, we swap A[mid] with A[low] and increment low making sure that element with index lesser than low is a Zero.

(iv) CASE – II : If the element at mid, that is, A[mid] == 2, this means the correct position of this element is in the range [hi+1, N], therefore, we swap A[mid] with A[hi] and decrement high making sure that element with index greater than high is a two.

(v) CASE – III : If the element at mid, that is, A[mid]=1, this means that the element is already in its correct segment because [low, mid-1] is the range where it needs to be. Therefore, we do nothing and simply increment the mid pointer.
So, there are total three cases, let us take a moment and emphasise on the fact that mid pointer gets only incremented only when the element A[mid] == 1.

Let us discuss every case individually,
For case – I : In this case we increment mid as well along with increment low pointer, as we are sure that element at low pointer before swapping can surely only be one as had it been a two, it would have already got swapped with high pointer when mid pointer explored it as the only reason that mid pointer left it because it was a one.
For case – II : Now, In this case we swap the element at mid and high, but unlike case – I, in this case we are not sure about the element which will come at mid index after swapping as the element at high index before swapping can be any of zero, one or two, therefore, we need to explore this swapped element and hence we do not increment mid pointer in this case.
For case – III : There is no confusion regarding incrementing mid in this case as already discussed, as we know the element at mid is one therefore we definitely need to increment mid here.
Time complexity of this algorithm is also O(n) but it sorts the array in just a single pass and without any extra space unlike previous approach.
package Arrays;

    public class sort012 {

    public static void main(String[] args) {

        int[]a = {1,2,2,0,0,1,2,2,1};
        sort(a);
        for(int val : a)
        {
            System.out.print(val + " ");
        }

    }

    public static void sort(int[]a)
    {
        /* Three pointers to divide the array in designated segments
         * as discussed in the post*/
        int low=0,mid=0,high=a.length-1;
        while(mid<=high)
        {
            /* Case - 1, when element at mid pointer is zero,
             * swap with element at low*/
            if(a[mid]==0)
            {
                a[low]=swap(a[mid], a[mid]=a[low]);
                /* Increment low as well as mid, as we know
                 * the swapped element at mid is a one*/
                low++;
                mid++;
            }
            /* Case - 1, when element at mid pointer is two,
             * swap with element at high*/
            else if(a[mid]==2)
            {
                /* decrement only high and keep mid unchanged, as
                 * we do not know anything about the swapped element
                 * at mid*/
                a[high]=swap(a[mid],a[mid]=a[high]);
                high--;
            }
            else {
                /*Case - 3, when element at mid pointer is one*/
                /*do nothing, and increment mid pointer*/
                mid++;
            }

        }
    }

    /* utility swap function*/
    public static int swap(int i, int j)
    {
        return i;
    }
}
That’s about sort an array of 0s, 1s and 2s.
]]>
					
					https://java2blog.com/sort-array-of-0s-1s-and-2s/feed/
			4