Category: Divide & Conquer

Longest Increasing Subsequence

The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.  

Merge Sort for Singly Linked List

Given a linked list, sort it using merge sort algorithm.     Merge sort is an efficient, general-purpose sorting algorithm which produces a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Mergesort is a comparison sort, i.e. it can sort items of any type for …

Search in a nearly sorted array in O(logn) time

Given a nearly sorted array such that each of the N elements may be misplaced by no more than one position from the correct sorted order, efficiently search a given element in it. Report if the element is not present in the input array.   An element at index i in correct sorted order can …

Find Floor and Ceil of a number in a sorted array

Given a sorted array of integers, find floor and ceil of a given number in it. The floor and ceiling map the given number to the largest previous or the smallest following integer, respectively. More precisely, for a number x, floor(x) is the largest integer less than or equal to x and ceiling(x) is the …