Notes

BINARY SEARCH

Noise In The Library

class Result {
static long Binarysrch(int arr[],int n,int k) {
int l=0;
int r=n-1;
while(l<=r) {
int m=(l+r)/2;
if(arr[m]==k) {
return m;
}
else if(k>arr[m]) {
r=m-1;
}
else {
l=m+1;
}
}
return n;
}
static long totalNoise(int n, int book_IDs[], int k, int booksToFind[]) {
long sum = 0;
for(int i=0;i<k;i++){
int x = booksToFind[i];
sum += Binarysrch(book_IDs,n,x);
}
return sum;
}
}
--------------------------------------------------------------------------------------------------------------------------
Challenges To Find First Occurrence

class Result {
static long firstOcc(int arr[],int n,int k) {
int l = 0;int r = n-1;
long ans = -1;
while(l<=r) {
int m = l + ((r-l)/2);
if(arr[m]==k) {
ans = m;
r = m-1;
}
else if(arr[m] <k) {
l = m+1;
}else {
r = m-1;
}
}
return ans;
}
static long solveChallenges(int n, int arr[], int k, int challenges[]) {
long sum = 0;
for(int i=0;i<k;i++){
int x = challenges[i];
sum += firstOcc(arr,n,x);
}
return sum;
}
}


--------------------------------------------------------------------------------------------------------------------------

Solve Challenges To Win The Game

class Result {
static long firstOcc(int arr[],int n,int k) {
int l = 0;int r = n-1;
long ans = -1;
while(l<=r) {
int m = l + ((r-l)/2);
if(arr[m]==k) {
ans = m;
r = m-1;
}
else if(arr[m] <k) {
l = m+1;
}else {
r = m-1;
}
}
return ans;
}
static long lastOcc(int arr[],int n,int k) {
int l = 0;int r = n-1;
long ans = -1;
while(l<=r) {
int m = l + ((r-l)/2);
if(arr[m]==k) {
ans = m;
l = m+1;
}
else if(arr[m] <k) {
l = m+1;
}else {
r = m-1;
}
}
return ans;
}
static long solveChallenges(int n, int arr[], int k, int challenges[]) {
long sum = 0;
for(int i=0;i<k;i++){
int x = challenges[i];
if(firstOcc(arr,n,x) == -1){
sum+=0;
}
else{
sum += lastOcc(arr,n,x)-firstOcc(arr,n,x)+1;
}
}
return sum;
}
}

--------------------------------------------------------------------------------------------------------------------------
Students standing in a line

class Result {
int studentShifted(int nums[], int n) {
int s = 0;int e = n-1;
int ans = 0;
while(s<=e){
int mid = s+ (e-s)/2;
int next = (mid+1)%n;
int prev = (mid+n-1)%n;
if(nums[mid]<=nums[next] && nums[mid]<=nums[prev]){
ans = n-mid-1;
break;
}
else if(nums[mid]<=nums[s]){
s = mid+1;
}else{
e = mid-1;
}
}
return ans;
}
}
--------------------------------------------------------------------------------------------------------------------------

Integer Square Root

class Result {
static long sqrt(long n) {
long i = 1;
for(i=1;i*i<=n;i++){
}
return i-1;
}
}

--------------------------------------------------------------------------------------------------------------------------

Search element in a rotated sorted array

class Result {
static int binarySearch(int [] arr,int s,int e,int x){
while(s<=e){
int mid = s + (e - s)/2;
if(arr[mid] == x)
return mid;
else if(arr[mid]>=x)
e = mid-1;
else
s = mid + 1;
}
return -1;
}
static int findMin(int[] nums) {
int n = nums.length;
int s = 0;int e = n-1;
if (nums.length == 1) {
return nums[0];
}
while(s<=e){
int mid = s+ (e-s)/2;
int next = (mid+1)%n;
int prev = (mid+n-1)%n;
if(nums[mid]<=nums[next] && nums[mid]<=nums[prev]){
return mid;
}
else if(nums[mid]<=nums[e]){
e = mid - 1;
}else{
s = mid+1;
}
}
return -1;
}
static int searchRotatedSortedArray(int arr[], int x) {
int min_index = findMin(arr);
int n = arr.length;
int i1 = binarySearch(arr, min_index,n-1,x);
int i2 = binarySearch(arr, 0,min_index-1,x);
if(i1==-1){
return i2;
}
return i1;
}
}


