## First missing integer in an unsorted array

Posted on

Problem statement – Given an unsorted integer array, find the first missing positive integer. Example, If A = [-1, 4, 2, 3, 5], missing integer = 1. If A = [1, 5, 2, 3, 4, 7], missing integer = 6. If A = [-1, -2, -3, -4], missing integer = 1. Clues – Your solution […]

## Maximum sum contiguous sub-array

Posted on

Find a contiguous sub-array whose sum is maximum. Using the dynamic programming based Kadane’s Algorithm, we can solve this in O(N) time.

## Find the majority element in an array

Posted on

Given an unsorted array, find the majority element. Majority element is defined as that element which occurs for more than N/2 times. If the majority element exists, there will only be one such element. We can do this in O(N) time by the Boyer–Moore majority voting algorithm.

## Find pivot element in a sorted and rotated array

Posted on

Problem Statement – Suppose we have a sorted array, and now we rotate it N times, find the pivot element. The pivot element would be the largest element. Also, can you calculate N? Clues – Solution should be O(log N) in time and O(1) in space. Can you think of  a binary search based solution […]

## Kth smallest element in an array

Posted on

Given an unsorted array of N elements, find the kth smallest element. This can be done in O(N) time and O(1) space by the Quickselect Algorithm. The Quickselect Algorithm is a divide-and-conquer based algorithm which rearranges the array such that the kth element is the kth smallest element in the array.