Given an array nums of integers, return how many of them contain an even number of digits.
Example 1:
Input: nums = [12,345,2,6,7896]
Output: 2
Example 2:
Input: nums = [555,901,482,1771]
Output: 1
Solution
Loop through Array
Find number of digits in each number
Increase counter by 1 if number of digits in the number is even
/**
* FindNumbersWithEvenNumberOfDigits.java
* Purpose: Find Numbers with Even Number of Digits
*
* @author Megha Rastogi
* @version 1.0 08/09/2020
*/
class FindNumbersWithEvenNumberOfDigits {
/**
* Find Numbers with Even Number of Digits
*
* @param Array, nums
* @return integer, numberOfEvenDigitNumbers
*/
public int findNumbers(int[] nums) {
// initialize the variable to store the count of
// even digit numbers
int numberOfEvenDigitNumbers = 0;
// loop through the array and increase the counter
// if number of digits are even
for(int num: nums){
if(numberOfDigits(num) % 2 == 0)
numberOfEvenDigitNumbers++;
}
//return the result
return numberOfEvenDigitNumbers;
}
/**
* Find number of digits in an integer
*
* @param integer, num
* @return integer, numberOfDigits
*/
public int numberOfDigits(int num){
// initialize the counter to store number of digits
int numberOfDigits = 0;
// loop until number is greater than 0
// Continuously divide num by 10
// increase the numberOfDigits by 1
while(num > 0){
num /= 10;
numberOfDigits++;
}
// return the result
return numberOfDigits;
}
}
Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
Example: Given a binary tree
1
/ \
2 3
/ \
4 5
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
Note: The length of the path between two nodes is represented by the number of edges between them.
Solution
It’s clear that we need to find the length of the longest path between two nodes in a tree. So here those nodes are either 4 and 3 or 5 and 3. Both 5 and 5 are the leaf nodes of the right subtree and 3 is the leaf node of the left subtree. The depth of the tree is the max length from root to leaf. It could be safely said, the max diameter will be the max depth of left subtree and right subtree at any time. For a node root of the tree, we need to do following –
Find the depth of left child
Find the depth of right child
Update global variable diameter with the sum of left and right depth if it is more than depth’s current value.
return depth of the root
Both the time and space complexity will of O(n) where n is the number of nodes in the binary tree.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
/**
* DiameterOfBinaryTree.java
* Purpose: Find the diameter of Binary Tree
*
* @author Megha Rastogi
* @version 1.0 08/03/2020
*/
class DiameterOfBinaryTree {
// ans variable to track diameter
int ans = 0;
/**
* Find the diameter of Binary Tree
*
* @param root, TreeNode
* @return integer, diameter
*/
public int diameterOfBinaryTree(TreeNode root) {
if(root == null)
return 0;
depth(root);
return ans-1;
}
/**
* Helper method to find the diameter of a binary tree
*
* @param root, TreeNode
* @return integer, diameter
*/
public int depth(TreeNode root){
// return 0 when reaching leaf nodes
if(root == null)
return 0;
// left node depth
int left = depth(root.left);
// right node depth
int right = depth(root.right);
// update diameter with the max diameter till now
ans = Math.max(ans, left+right+1);
//return depth till this node
return Math.max(left, right)+1;
}
}
Given an array nums, write a function to move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.
Example:
Input: [0,1,0,3,12]
Output: [1,3,12,0,0]
Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.
Solution
One of the solutions is to create new array of the same size as input array. Add the non zero values to the new array. Add zero to the remaining positions at the last. The time complexity is linear, but the space complexity is O(n), n being the size of array.
But we can do this without using that extra array. We keep track of index. And iterate over the array, updating the index position with the current element if current element is not zero. Then looping to make all elements from index to last zero. This will make the space complexity O(1).
/**
* MoveZerosToEnd.java
* Purpose: Move zeros to end.
*
* @author Megha Rastogi
* @version 1.0 07/13/2020
*/
class MoveZerosToEnd {
/**
* Move zeros to end of array
*
* @param Array, nums
*/
public void moveZeroes(int[] nums) {
// track index to keep track of non zero elements
int index = 0;
// Loop through the array and
// if element is not zero make it the
// indexth element
for(int arr_i = 0; arr_i < nums.length; arr_i++) {
if(nums[arr_i] != 0){
nums[index++] = nums[arr_i];
}
}
// Loop from index to end to make the end elements zero
for(int arr_i = index; arr_i < nums.length; arr_i++){
nums[arr_i] = 0;
}
}
}
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1
Input: [2,2,1]
Output: 1
Example 2
Input: [4,1,2,1,2]
Output: 4
Solution
A simple approach using extra space is to use a HashMap of the integers as keys and counts as value. Then iterate over the HashMap to find the key with value 1. That will give us a time complexity of O(n) and space complexity of O(n), n being the size of the array.
Another more simple approach is to use XOR (bit manipulation). Given two numbers, a and b, as we know an XOR a is 0 and 0 ^ b is b.So we can iterate over the array and keep XORing the elements with one another, similar ones will cancel out and we will get the unique one.
/**
* SingleNumber.java
* Purpose: Find maximum sum contiguous subarray
*
* @author Megha Rastogi
* @version 1.0 07/13/2020
*/
class SingleNumber {
/**
* Find unique number in an array of duplicates
*
* @param Array, nums
* @return integer, ans
*/
public int singleNumber(int[] nums) {
int ans = 0;
// looping through the array and using XOR
// as a ^ a is 0 and 0 ^ b is b
for(int i = 0; i < nums.length; i++){
ans ^= nums[i];
}
return ans;
}
}
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Solution
We need to find the maximum sum contiguous subarray here. Let’s start from the example above. Let’s keep track of sum and maxSum which is a very small number N. And start summing from the beginning –
for -2, sum is -2, maxSum will still become -2.
sum of -2 and 1 will be -1, A thing to note here is our new sum -1 is less than the current value 1. So our sum should become 1 and max between -2 and 1 is 1. Therefore our maxSum is also 1.
sum of 1 and -3 is -2. maxSum between -2, 1 is 1.
sum of -2 and 4 is 2, which is less than 4. so sum becomes 4. and maxSum becomes 4.
And we keep doing this until we reach end.
Our basic algorithm will be
Take two variables sum and maxSum to keep track of sum and maxSum till a given position in array.
Loop through the array
sum is addition of sum and current value in the array. If sum < current value in the array, sum becomes current value in the array.
maxSum is maximum of maxSum and sum.
Repeat above steps until we reach the end of the loop.
return the maxSum
/**
* MaxSubArray.java
* Purpose: Find maximum sum contiguous subarray
*
* @author Megha Rastogi
* @version 1.0 06/06/2020
*/
class MaxSubArray {
/**
* Find maximum sum contiguous subarray
*
* @param Array, nums
* @return integer, maxSum
*/
public int maxSubArray(int[] nums) {
// Initalize maxSum and sum
int maxSum = Integer.MIN_VALUE, sum = 0;
// Loop through the array
for(int i = 0; i < nums.length; i++){
// add current value to sum
sum+=nums[i];
// update sum if it becomes less than current value
if(sum < nums[i])
sum = nums[i];
// update the max sum
maxSum = Math.max(maxSum, sum);
}
//return the max sum
return maxSum;
}
}
In the previous post, we discussed Depth First Search and its implementation in Java. In this post, we learn how to use Breadth First Search to find whether there exists a path between two vertices in a graph.
Again for this post also, we will create a graph for a directed unweighted graph as an adjacency list using the concepts discussed in this previous post. Then apply BFS on it.
How does Breadth First Search (BFS) work?
We have source node and a destination node in a graph. Our motive is to find a path between them. So we call BFS on our source and destination. In DFS, we traverse from node to its child, then to its grandchild and so on. In BFS we go level by level. First, we go through the first node(first layer), then it’s children (second layer) followed by its grandchildren(third layer) and so on until we reach the destination or we have traversed every node.
Here we first add the first node to a queue. Then check whether the first node in our queue is the destination. If yes, it returns true. Else remove the node from the queue. If the node is not in the visited set, add them to the visited set. Then we add the node’s children to our queue. Repeat the above process for every node in queue. If after traversing all nodes we don’t get a path, we return false.
Consider the graph in Fig 4. We have to find whether a path exists between A and H.
First, we check if start is destination ie A is a destination. It is not. So we move on to A’s children B and F and check them sequentially whether they are the destination (Orange Color). They are not, so we traverse B’s children followed by F’s children i.e., C, F (Green Color), and G(Yellow Color). Next we traverse C’s, F’s and G’s children. We continue in this way till we reach our destination node H.
Implementation
Now we code the above concept in Java. I will break down the code into few simple steps for ease in understanding
Step 1: Create a Node class, which stores the Node’s id of primitive type along with a LinkedList/ArrayList to store adjacency list of that node.
Step 2: Create a HashMap/ArrayList to store the vertices of a graph as Node objects. Here we can create a global variable to store graph or locally in methods and then pass them as parameters. Till now, we created a global variable for the graph, for the next two videos we will create a graph in a method and pass it as parameters.
Step 3: Add all the edges into the graph by updating the adjacency list of source nodes.
Step 4: Write method to find whether a path exists between source and destination using BFS.
Now we go through each step in detail:
Step 1:
Create a Node class, which stores the Node id/name/label of primitive type along with a LinkedList/ArrayList to store adjacency list of that node. For a detailed explanation refer to this post.
/**
* Node --- class to store each vertex along with its adjacent vertices
*/
static class Node{
private String id;
private LinkedList<Node> adjacent;
public Node(String id){
this.id = id;
adjacent = new LinkedList<Node>();
}
//Getter method for start vertex
public String getId(){
return id;
}
//Getter method for end vertex
public LinkedList<Node> getAdjacent(){
return adjacent;
}
//add node to the adajcent list
public void addAdjacent(Node vertex){
adjacent.add(vertex);
}
//To print Node
public String toString(){
String msg = id + " : ";
for(Node node: adjacent)
msg = msg + node.id + " ";
return msg;
}
}
Step 2:
Create a HashMap/ArrayList to store the vertices of a graph as Node objects.
In our example graph in Fig 1, we have string nodes. So our HashMap will have keys of type String and Values of type Node.
/**
* Creates a HashMap with string key and Node value
* @param input list of edges
* @return HashMap<String,Node>
*/
public static HashMap<String, Node> createGraph(String[] input){
HashMap<String, Node> graph = new HashMap<String, Node>();
Node node;
for(String s: input){
String first = String.valueOf(s.charAt(0));
String second = String.valueOf(s.charAt(1));
add(graph, first, second);
}
return graph;
}
Step 3:
Add all the edges into the graph by updating the adjacency list of source nodes.
Our input is an array of strings where each string “XY” represents an edge from X to Y. So we traverse our list and do the following three steps on each of the string values.
//Input edges of the graph.
{"AB","AE","BC","BF","CG","CD","EF","FG","GH","DH"};
Part 1: First we separate X and Y from our string “XY”. We can do that by using the String’s charAt(index) method and assign them to a first and second variable. Then add the edge to our graph by calling the add method.
public static void add(HashMap<String, Node> graph, String source, String destination){
//Get nodes corresponding to source and destination vertices.
Node s = getNode(graph, source);
Node d = getNode(graph, destination);
//add nodes to adjacent list
s.addAdjacent(d);
}
Part 2: We access the node corresponding to string X and Y in the graph. If there is no such node in our graph then we create one. This method getNode() does exactly that. It checks whether string K is present in our graph, if yes, then returns the corresponding node, else creates a new node with id K and adds it to our graph with key K.
Part 3: Once we have both the nodes, we can add the destination node to source node’s adjacent list. Now our graph is created.
Step 4:
Write method to find whether a path exists between source and destination.
Here we need to traverse nodes in the order they come in. So we use a LinkedListqueue of type Nodes. We add them as they come and always remove the first one in the list. To keep track of visited nodes, so that we don’t go inside an infinite loop, we use a HashSetvisited.
We start by adding the first node to the queue. Then we loop over this queue until the queue becomes empty. Inside the loop, we remove the first node in the list. Then check whether the node is same as the destination. If yes, we return true. If no, we add the node to visited set if it has not been added. Next, we loop through the node’s adjacent list to add all its children to the queue. If we didn’t find destination even after traversing all nodes, we return false.
public static boolean pathExists(HashMap<String, Node> graph, String source, String destination){
//To store the children of nodes visited
LinkedList<Node> queue = new LinkedList<Node>();
//To store the visited nodes
HashSet<String> visited = new HashSet<String>();
//adding node of startId in the linkedlist
queue.add(getNode(graph, source));
while(!queue.isEmpty()){
Node parent = queue.remove();
//Check if current node is the destination node
if(parent.getId().equals(destination))
return true;
//add source to visited set
if(visited.contains(parent.getId()))
continue;
visited.add(parent.getId());
//add children to the queue
for(Node children: parent.getAdjacent())
queue.add(children);
}
return false;
}
Example
Consider the graph in Fig 1. We will apply the above BFS method on