Close

## Finding the least common ancestor (LCA) in a binary search tree

Given a Binary Search Tree (BST), How do we find the Lowest Common Ancestor (LCA) of the given two nodes? For example in the following BST, the LCA of 5 and 8 is 7 because it is the nearest ancestor common to both the nodes. Let us assume that the LCA(5,7) is 7 itself (…

## Finding the first repeated element in the array

Given an array which contains some duplicate entries, How do we find the element which appears first and is also repeated.For example let us consider the array [10, 78, 45, 39, 22, 45, 78, 61].The element 78 is repeated and it appears before all such repetitive elements. Note that, though two entries of 45 is…

## Given an array, find two values in the array which sum upto a value K

Given an array, and a value K as input, we have to find a pair of elements such that their sum is K. There are multiple ways  of solving this problem. We will discuss some of them in this post. Let us implement the function which prints the two values such that array[i] + array[j]…

## Checking duplicates in an array in O(n) time and O(1) space

Let us consider an array of size N contains numbers in the range [1,N]. We have to find if it has duplicates in linear time – O(n) and by using only constant extra space – O(1). Let us also have a restriction that we should traverse the array only once. Take a look at the following…

## How does binary search work

Given an array of numbers, how do you search for a number? The simplest method is to start at the first element and keep comparing until the end of the array. If it is found anywhere in the middle, return it. Otherwise we would reach the end of the array which indicates that the element in…