How to find the largest subarray with sum 0

How to find the largest subarray with sum 0

subarray with sum 0  

Given an array of integers, find the largest subarray with sum equals to 0. If theres no subarray with sum 0 then print as "No subarray with sum 0".

As solution we are going to iterate the give array from 0th index to nth index and sum each values and finding the subarray.

Solution:

• Iterating from starting to end of the array
• Iterating sub array from 'start' to 'end' pointer and break if sum zero got or sub array smaller than previous sub array with zero 

Lets see simple java code

public class SubArrayZero {

 public static void main(String[] args) {

  int array[] = new int[] { 15, -2, 2, -8, 0, 1, 7, 10, 23 };

  SubArrayZero obj = new SubArrayZero();

  obj.getSubArraySumZero(array);
 }
 
 public void getSubArraySumZero(int[] array) {

  int start = 0, end = 0, sum = 0, fStart = 1, fEnd = -1;

  // Iterating from starting to end of the array
  for (int i = 0; i < array.length; i++) {

   end = i;
   sum += array[i];

   if (sum == 0) {
    if ((fEnd - fStart) < (end - start)) {
     fStart = start;
     fEnd = end;
    }
   } else {
    int tSum = sum;
    
    /* Iterating sub array from 'start' to 'end' pointer and break
    *  if sum zero got or sub array smaller than previous sub array with zero 
    */
    for (int j = start; j < end; j++) {
     tSum -= array[j];
     if (tSum == 0) {
      if ((fEnd - fStart) < (end - (j + 1))) {
       fStart = j + 1;
       fEnd = end;
      }
      break;
     } else if ((fEnd - fStart) > (end - (j + 1)))
      break;
    }
   }
  }
  if(fEnd != -1) {
   System.out.println("Start Index : " + fStart);
   System.out.println("End Index   : " + fEnd);
  }else {
   System.out.println("No subarray with sum 0");
  }
 }
}

OUTPUT:

Start Index : 1
End Index   : 6

How to find integer pairs with given sum

How to find integer pairs with given sum

Pair of given sum  

Given an array of integers, and a number ‘sum’, find the number of pairs of integer in the array whose sum is equal to ‘sum’.

Array can be a combination of +ve, -ve and duplicate elements. Where we need to get the list of all unique pairs from the given array which makes sum is equal to given number. Easy solution with O(N) time complexity will be 

• Iterate each element from array and store it in Set.
• Compare the elements difference from sum as whether present in the Set or not. If present then print the pair with element and sum difference. 
• Remove the difference element from Set to avoid generating duplicate pair. 

Lets see simple Java solution

import java.util.HashSet;

public class PairSum {

 public static void main(String[] args) {

  int[] val = new int[] { 1, 7, 3, 3, 3, 4, 3, -1, 3, 6, 6, 6, 6, 2, 6, 3, 3, 5, 8, 10 };
  PairSum obj = new PairSum();
  obj.getPairs(val, 9);
 }

 public void getPairs(int[] val, int sum) {
  
  HashSet<Integer> set = new HashSet<Integer>();
  int count = 0;
  for (int i : val) {
   if (set.contains(sum - i)) {
    System.out.println("Pair : (" + (sum - i) + ", " + i + ")");
    set.remove(sum - i); // Removing existing value from set to avoid duplicate pair to print
    count++;
   }
   set.add(i);
  }
  
  System.out.println("\nNo. of pairs : "+count);
 }
}

OUTPUT:

Pair : (3, 6)
Pair : (7, 2)
Pair : (6, 3)
Pair : (4, 5)
Pair : (1, 8)
Pair : (-1, 10)

No. of pairs : 6

How to print singly linked list in reverse order

How to print singly linked list in reverse order

Reverse Linked List  

If we talk about Singly Linked List then it will be a 1 way traversal from head node to tail node. But if we need to print the linked list values from tail node to head node (in reverse order) with O(N) time complexity. ???

• Its simple just we need to apply recursive algorithm where we need to start from head node and reach tail which is last node.
• Next print each node values in recursive call. By this way we can achieve printing linked list in recursive order without traversing more than once which is by time complexity O(N) only. 

Lets see simple code to create Singly Linked List and printing same Linked List in reverse order with O(N) complexity.

class NODE {

 int data;
 NODE next;

 public NODE(int data) {
  this.data = data;
  this.next = null;
 }
}

public class PrintLinkedList {

 public static void main(String[] args) {

  PrintLinkedList obj = new PrintLinkedList();
  int val[] = new int[] { 1, 5, 7, 10, 89 };

  NODE head = obj.createLinkedList(val);
  obj.printLLInReverse(head);
 }

