Problem: Given an binary array containing only 0s and 1s, find the largest subarray which contain equal no of 0s and 1s. Examples: Input: arr[] = {1, 0, 1, 1, 1, 0, 0,0,1} Output: 1 to 8 (Starting and Ending indexes of output sub array) Implementation: In this method,use two nested loops. The outer loop … Read More →
Find a Number that Appears Only once in array of Duplicates
Problem: Given an array of integers, every element appears twice except for one. Find that single one. Note:Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory. Solution: Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory. Solution: XORing x with itself gives … Read More →
Counting Sort
Counting sort is a linear time sorting algorithm used to sort items when they belong to a fixed and finite set. Integers which lie in a fixed interval, say k1 to k2, are examples of such items. Algorithm: 1. Count for every key j, 1 ≤ j ≤ m how often it occurs in the … Read More →
Sort Elements By Frequency
Problem: You are given an array. You have to sort the array elements in decreasing order of their frequency. eg. [2,3,4,2,8,1,1,2] Output: [2 2 2 1 1 3 4 8] Solution: Method 1 (Use Sorting) 1) Use quick sort algorithm to sort the elements O(nlogn) 2) Scan the sorted array and construct a 2D array … Read More →
Find the Minimum Distance Between Two Numbers
Problem: You are given an array and two elements, find the minimum distance between the elements in the array. The array may have duplicates. For example, if the array is (1, 5, 3, 7, 2, 8, 3, 4, 5, 9, 9, 3, 1, 3, 2, 9) Min Distance (4, 7): 4 Min Distance (9, 3): … Read More →
Find Anagrams in array of Strings
Problem: You are given an array of strings and you have to print all the anagrams within the array. What is anagram – For those who don’t know, two words are anagrams if they contain the same characters. We have already discussed how to check if 2 strings are anagrams here. Solution: Let’s use this … Read More →
Find the Rotation Count in Rotated Sorted array
Problem : Find the count k by which array has been rotated in the rotated sorted array. So for example we have sorted array as 2,3,6,12, 15, 18. Now suppose the array is rotated k times ( we don’t know k), such that array becomes 15, 18,2,3,6,12 We have to find K? Solution : This … Read More →
Find the Minimum Element in the Rotated Sorted array
Problem : Find the minimum element in the rotated sorted array. For example we have array as – 1,3,6,9,12,15. Now suppose the array is rotated k times ( we don’t know k), such that array becomes 12,15,1,3,6,9 Solution – The answer to this lies on the fact that if we can find the point on … Read More →
Find a Pair Whose Sum is Closest to Zero in Array
Problem: This problem is also called minimum absolute sum pair. You are given an array of integers, containing both +ve and -ve numbers. You need to find the two elements such that their sum is closest to zero. eg. Array [15, 5, -20, 30, -45] O/P should be 15, -20 Solution: Searching for two numbers … Read More →
Next Greater Element in array
Problem: You are given an array, print the next greater element for each element. Elements for which no greater element exist, print next greater element as -1. You have to reduce the number of comparisons. For any array, rightmost element always has next greater element as -1. eg. For array [4, 15, 2, 9, 20, … Read More →
Leaders in an array
Problem: You are given an array. You have to write a program that will print all the leaders in the array. An element is leader if it is greater than all the elements to its right side. And the rightmost element is always a leader. For example array {6, 7, 4, 3, 5, 2}, leaders … Read More →
Maximum size square sub-matrix with all 1s
Problem: Given a binary matrix consisting only 0s and 1s, find the maximum size square sub-matrix with all 1s. Example: Consider the below matrix. 0 1 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 The … Read More →
What’s going on ?