--------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------
HASHING

Count frequency of each character

class Result {
static void countFrequency(String str){
HashMap<Character,Integer>mp = new HashMap<>();
for(int i=0;i<str.length();i++){
char c =str.charAt(i);
mp.put(c,mp.getOrDefault(c,0)+1);
}
for(int i=0;i<str.length();i++){
char c =str.charAt(i);
if(mp.get(c)!=0){
System.out.print(c);
System.out.print(mp.get(c)+" ");
mp.put(c,0);
}
}
}
}

--------------------------------------------------------------------------------------------------------------------------
First Unique Character

import java.util.*;
class Result {
static int firstUniqueChar(String str) {
HashMap<Character,Integer>mp = new HashMap<>();
for(int i=0;i<str.length();i++){
char c =str.charAt(i);
mp.put(c,mp.getOrDefault(c,0)+1);
}
for(int i=0;i<str.length();i++){
if(mp.get(str.charAt(i))==1){
return i;
}
}
return -1;
}
}

--------------------------------------------------------------------------------------------------------------------------
Longest Consecutive Subsequence

class Result {
static int LongestConsecutiveSubsequence(int arr[], int n) {
HashSet<Integer> set = new HashSet<Integer>();
int ans = 0;
for (int i = 0; i < n; i++){
set.add(arr[i]);
}
for (int i = 0; i < n; i++){
if (!set.contains(arr[i] - 1)) {
int j = arr[i];
while (set.contains(j)){
j++;
}
ans = Math.max(ans,j-arr[i]);
}
}
return ans;
}
}

--------------------------------------------------------------------------------------------------------------------------
Check if two arrays are equal or not

class Result {
static int arraysEqualorNot(int[] A, int[] B) {
HashMap<Integer, Integer> map = new HashMap<>();
if(A.length!=B.length){
return 0;
}
for(int i=0;i<A.length;i++){
map.put(A[i],map.getOrDefault(A[i],0)+1);
}
for(int i=0;i<B.length;i++){
if(!map.containsKey(B[i])){
return 0;
}else{
map.put(B[i],map.getOrDefault(B[i],0)-1);
if(map.get(B[i])==0){
map.remove(B[i]);
}
}
}
if(map.isEmpty()){
return 1;
}
return 0;
}
}

--------------------------------------------------------------------------------------------------------------------------
Maximum Frequency in a sequence

import java.util.*;
class Main{
static int maxFreq(int arr[],int n){
HashMap<Integer, Integer> map = new HashMap<>();
for(int i=0;i<n;i++){
map.put(arr[i],map.getOrDefault(arr[i],0)+1);
}
int max=0;int maxEle=-1;
for(Map.Entry<Integer,Integer> entry:map.entrySet()){
int key=entry.getKey();
int val=entry.getValue();
if(val>max){
max=val;
maxEle=key;
}
}
return maxEle;
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0){
int n = sc.nextInt();
int []arr = new int[n];
for(int i=0;i<n;i++){
arr[i] = sc.nextInt();
}
System.out.println(maxFreq(arr,n));
}
}
}
--------------------------------------------------------------------------------------------------------------------------
Find all pairs with K difference

class Result {
static int getPairsCount(int arr[], int n, int k) {
HashSet<Integer> set=new HashSet<>();
for(int i=0;i<n;i++){
set.add(arr[i]);
}
int c = 0;
for(int i=0;i<n;i++){
if(set.contains(arr[i]-k)){
c++;
}
}
return c;
}
}
--------------------------------------------------------------------------------------------------------------------------
Insurance Agent with a target