 /*
  * Recursive method to print LL in reverse order
  */
 public void printLLInReverse(NODE tmp) {
  if (tmp != null) {
   printLLInReverse(tmp.next);
   System.out.println(tmp.data);
  }
 }

 /*
  * Create linked list based on given array
  */
 public NODE createLinkedList(int val[]) {
  NODE start = null;
  for (int i : val) {
   NODE tmp = new NODE(i);
   if (start == null) {
    start = tmp;
   } else {
    NODE mover = start;
    while (mover.next != null) {
     mover = mover.next;
    }
    mover.next = tmp;
   }
  }
  return start;
 }
}

OUTPUT:

89
10
7
5
1

How to Design a simple LRU cache in Java

How to Design a simple LRU cache in Java

LRU  

Design and implement a data structure for Least Recently Used (LRU) cache by supporting set() and get() operations with O(1) complexity. 

Least Recently Used (LRU) Cache?

Its a caching mechanism where we evicts least recently used items from the cache to accommodate new entries at top. So in that case in cache we maintain only the recently used data and least used entries will be evicted once we need to set new value in cache. 

How to implement simple LRU Cache?

We can implement by using multiple data structure like stack, Queue, LinkedList etc., 
Now in this tutorial lets see how to implement by using Doubly LinkedList and map to hold the LinkedList nodes which makes O(1) complexity for our read / get() operation.

Steps:

• NodeLRU class which holds the data, next and previous node values.
• In LRUCache setting cache size as 5 to make it simple 
• set() method will check already value present in map or not. If its present remove the existing value from map and LinkedList and add the new value in LinkedList and map.
• get() method will fetch node if present in map and return the values or else return -1 if not present. 
• Once we get the value the node will be shifted to the head of LinkedList to make it as recently used. 

By this way we can implement the LRU cache with simple logic by using LinkedList and map. Lets see the java implementation for the same

import java.util.HashMap;
import java.util.Map.Entry;

/*
 * LinkedList node to hold the cached data
 */
class NodeLRU {
 int data;
 NodeLRU next;
 NodeLRU previous;

 public NodeLRU(int data) {
  this.data = data;
  this.next = null;
  this.previous = null;
 }
}

/**
 * Implementing LRU Cache using LinkedList and HashMap to get() value with O(1) 
 * time complexity.
 */
class LRUCache {

 // Total cache size 
 private final static int CACHE_SIZE = 5;

 // Map to hold the cached nodes
 private HashMap<Integer, NodeLRU> map = new HashMap<Integer, NodeLRU>(CACHE_SIZE);
 
 // Doubly LinkedList head and tail node pointer
 private NodeLRU head = null;
 private NodeLRU tail = null;

 /*
  * Set method which will add data into LinkedList
  * and if already key present then remove and ADD as new element.
  */
 public void set(int key, int val) {
  if (map.containsKey(key)) {
   removeExistingNode(key, val);
   set(key, val);
  } else {
   addNode(key, val);
  }
 }

 /*
  * Get method which will return node data if present
  * else returns -1. Once if data node present in map then
  * Fetch the node and place it @ head location. 
  */
 public int get(int key) {
  if (map.containsKey(key)) {
   NodeLRU node = map.get(key);
   makeAsRecentUsed(node);
   return node.data;
  }
  return -1;
 }
 
 /*
  * One if node present via get() method then 
  * pick out the node and stitch with head location as first node.
  * 
  */
 private void makeAsRecentUsed(NodeLRU node) {
  if (node.equals(head)) {
   return;
  } else if (node.equals(tail)) {
   tail.previous.next = null;
   tail = tail.previous;
  } else {
   node.previous.next = node.next;
   node.next.previous = node.previous;
  }
  node.previous = null;
  node.next = head;
  head.previous = node;
  head = node;
 }

 /*
  * Delete the least used node frm LinkedList and map
  */
 private void removeExistingNode(int key, int val) {
  NodeLRU tmp = map.get(key);
  if (tmp.next != null && tmp.previous != null) {
   tmp.previous.next = tmp.next;
   tmp.next.previous = tmp.previous;
  } else if (tmp.equals(tail)) {
   removeLeastUsed();
  } else if (tmp.equals(head)) {
   removeHeadNode();
  }
 }

 /*
  * Removing 1st node
  */
 private void removeHeadNode() {
  NodeLRU firstNode = head;
  tail = tail.next;
  tail.previous = null;
  removeFromMap(firstNode);
 }
 
 /*
  * Adding new node to LinkedList
  */
 private void addNode(int key, int val) {
  if (map.size() < CACHE_SIZE) {
   NodeLRU tmp = new NodeLRU(val);
   if (head == null && tail == null) {
    head = tail = tmp;
   } else {
    head.previous = tmp;
    tmp.next = head;
    head = tmp;
   }
   map.put(key, tmp);
  } else {
   removeLeastUsed();
   addNode(key, val);
  }
 }

