Find kth smallest value in a sorted matrix
Given a row-wise and column-wise sorted square matrix and a positive integer k, find the kth smallest number in the matrix.
Category: Divide & Conquer
Find `k` closest elements to a given value in an array
Given a sorted integer array, find the k closest elements to x in the array where k and x are given positive integers.
Check if a number is a perfect square
Given a positive number, check if it is a perfect square without using any built-in library function. A perfect square is a number that is the square of an integer.
Segregate positive and negative integers using merge sort
Given an array of positive and negative integers, segregate them without changing the relative order of elements. The output should contain all positive numbers follow negative numbers while maintaining the same relative ordering.
Sort a doubly-linked list using merge sort
Given a doubly linked list, sort it using the merge sort algorithm. Merge sort is an efficient sorting algorithm that uses the divide-and-conquer technique to sort a sequence of items.
Find the square root of a number using a binary search
Given a positive number, find the square root of it. If the number is not a perfect square, then return the floor of its square root.
Unbounded Binary Search
Given a monotonically increasing function f(x) on the non-negative integers, find the value of x, where f(x) becomes positive for the first time. In other words, find a positive integer x such that f(x-1), f(x-2), … are negative and f(x+1), f(x+2), … are positive.
Longest Common Prefix (LCP) Problem
Write an efficient algorithm to find the longest common prefix (LCP) between a given set of strings.
Find the odd occurring element in an array in logarithmic time
Given an array of n integers where every element appears an even number of times except one element, which appears an odd number of times, find that odd occurring element in logarithmic time and constant space.
Find the missing term in a sequence in logarithmic time
Given a sequence of n numbers such that the difference between the consecutive terms is constant, find the missing term in logarithmic time.
Division of two numbers using binary search algorithm
This post will discuss the division of two numbers (integer or decimal) using the binary search algorithm.
Efficiently merge `k` sorted linked lists
In the previous post, we have discussed how to merge two sorted linked lists into one list. This post will merge k sorted linked lists into a single list efficiently.