class Result {
static int totalWays(int members[], int n, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0,1);
int res = 0;
int currSum = 0;
for (int i = 0; i < n; i++) {
currSum += members[i];
int removeSum=currSum-target;
if (map.containsKey(removeSum)){
res += map.get(removeSum);
}
map.put(currSum,map.getOrDefault(currSum,0)+1);
}
return res;
}
}
--------------------------------------------------------------------------------------------------------------------------
Find all pairs with sum K

class Result {
static int getPairsCount(int arr[], int n, int k) {
HashMap<Integer,Integer> map=new HashMap<>();
int count=0;
for(int i=0;i<n;i++){
count+=map.getOrDefault(k-arr[i],0);
map.put(arr[i],map.getOrDefault(arr[i],0)+1);
}
return count;
}
}
--------------------------------------------------------------------------------------------------------------------------
Find contiguous sub-array with given sum

class Result {
static void findTheSubArray(int arr[], int n, int target) {
HashMap<Integer,Integer> map = new HashMap<>();
int sum=0;
int start=0;
int end=0;
Boolean flag=false;
for(int i=0;i<n;i++){
map.put(sum,i);
sum+=arr[i];
if(map.containsKey(sum-target)){
start=map.get(sum-target);
end=i;
flag=true;
break;
}
}
if(flag){
System.out.print(start+" "+end);
}
else{
System.out.print(-1);
}
}
}

--------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------
SORTING

Sort an array using quick sort