 /*
  * Removing least/ last node from LinkedList
  */
 private void removeLeastUsed() {
  NodeLRU leastUsed = tail;
  tail = tail.previous;
  tail.next = null;
  removeFromMap(leastUsed);
 }

 /*
  * Removing from map also based on value node
  */
 private void removeFromMap(NodeLRU node) {
  for (Entry<Integer, NodeLRU> entry : map.entrySet()) {
   if (entry.getValue().equals(node)) {
    map.remove(entry.getKey());
    return;
   }
  }
 }

 /*
  * Method to print all LinkedList nodes data
  */
 public void printValueFromCache() {
  NodeLRU tmp = head;
  System.out.print("CACHE VALUES : ");
  while (tmp != null) {
   System.out.print(tmp.data + ", ");
   tmp = tmp.next;
  }
  System.out.println();
 }

 public static void main(String[] args) {

  LRUCache obj = new LRUCache();
  
  // Adding 1 to 5 values to cache
  obj.set(1, 11);
  obj.set(2, 12);
  obj.set(3, 13);
  obj.set(4, 14);
  obj.set(5, 15);

  obj.printValueFromCache();
  
  /*
   *  Reading value with key (1) which we adding 1st and
   *  placed last in LL. Once we read same value (Node) should 
   *  be placed as recent and moved to top of linked List.
   */
  
  int val = obj.get(1);
  System.out.println("READ VALUE : "+val);

  obj.printValueFromCache();
  
  /*
   * Adding some more values to Cache. Since we set cache size as 5
   * least used 3 nodes like (2,3,4) need to removed and (6,7,8)
   * values need to added to linked list 
   */
  obj.set(6, 66);
  obj.set(7, 77);
  obj.set(8, 88);

  obj.printValueFromCache();
  
  /*
   * Reading again with key (5) which makes node to shift to head
   * which will be recently used
   */
  val = obj.get(5);
  System.out.println("READ VALUE : "+val);

  obj.printValueFromCache();

 }
}

OUTPUT:

CACHE VALUES : 15, 14, 13, 12, 11, 
READ VALUE : 11
CACHE VALUES : 11, 15, 14, 13, 12, 
CACHE VALUES : 88, 77, 66, 11, 15, 
READ VALUE : 15
CACHE VALUES : 15, 88, 77, 66, 11, 

How to get Maximum Subarray Sum in optimal way

How to get Maximum Subarray Sum in optimal way

Maximum sub array  

Given an array with both positive and negative integers and need to find the sum of contiguous subarray of numbers which has the largest sum along with the index values like start and end index from the given array. Also time complexity with O(N)

For example, if the given array is {-2, 5, 4, -3, 6, 9, -1}, then the maximum subarray sum is 21 and array index from 1 to 5 which is  5 + 4 + -3 + 6 + 9 = 21.

Solution:

• Define each 2 variables for sum, start index and for end index. 
• 1st sum and index points will hold each block of sum until its values <= 0. 
• If any negative value comes in iteration then compare the 1st sum with 2nd (which holds the maximum subarray sum) sum and copy if its greater. 
• Iterate until array end and get the maximum subarray sum with the complexity of O(N)

If there are any better solution please post it under below comments section and sharing makes better.

public class SubArray {

 public static void main(String[] args) {

  int array[] = new int[] { -2, 5, 4, -3, 6, 9, -1 };

  SubArray obj = new SubArray();

  obj.getMaximumSumSubArray(array);
 }

 public void getMaximumSumSubArray(int[] array) {

  int start = 0, end = 0, sum = 0, finalSum = 0, fStart = 0, fEnd = 0;

  for (int i = 0; i < array.length; i++) {

   // Avoid initial array with negative
   if (array[i] > 0 && sum == 0) {
    start = end = i;
    sum = array[i];

    // Add current value with sum
   } else if (array[i] > 0) {
    end = i;
    sum += array[i];

   } else {
    // Copy sum to finalSum if sum > finalSum
    if (sum > finalSum) {
     finalSum = sum;
     fStart = start;
     fEnd = end;
    }

    // If sum + current <= 0 then start new sum
    if ((array[i] + sum) <= 0) {
     sum = 0;

    } else {
     sum += array[i];
    }
   }
  }

  // Last compare, sum and finalSum
  if (sum > finalSum) {
   finalSum = sum;
   fStart = start;
   fEnd = end;
  }

  System.out.println("Sum         : " + finalSum);
  System.out.println("Start Index : " + fStart);
  System.out.println("End Index   : " + fEnd);

 }
}

