Close

## Searching for an element in array of adjacent numbers

Given an array of numbers where the difference between any adjacent numbers is 1, how do we efficiently find a given number? For example consider the array {1, 2, 1, 2, 3, 2, 3, 4, 5, 6}, and we want to search for the number 5. The simplest solution is to check if the number…

## Linear search

Given an array of numbers, how do we search for a given number? For example, given an array [6, 50, 24, 36, 42], the number 36 is present at the index 3 starting with 0. The number 17 is not present any where. The simplest algorithm to solve this problem is to check each element…

## Searching for a word in a grid

Given a two dimensional table of letters, and a word to be searched, design an algorithm to check if it is present in the grid. The word can be formed in any of the 8 possible directions as shown below. Here is how I solved this problem. Write a function which takes the string to…

## Maximum length of subarray with non-zero elements

Given an array of of size N, How do we find the longest sub-array with all non-zero elements? For example consider the array {34, 0, 18, 3, 0, 1, 4, 5, 0, 12}, the longest sub-array with non-zero elements is 3 i.e {1,4,5}. This problem is from Codechef. Follow this link to solve this problem…

## Finding the magic index of the array

Given a sorted array of distinct values, how do you find an index i such that array[i] = i? Let us call it a magic index.For example if the given array is [-23, -4, 2, 19, 56]. Element 2 is found at array. So the output is 2.If there no such element in the array…

## Finding the minimum and maximum elements in a binary seach tree

Given a binary search tree, how do we find the maximum and minimum elements in it? For example in the given tree, the maximum element is 8 and the minimum element is 1. This algorithm is based on the following simple observation. In a Binary search tree, the minimum element always lies on the left…

## Searching for an element in the sorted matrix

Given a row wise and column wise sorted two dimensional array or matrix. How to search for an element efficiently? Example of the array can be int[][] matrix = {                   {1,3,5,7,9},                   {10,12,14,16,18},                   {19,21,23,25,27},                   {28,30,32,34,36},                   {37,39,41,43,45}                }; This can be done using the following algorithm.  We start our search with the top right element.  If it…

## Finding a number in a sorted array with the least difference from given number

Given a sorted array and a value, we have to find the closest value (with least difference). For example let the input array be {-2, 4, 7, 11, 17} and the input number is 10, the output should be 11. This problem is actually a variation of binary search where in we have to find…

## Finding the majority element of an array

Given an array of  N elements, the majority element is defined as the one which occurs more than N/2 times. One simple approach is to find the mode (which appears for most number of times) and check if its frequency is greater than N/2. Three strategies for finding the mode are discussed in my previous…

## Finding the unique number in an array

Given an array of numbers which contains all the numbers in pairs expect one element. We have to find that unique element. For example in the array [7,3,8,1,3,4,7,1,8] 4 is the unique element and all the remaining elements occur in pairs. This is actually a specific case of more generic problem discussed in the my…