Reverse digits of a signed integer - Leet Code Solution
Problem Statement Given a signed integer, reverse digits of an integer. Return…
August 14, 2020
First try to understand question.
You can find the location of these two nodes on the tree. There can be three possibilities:
For Case-2, on finding that both nodes are on the same side. We will repeat our same algorithm going forward in that side only.
Lets see a code for this.
public class CommonAncestor {
public static class Node {
public int data;
public Node left;
public Node right;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
/**
* To check whether a node exists in a root element
*/
private boolean covers(Node root, Node toSearch) {
if (root == null || toSearch == null) {
return false;
}
if (root.data == toSearch.data) {
return true;
}
return this.covers(root.left, toSearch) || this.covers(root.right, toSearch);
}
private Node helper1(Node root, Node node1, Node node2) {
if (root == null) {
return null;
}
if (root.data == node1.data || root.data == node2.data) {
return root;
}
boolean firstNodeFoundOnLeft = this.covers(root.left, node1);
boolean firstNodeFoundOnRight = this.covers(root.left, node2);
if (firstNodeFoundOnLeft != firstNodeFoundOnRight) {
//both are on different sides. Found result.
return root;
}
//both are on the same side.
return this.helper1(firstNodeFoundOnLeft ? root.left : root.right,
node1, node2);
}
public Node findCommonAncestor_1(Node root, Node node1, Node node2) {
if (!this.covers(root, node1) || !this.covers(root, node2)) {
//one or both nodes are not in the tree
System.out.println("Not covered");
return null;
}
return this.helper1(root, node1, node2);
}
}
helper1(root, node1, node2)
The function calls recursively, and same code repeats.
Consider the tree to be balanced tree.
covers()
is called twice. So, its 2 times O(n)
, which computes to O(n)
helper1()
function gets called on branches one time for each node.
2 * n/2 for both nodes.
Which comes out to be: 2n/2 + 2n/4 + 2n/8 ~= O(logn)
Total complexity of this code is O(n)
Problem Statement Given a signed integer, reverse digits of an integer. Return…
Problem Statement Given a string, find the first non-repeating character in it…
Problem Statement Given a string s, find the longest palindromic substring in s…
Problem Statement You are given an n x n 2D matrix representing an image, rotate…
Problem Statement Given n non-negative integers a1, a2, …, an , where each…
In this post, we will see some of the frequently used concepts/vocabulary in…
System design interview is pretty common these days, specially if you are having…
Introduction You are given an array of integers with size N, and a number K…
Graph Topological Sorting This is a well known problem in graph world…
Problem Statement Given a Binary tree, print out nodes in level order traversal…
Problem Statement Given an array nums of n integers and an integer target, are…