OUPUT:

Sum         : 21
Start Index : 1
End Index   : 5

Simple, how to get only left child in BST

Simple, how to get only left child in BST

Simple  

As same as traversals like inorder, preorder, postorder and level order we need to traverse to BST and need to print only the left child of each nodes in Binary Search Tree.
From below example we need to get only the nodes including root nodlike 11, 6, 4, 17, 31

Solution:

• Place the root node in Queue.
• Iterate Queue until queue becomes empty. 
• Next Enqueue the child nodes left and right nodes inside same queue and print only the left node values. 
• Repeat the process for each leaf node.

class Node {
 Node left, right;
 int data;

 public Node(int data) {
  this.data = data;
 }
}

public class LeftNodes {

 public static void main(String[] args) {

  int a[] = { 4, 5, 3, 8, 7, 6, 100, 9, 3, 2, 1 };

  Node root = null;
  LeftNodes tree = new LeftNodes();

  for (int i = 0; i < a.length; i++) {
   root = tree.insertNode(root, a[i]);
  }
  tree.printLeftNodes(root);
 }

 public void printLeftNodes(Node root) {

  if (root == null)
   return;

  Queue<Node> queue = new LinkedList<Node>();
  queue.add(root);
  System.out.println(root.data);

  while (queue.size() > 0) {
   Node current = queue.poll();
   if (current.left != null) {
    System.out.println(current.left.data);
    queue.add(current.left);
   }
   if (current.right != null) {
    queue.add(current.right);
   }
  }
 }

 public Node insertNode(Node root, int data) {
  Node currentNode = new Node(data);
  if (root == null) {
   root = currentNode;
  } else {
   insertData(currentNode, root);
  }
  return root;
 }

 public Node insertData(Node newNode, Node root) {

  if (root.data < newNode.data) {
   if (root.right == null) {
    root.right = newNode;
   } else {
    return insertData(newNode, root.right);
   }
  } else if (root.data > newNode.data) {
   if (root.left == null) {
    root.left = newNode;
   } else {
    return insertData(newNode, root.left);
   }
  }
  return root;
 }
}

OUTPUT:

4
3
2
1
7
6
9

How to do Level order traversal in Binary Search Tree

How to do Level order traversal in Binary Search Tree

Level order traversal  

We have see lot of tutorials based on Binary tree and also other traversals like Inorder, Preorder and Postorder etc.,

Now in this tutorial lets see how to do Level order traversal of Binary Search Tree using Queue. From the given below tree we need to get output as F, D, J, B, E, G, K, A, C I, H

Solution:

• Place the root node in Queue.
• Iterate Queue until queue becomes empty. Dequeue the first node from Queue and print the value of that node.
• Next Enqueue the child nodes left and right nodes inside same queue. 
• Repeat the process until each leaf node. 

Here in above example first we need to place 'F' node inside queue. Next in loop we need to print 'F' and get the child nodes 'D' and 'J' and enqueue inside same queue. Repeat the process until all leaf nodes and when Queue becomes empty.

class Node {
 Node left, right;
 int data;

 public Node(int data) {
  this.data = data;
 }
}

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

  int a[] = { 11, 6, 19, 4, 8, 5, 43, 49, 10, 31, 17, 5 };

  Node root = null;
  LevelOrderTraversal tree = new LevelOrderTraversal();

  for (int i = 0; i < a.length; i++) {
   root = tree.insertNode(root, a[i]);
  }
  tree.levelOrderTraversal(root);
 }

 public void levelOrderTraversal(Node root) {

  if (root == null)
   return;

  Queue<Node> queue = new LinkedList<Node>();
  queue.add(root);
  System.out.println(root.data);

  while (queue.size() > 0) {
   Node current = queue.poll();
   if (current.left != null) {
    System.out.println(current.left.data);
    queue.add(current.left);
   }
   if (current.right != null) {
    System.out.println(current.right.data);
    queue.add(current.right);
   }
  }
 }

 public Node insertNode(Node root, int data) {
  Node currentNode = new Node(data);
  if (root == null) {
   root = currentNode;
  } else {
   insertData(currentNode, root);
  }
  return root;
 }

 public Node insertData(Node newNode, Node root) {

  if (root.data < newNode.data) {
   if (root.right == null) {
    root.right = newNode;
   } else {
    return insertData(newNode, root.right);
   }
  } else if (root.data > newNode.data) {
   if (root.left == null) {
    root.left = newNode;
   } else {
    return insertData(newNode, root.left);
   }
  }
  return root;
 }
}

OUTPUT:

11
6
19
4
8
17
43
5
10
31
49