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 […]
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.
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.
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 […]
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.