class Result {
int partition (int arr[], int low, int high) {
int pivot = arr[low];
int i=low;
int j=high;
while(i<=j){
while(i<=j && arr[i]<= pivot){
i++;
}
while(i<=j && arr[j]>=pivot){
j--;
}
if(i<=j){
swap(arr,i,j);
}
}
swap(arr,low,j);
return j;
}
void quickSort(int arr[], int s, int e) {
if(s<e){
int p = partition(arr , s , e);
quickSort(arr , s , p - 1);
quickSort(arr , p + 1 , e);
}
}
static void swap(int arr[],int i,int j){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
--------------------------------------------------------------------------------------------------------------------------
Gifts for everyone with no bias

class Result {
public static int pickMGifts(int m, List<Integer> arr) {
Collections.sort(arr);
int min=Integer.MAX_VALUE;
int n=arr.size();
for(int i=0;i<n;i++){
if((m+i-1)>=n || m==0)
break;
int diff=arr.get(m+i-1)-arr.get(i);
min = Math.min(min,diff);
}
return min;
}
}
--------------------------------------------------------------------------------------------------------------------------
Kth largest number

static int kthLargest(int arr[], int n, int k) {
for(int i=0;i<arr.length-1;i++) {
for(int j=i+1;j<arr.length;j++) { //sorting an array
if(arr[i]>arr[j]) {
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
return arr[n-k-1];
}
--------------------------------------------------------------------------------------------------------------------------
Sort an array using merge sort

import java.util.*;
class Result {
void merge(int arr[], int l, int m, int r) {
int[] left = Arrays.copyOfRange(arr,l,m+1);
int[] right = Arrays.copyOfRange(arr,m+1,r+1);
int i=0,j=0,k=l;
while((i<left.length) && (j<right.length)){
if(left[i]<=right[j]){
arr[k++]=left[i++];
}
else{
arr[k++]=right[j++];
}
}
while(i<left.length){
arr[k++]=left[i++];
}
while(j<right.length){
arr[k++]=right[j++];
}
}
void mergeSort(int arr[], int l, int r) {
if(l<r){
int mid = (l+r)/2;
mergeSort(arr,l,mid);
mergeSort(arr,mid+1,r);
merge(arr,l,mid,r);
}
}
}
--------------------------------------------------------------------------------------------------------------------------
Queries for K largest

class Result {
static long solveQueries(int N, int arr[], int Q, int queries[]) {
long sum=0;
Arrays.sort(arr);
int arr2[]=new int[N];
int j=0;
for(int i=N-1;i>=0;i--){
arr2[j]=arr[i];
j++;
}
for(int i=0;i<Q;i++){
int d=queries[i];
sum=sum+arr2[d-1];
}
return sum;
}
}

--------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------
Priority & heap sort

Implement Priority Queue using Linked List
class PQueueLL
{
public QueueNode front, rear;
public void EnQueue(int data, int priority)
{
QueueNode temp = new QueueNode(data, priority);
if (front==null || temp.priority <= front.priority) {
temp.next = front;
front = temp;
} else {
QueueNode current = front;
while (current.next != null && current.next.priority < temp.priority) {
current = current.next;
}
temp.next = current.next;
current.next = temp;
}
}
public int DeQueue()
{
if (front==null) {
System.out.println("Queue is empty");
return -1;
}
int data = front.data;
front = front.next;
if (front==null) {
rear = null;
}
return data;
}
}
--------------------------------------------------------------------------------------------------------------------------
Sort an array using heap sort

class Result {
static void heapify (int array[], int n, int i) {
int largest = i;
int left = 2*i + 1;
int right = 2*i + 2;
if (left < n && array[left] > array[largest])
largest = left;
if (right < n && array[right] > array[largest])
largest = right;
if (largest != i) {
int swap = array[i];
array[i] = array[largest];
array[largest] = swap;
heapify(array, n, largest);
}
}
static void heapSort(int array[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(array, n, i);
for (int i=n-1; i>=0; i--) {
int temp = array[0];
array[0] = array[i];
array[i] = temp;
heapify(array, i, 0);
}
}
}

--------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------
Binary Tree

Create a binary tree from array

static Node buildTree(int arr[], int n) {
Node root = flor(arr,0,n);
return root;
}
static Node flor(int arr[],int i,int n){
if(i>=n)
return null;
Node temp=new Node(arr[i]);
temp.leftChild=flor(arr,2*i+1,n);
temp.rightChild=flor(arr,2*i+2,n);
return temp;
}
--------------------------------------------------------------------------------------------------------------------------
Print binary tree with level order traversal

static void printLevelWise(Node root) {
if(root==null){
return;
}
Queue<Node> q = new LinkedList<Node>();
q.offer(root);
while(!q.isEmpty()) {
int size = q.size();
for(int i=0;i<size;i++){
Node temp=q.poll();
System.out.print(temp.data);
if (i < size - 1) {
System.out.print(" ");
}
if(temp.left!=null) {
q.offer(temp.left);
}
if(temp.right!=null) {
q.offer(temp.right);
}
}
System.out.println();
}
}
--------------------------------------------------------------------------------------------------------------------------
Print nodes at odd levels of the binary tree
class Result {
static void printOdd(Node root) {
if (root == null) return;
Queue<Node> q = new LinkedList<>();
q.offer(root);
int level = 1;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
Node temp = q.poll();
if (level % 2 != 0) {
System.out.print(temp.data + " ");
}
if (temp.left != null) {
q.offer(temp.left);
}
if (temp.right != null) {
q.offer(temp.right);
}
}
level++;
}
}
}
--------------------------------------------------------------------------------------------------------------------------
Write iterative version of inorder traversal

static void printInorder(Node root){
if(root == null){
return;
}
Stack<Node> st = new Stack<Node>();
Node current = root;
while(current != null || !st.isEmpty()){
while(current != null){
st.push(current);
current = current.leftChild;
}
current = st.pop();
System.out.print(current.data + " ");
current = current.rightChild;
}
}
--------------------------------------------------------------------------------------------------------------------------
Complete the inorder(), preorder() and postorder() functions for traversal with recursion

static void inorder(Node root){
if(root==null){
return;
}
inorder(root.leftChild);
System.out.print(root.data+" ");
inorder(root.rightChild);
}
static void preorder(Node root){
if(root==null){
return;
}
System.out.print(root.data+" ");
preorder(root.leftChild);
preorder(root.rightChild);
}
static void postorder(Node root){
if(root==null){
return;
}
postorder(root.leftChild);
postorder(root.rightChild);
System.out.print(root.data+" ");
}
--------------------------------------------------------------------------------------------------------------------------
Construct tree from given inorder and post order traversal

class Result {
static int postIndex;
static Node buildTree(int in[], int post[], int N) {
postIndex = N - 1;
return buildTreeUtil(in, post, 0, N - 1);
}
static Node buildTreeUtil(int in[], int post[], int inStart, int inEnd) {
if (inStart > inEnd) {
return null;
}
Node root = new Node(post[postIndex--]);
if (inStart == inEnd) {
return root;
}
int inIndex;
for (inIndex = inStart; inIndex <= inEnd; inIndex++) {
if (in[inIndex] == root.data) {
break;
}
}
root.rightChild = buildTreeUtil(in, post, inIndex + 1, inEnd);
root.leftChild = buildTreeUtil(in, post, inStart, inIndex - 1);
return root;
}
}
--------------------------------------------------------------------------------------------------------------------------
Count the number of leaf and non-leaf nodes in a binary tree

class Result {
static int countLeafs(Node root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
return countLeafs(root.left) + countLeafs(root.right);
}

static int countNonLeafs(Node root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 0;
}
return 1 + countNonLeafs(root.left) + countNonLeafs(root.right);
}
}
--------------------------------------------------------------------------------------------------------------------------
Print all paths to leaves and their details of a binary tree

static int pathCount = 0;
static void printAllPaths(Node root) {
if (root == null) {
return;
}
List<Integer> path = new ArrayList<>();
printAllPathsUtil(root, path);
System.out.println(pathCount);
}
static void printAllPathsUtil(Node node, List<Integer> path) {
if (node == null) {
return;
}
path.add(node.data);
if (node.left == null && node.right == null) {
String pathString = "";
for (Integer i : path) {
pathString += i + " ";
}
pathString += path.size()-1;
System.out.println(pathString);
pathCount++;
} else {
printAllPathsUtil(node.left, path);
printAllPathsUtil(node.right, path);
}
path.remove(path.size() - 1);
}
--------------------------------------------------------------------------------------------------------------------------
Find the right node of a given node

class Result {
static int findRightSibling(Node root, int key) {
if (root == null) return -1;

Queue<Node> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
Node current = q.poll();
if (current.data == key) {
if (i < size - 1) {
Node rightSibling = q.peek();
return rightSibling.data;
} else {
return -1;
}
}
if (current.left != null) {
q.offer(current.left);
}
if (current.right != null) {
q.offer(current.right);
}
}
}
return -1;
}
}
--------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------
BINARY SEARCH TREE

Given binary tree is binary search tree or not

class Result {
static int isBinarySearchTree(Node root) {
if(isBSTUtil(root, Integer.MIN_VALUE, Integer.MAX_VALUE)){
return 1;
}
return 0;
}

static boolean isBSTUtil(Node node, int min, int max) {
if (node == null) {
return true;
}
if (node.data < min || node.data > max) {
return false;
}
return (isBSTUtil(node.left, min, node.data - 1) &&
isBSTUtil(node.right, node.data + 1, max));
}
}
--------------------------------------------------------------------------------------------------------------------------
Find the kth smallest element in the binary search tree

static int kSmallest(Node root, int k) {
if(root==null) return 0;
Stack<Node> st = new Stack<>();
Node temp = root;
int count = 0;
while (temp != null || !st.isEmpty()) {
while (temp != null) {
st.push(temp);
temp = temp.left;
}
temp = st.pop();
count++;
if (count == k) {
return temp.data;
}
temp = temp.right;
}
return -1;
}
--------------------------------------------------------------------------------------------------------------------------
Convert Level Order Traversal to BST

import java.util.*;
class Result {
static Node buildSearchTree(int[] t, int n) {
if (n <= 0) {
return null;
}
Node root = new Node(t[0]);
Queue<Node> q = new LinkedList<>();
q.offer(root);
int i = 1;
while (i < n) {
Node temp = q.poll();
Node leftChild = new Node(t[i]);
temp.leftChild = leftChild;
q.offer(leftChild);
i++;
if (i < n) {
Node rightChild = new Node(t[i]);
temp.rightChild = rightChild;
q.offer(rightChild);
i++;
}
}
return root;
}
}