Given an array of non negative ints, is it possible to choose a sub array, such that the sum is equal to the given target? Example: Input : arr[] = {2, 4, 8}, target = 12 Output : true.(because 4+ 8 = 12(target sum)) Input : arr[] = {2, 4, 8}, target = 10 Output … Read More →
Maximum difference between two elements
Given an array arr[] of integers, find out the difference between any two elements such that larger element appears after the smaller number in array. Examples: If array is [2, 3, 8, 6, 4, 8, 1] then returned value should be 6 (Diff between 8 and 2). If array is [ 7, 9, 5, 6, … Read More →
Find Majority Element in an array in O(n)
The majority element is the element that occurs more than half of the size of the array. Algorithm below loops through each element and maintains a count of a[maj_index], If next element is same then increments the count, if next element is not same then decrements the count, and if the count reaches 0 then … Read More →
Find local minima in an array
You are given an array Arr[1 .. n] with the special property that Arr[1] ≥ Arr[2] and Arr[n − 1] ≤ Arr[n]. We say that an element Arr[x] is a local minimum if it is less than or equal to both its neighbors. Derive an algorithm in O(log n) For example in the array 9,6,2,14,5,7,4 … Read More →
Even numbers at even index and Odd numbers at odd index
You are given an array of positive numbers. You have to rearrange array such that even numbers at even position and odd numbers at odd positions. If suppose odd numbers exceeds the even numbers or vice-versa than keep them untouched. Do this in one pass and without using any extra memory. input : {2 5 7 … Read More →
Find Union and Intersection of 2 sorted arrays
Union refers to the set of all the elements of the 2 arrays. Intersection here refers to the set of elements which are common in both the arrays. Steps to find union of 2 arrays: 1) i and j, initial values i = 0, j = 0 2) If a1[i] < a2[j] then print a1[i] … Read More →
Find missing number and duplicate number
Given an array of size N containing number from 1 to n,except one number is missing and one number is duplicated.Find Both numbers in linear time. This problem is an extension of our post of finding missing number in an array. Solution : Let missing number be x and duplicate number be y. We know … Read More →
Find the smallest positive number missing from an unsorted array
You are given an unsorted array with both positive and negative elements. You have to find the smallest positive number missing from the array in O(n) time using constant extra space. Example: Input = {2, 3, 4, 6, 8, -1, -3} Output = 1 Input = { 1, 3, -7, 6, 8, 1, -5, 5 … Read More →
Sort an array of 0s,1s,2s
You are given an array of 0s 1s and 2s in random order. Sort the array so the o,1 and 2 are segregated. This problem is similar to Dutch national Flag problem. Method 1: Use count sort logic. Complexity: O(N) Method 2: 1. Sort the array treating {0} as one group and {1, 2} … Read More →
Missing number in an array
You are given an array of n – 1 unique numbers in the range from 0 to n – 1. There is only one number missing in the range from 0 to n – 1 . You need to find the missing number. We know that sum of of numbers from 0 – n-1 is … Read More →
Print a Square Matrix in Spiral Form
Given a N*N square matrix. Write a code to print it in spiral order. Time Complexity : O(N^2)
Find a pair of elements from an array whose sum equals a given number
Given array of n integers and given a number X, find all the unique pairs of elements (a,b), whose summation is equal to X. Algorithm: (1) Sort the array in ascending order. Use quick sort O(n logn), we mentioned in our previous post. (2) Initialize two index variables to find the candidate elements in the … Read More →
What’s going on ?