Lowest Common Ancestor (LCA) Problem

Let T be a rooted tree with n nodes. The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).

The LCA of v and w in T is the shared ancestor of v and w that is located farthest from the root. Computation of lowest common ancestors may be useful, for instance, as part of a procedure for determining the distance between pairs of nodes in a tree: the distance from v to w can be computed as the distance from the root to v, plus the distance from the root to w, minus twice the distance from the root to their lowest common ancestor.

Algorithm:
As we trace the two paths from both nodes up to the root, eventually it will merge into one single path. The LCA is the exact first intersection node where both paths merged into a single path. An easy solution is to use a hash table which records visited nodes as we trace both paths up to the root. Once we reached the first node which is already marked as visited, we immediately return that node as the LCA.

Problem:
Input:
No. of nodes in the binary tree
Preorder traversal of the tree
Inorder traversal of the tree
No. of queries
Node1 Node2
.
.
.


Output:
LCA of Node1 and Node2

Code in C++:




Time complexity: O(nq) (n: no.of nodes, q: no. of queries)

Maximum Subarray Problem

Maximum Subarray Problem:
The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) 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.

Let us solve this problem step-by-step. The naive and simplest brute-force solution would be to consider each index of the array as the start of the subarray and checking if the sum till each of the further indices in the array is maximum. Assuming n to be the size of the array, we will iterate through the array n times to fix the start i of the subarray and for each of these n start indices, we will iterate n-i times through the array for finding the end index of the maximum sum subarray. Hence, the time complexity of the solution will be: O(n^2).

Algorithm: 

def max_subarray(A, n):

    left = right = 0

    max_sum = -INF

    for i = 0 to n:

        sum = 0

        for j = i to n:

            sum = sum + A[i]

            if sum > max_sum:

               max_sum = sum

               left = i

               right = j

    return (left, right, max_sum)

Code in C++:

Algorithm:

def max_subarray(A):
    max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

Code in C++:

 

Time Complexity: O(n)