MEDIAN OF SORTED ARRAYS
QUICKSORT ALGO BASED PROBLEMS
K’th Smallest/Largest Element in Unsorted Array | Set 1
Given an array and a number k where k is smaller than size of array, we need to find the k’th smallest element in the given array. It is given that ll array elements are distinct.
Examples:
Input: arr[] = {7, 10, 4, 3, 20, 15}
k = 3
Output: 7
Input: arr[] = {7, 10, 4, 3, 20, 15}
k = 4
Output: 10
k largest(or smallest) elements in an array | added Min Heap method
Question: Write an efficient program for printing k largest elements in an array. Elements in array can be in any order.
For example, if given array is [1, 23, 12, 9, 30, 2, 50] and you are asked for the largest 3 elements i.e., k = 3 then your program should print 50, 30 and 23.
ROTATED N SORTED ARRAY PROBLEMS
CONCEPT : No of rotations = index of minimum element.
Search an element in a sorted and rotated array
An element in a sorted array can be found in O(log n) time via binary search. But suppose we rotate an ascending order sorted array at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Devise a way to find an element in the rotated array in O(log n) time.
Input : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3};
key = 3
Output : Found at index 8
Input : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3};
key = 30
Output : Not found
Input : arr[] = {30, 40, 50, 10, 20}
key = 10
Output : Found at index 3
An element in a sorted array can be found in O(log n) time via binary search. But suppose we rotate an ascending order sorted array at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Devise a way to find an element in the rotated array in O(log n) time.
Input : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3};
key = 3
Output : Found at index 8
Input : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3};
key = 30
Output : Not found
Input : arr[] = {30, 40, 50, 10, 20}
key = 10
Output : Found at index 3
Search An Element in sorted an rotated array
Find the Rotation Count in Rotated Sorted array
Consider an array of distinct numbers sorted in increasing order. The array has been rotated (anti-clockwise) k number of times. Given such an array, find the value of k.
Examples:
Input : arr[] = {15, 18, 2, 3, 6, 12}
Output: 2
Explanation : Initial array must be {2, 3,
6, 12, 15. 18}. We get the given array after
rotating the initial array twice.
Input : arr[] = {7, 9, 11, 12, 5}
Output: 4
Input: arr[] = {7, 9, 11, 12, 15};
Output: 0
Sort a Rotated Sorted Array
You are given a rotated sorted array and your aim is to restore its original sort in place.
Expected to use O(1) extra space and O(n) time complexity.
Examples:
Examples:
Input : [3, 4, 1, 2] Output : [1, 2, 3, 4] Input : [2, 3, 4, 1] Output : [1, 2, 3, 4]
SORTED ARRAY PROBLEMS
Median of two sorted arrays of same size
There are 2 sorted arrays A and B of size n each. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). The complexity should be O(log(n)).
There are 2 sorted arrays A and B of size n each. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). The complexity should be O(log(n)).
Sort elements by frequency | Set 1
Print the elements of an array in the decreasing frequency if 2 numbers have same frequency then print the one which came first.
Examples:
Examples:
Input: arr[] = {2, 5, 2, 8, 5, 6, 8, 8}
Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6}
Input: arr[] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8}
Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6, -1, 9999999}
Solution :
1)Store them in TreeMap with count
2) Map<Integer, Integer>rm = map.descendingMap();
3)Iterate over map & store element in new array as per frequency
-
-
Find minimum number of merge operations to make an array palindrome
Given an array of positive integers. We need to make the given array a ‘Palindrome’. Only allowed operation on array is merge. Merging two adjacent elements means replacing them with their sum. The task is to find minimum number of merge operations required to make given array a ‘Palindrome’.
To make an array a palindromic we can simply apply merging operations n-1 times where n is the size of array (Note a single element array is alway palindrome similar to single character string). In that case, size of array will be reduced to 1. But in this problem we are asked to do it in minimum number of operations.
Example:
Input : arr[] = {15, 4, 15}
Output : 0
Array is already a palindrome. So we
do not need any merge operation.
Input : arr[] = {1, 4, 5, 1}
Output : 1
We can make given array palindrome with
minimum one merging (merging 4 and 5 to
make 9)
Input : arr[] = {11, 14, 15, 99}
Output : 3
We need to merge all elements to make
a palindrome.
Expected time complexity is O(n).
Given an array of positive integers. We need to make the given array a ‘Palindrome’. Only allowed operation on array is merge. Merging two adjacent elements means replacing them with their sum. The task is to find minimum number of merge operations required to make given array a ‘Palindrome’.
To make an array a palindromic we can simply apply merging operations n-1 times where n is the size of array (Note a single element array is alway palindrome similar to single character string). In that case, size of array will be reduced to 1. But in this problem we are asked to do it in minimum number of operations.
Example:
Input : arr[] = {15, 4, 15}
Output : 0
Array is already a palindrome. So we
do not need any merge operation.
Input : arr[] = {1, 4, 5, 1}
Output : 1
We can make given array palindrome with
minimum one merging (merging 4 and 5 to
make 9)
Input : arr[] = {11, 14, 15, 99}
Output : 3
We need to merge all elements to make
a palindrome.
Expected time complexity is O(n).
Maximum Length Bitonic Subarray | Set 1 (O(n) tine and O(n) space)
Given an array A[0 … n-1] containing n positive integers, a subarray A[i … j] is bitonic if there is a k with i <= k <= j such that A[i] <= A[i + 1] ... <= A[k] >= A[k + 1] >= .. A[j – 1] > = A[j].Write a function that takes an array as argument and returns the length of the maximum length bitonic subarray.
Expected time complexity of the solution is O(n)
Simple Examples
1) A[] = {12, 4, 78, 90, 45, 23}, the maximum length bitonic subarray is {4, 78, 90, 45, 23} which is of length 5.
2) A[] = {20, 4, 1, 2, 3, 4, 2, 10}, the maximum length bitonic subarray is {1, 2, 3, 4, 2} which is of length 5.
Extreme Examples
1) A[] = {10}, the single element is bitnoic, so output is 1.
2) A[] = {10, 20, 30, 40}, the complete array itself is bitonic, so output is 4.
3) A[] = {40, 30, 20, 10}, the complete array itself is bitonic, so output is 4.
Given an array A[0 … n-1] containing n positive integers, a subarray A[i … j] is bitonic if there is a k with i <= k <= j such that A[i] <= A[i + 1] ... <= A[k] >= A[k + 1] >= .. A[j – 1] > = A[j].Write a function that takes an array as argument and returns the length of the maximum length bitonic subarray.
Expected time complexity of the solution is O(n)
Expected time complexity of the solution is O(n)
Simple Examples
1) A[] = {12, 4, 78, 90, 45, 23}, the maximum length bitonic subarray is {4, 78, 90, 45, 23} which is of length 5.
1) A[] = {12, 4, 78, 90, 45, 23}, the maximum length bitonic subarray is {4, 78, 90, 45, 23} which is of length 5.
2) A[] = {20, 4, 1, 2, 3, 4, 2, 10}, the maximum length bitonic subarray is {1, 2, 3, 4, 2} which is of length 5.
Extreme Examples
1) A[] = {10}, the single element is bitnoic, so output is 1.
1) A[] = {10}, the single element is bitnoic, so output is 1.
2) A[] = {10, 20, 30, 40}, the complete array itself is bitonic, so output is 4.
3) A[] = {40, 30, 20, 10}, the complete array itself is bitonic, so output is 4.
Find the Sub-array with sum closest to 0
3.2
Given an array of both positive and negative numbers, the task is to find out the subarray whose sum is closest to 0.
There can be multiple such subarrays, we need to output just 1 of them.
Examples:
Input : arr[] = {-1, 3, 2, -5, 4}
Output : 1, 3
Subarray from index 1 to 3 has sum closest to 0 i.e.
3 + 2 + -5 = 0
Input : {2, -5, 4, -6, 3}
Output : 0, 2
2 + -5 + 4 = 1 closest to 0
Asked in : Microsoft
3.2
Given an array of both positive and negative numbers, the task is to find out the subarray whose sum is closest to 0.
There can be multiple such subarrays, we need to output just 1 of them.
Examples:
There can be multiple such subarrays, we need to output just 1 of them.
Examples:
Input : arr[] = {-1, 3, 2, -5, 4}
Output : 1, 3
Subarray from index 1 to 3 has sum closest to 0 i.e.
3 + 2 + -5 = 0
Input : {2, -5, 4, -6, 3}
Output : 0, 2
2 + -5 + 4 = 1 closest to 0
Asked in : Microsoft
Find lost element from a duplicated array
Given two arrays which are duplicates of each other except one element, that is one element from one of the array is missing, we need to find that missing element.
Examples:
Input: arr1[] = {1, 4, 5, 7, 9}
arr2[] = {4, 5, 7, 9}
Output: 1
1 is missing from second array.
Input: arr1[] = {2, 3, 4, 5}
arr2[] = {2, 3, 4, 5, 6}
Output: 6
6 is missing from first array.
Given two arrays which are duplicates of each other except one element, that is one element from one of the array is missing, we need to find that missing element.
Examples:
Input: arr1[] = {1, 4, 5, 7, 9}
arr2[] = {4, 5, 7, 9}
Output: 1
1 is missing from second array.
Input: arr1[] = {2, 3, 4, 5}
arr2[] = {2, 3, 4, 5, 6}
Output: 6
6 is missing from first array.
Find duplicates
eg. {1,2,3,1,6,6} o/p 1,3,6
Solution :
1) Try to add values to HashSet ,if doesn't add, print the number
Solution :
1) Try to add values to HashSet ,if doesn't add, print the number
While loop increment i, j, k problems
Union of arrays
Common Elements in Three arrays
-
-
Median Of Sorted Arrays
-
-
-
-
Median Of Sorted Arrays
-
-
Intersection of Arrays
Fixed Point in Arrays
FloorCeilSearch
Binary Search based problems
Search
Given an integer array and an element x, find if element is present in array or not. If element is present, then print index of its first occurrence. Else print -1.
Sorted N Rotated Array Problems
Find the maximum element in an array which is first increasing and then decreasing
Search an element in an unsorted array using minimum number of comparisons
Search an element in sorted and rotated Array
Find the maximum element in an array which is first increasing and then decreasing
Solution : Find the pivot elements index ,an element before pivot will be the one
Pair Sum /Pair Product problems
Given an unsorted Array find the pair of elements in that generate the largest product or largest sum
public static void maxELement_3(int[] num1) { int[] num = {4,3,5,7,2,5,67,32,89,45,76,90,9}; Integer maxE[] = {0,0}; Arrays.stream(num).forEach(x->{ if(x>maxE[0]){ maxE[1] = maxE[0]; maxE[0] = x; }else if(x>maxE[1]){ maxE[1]= x; } }); System.out.println("max element is "+maxE[0]+"second max element is"+maxE[1]); }
Find a pair with the given difference
Given an unsorted array and a number n, find if there exists a pair of elements in the array whose difference is n.
Examples:
Input: arr[] = {5, 20, 3, 2, 50, 80}, n = 78
Output: Pair Found: (2, 80)
Input: arr[] = {90, 70, 20, 80, 50}, n = 45
Output: No Such Pair
Solution :
1)Store array in hashmap & while trying to store , ,each time validate if
-
-
Traversing array from left side/ride problems
Minimum Distance in An Array
/*
*
* Step1 : Find the first element in array & store its index,
say firstIndex
*
* Step2 : Iterate the array beyond that point ,
* case1 : if first or second element is found
*
* 1 a) find out if it is equal to array[FirstIndex]
* if true , store the new index in firstIndex
* b) If false ,
* i)Calculate currentIndex-firstIndex< min_Dist
* if true
* min_dist = currentIndex-firstIndex
* 2)return min_dist
*
* */
-
-
/**
* An element is Leader if it is greater than All the elements to its right
*
* Scan all elements fronm right to left in array and keep track of
* maximum till now. When maximum changes it's value ,print it
*
* */
-
-
Greatest Element on Right Side
-
-
First Repeating Element
-
-
Moving zeros problems
Moving zeros to end
We are skipping the array assignment when arr[fast ] = 0, when it is arr[fast ] != 0, we are assigning values to array slow & later assigning zero to all elements beyond slow ....
We are skipping the array assignment when arr[fast ] = 0, when it is arr[fast ] != 0, we are assigning values to array slow & later assigning zero to all elements beyond slow ....
Preview:
public static void moveZerosToEnd(int arr[]){ int slow =0; int fast =0; while(fast < arr.length){ if(arr[fast] == 0){ fast++; continue; } arr[slow] = arr[fast]; slow++; fast++; } while(slow < arr.length){ arr[slow++] = 0; } }
Dutch National Flag Problem /Segregate 0's & 1's
-
-
Binary Search
Minimum/Maximum Difference Problems
Two elements whose sum is closest to zero
Question: An Array of integers is given, both +ve and -ve. You need to find the two elements such that their sum is closest to zero.
For the below array, program should print -80 and 85.
Solution:
1) Sort the Array nlogn
2) Calculate difference between adjacent elements & compare with min_difference
3) if min_difference is greater than current difference , store current diffrence in min_difference
4)return min difference
Question: An Array of integers is given, both +ve and -ve. You need to find the two elements such that their sum is closest to zero.
For the below array, program should print -80 and 85.
Solution:
1) Sort the Array nlogn
2) Calculate difference between adjacent elements & compare with min_difference
3) if min_difference is greater than current difference , store current diffrence in min_difference
4)return min difference
Solution:
1) Sort the Array nlogn
2) Calculate difference between adjacent elements & compare with min_difference
3) if min_difference is greater than current difference , store current diffrence in min_difference
4)return min difference
Find minimum difference between any pair in given array
eg. {1,5,3,19,18,25} o/p = 1
Minimum difference is between 18 and 19
Input: {30,5,20,9}
o/p : 4
Minimum difference is between 5 and 9
Solution
1) Sort the Array & calculate the difference between adjacent pair ...
2) Calculate difference between adjacent pairs & compare it with min_diff ,if it less than the difference found so far ,store it
3)
1) Sort the Array & calculate the difference between adjacent pair ...
2) Calculate difference between adjacent pairs & compare it with min_diff ,if it less than the difference found so far ,store it
3)
-
-
Maximum difference between two elements such that larger element appears after the smaller number
Given an array arr[] of integers, find out the difference between any two elements such that larger element appears after the smaller number in arr[].
Examples: If array is [2, 3, 10, 6, 4, 8, 1] then returned value should be 8 (Diff between 10 and 2). If array is [ 7, 9, 5, 6, 3, 2 ] then returned value should be 2 (Diff between 7 and 9)
or
Single Stock Problem
Say you have an
array for which the ith element is the price of a given stock on day i, you can
buy stock at any day, but can only buy once a day, but if you sell the stock,
you must sell all of them at once.
Seeking maximum
profit
Preview:
public int oneProfit(int arr[]){ int minPrice = arr[0]; int maxProfit = 0; for(int i=1; i < arr.length; i++){ if(arr[i] - minPrice > maxProfit){ maxProfit = arr[i] - minPrice; } if(arr[i] < minPrice){ minPrice = arr[i]; } } return maxProfit; }
3) Maximum gap between consecutive elements
public static void maxGap() { int[] input = {4, 3, 13, 2, 9, 7}; Arrays.sort(input); int min = Integer.MAX_VALUE; int diff =0; for(int i=1;i;i++){ diff = input[i]-input[i-1]; if(min>diff) min = diff; } System.out.println(" "+diff); }
4) Maximum repeating elements
public static void maxRepeatingELement() {
int arr[] = {2,2,1,3,1,2,0,3,0,0,0,4,5,4,4,4,4};
TreeMap frequencyMap = new TreeMap();
for(int i=0;iarr.length/2) {
System.out.println("no is"+arr[i]);
break;
}
frequencyMap.put(arr[i], count+1);
}else{
frequencyMap.put(arr[i],1);
}
}
int maxNum = Integer.MIN_VALUE;
int maxCount = Integer.MIN_VALUE;
for(Map.Entry entry : frequencyMap.entrySet()){
if(maxCount Write a program to reverse an array/string using while loop.
7)Majority Element
8) First Non Repeating element
8) First Non Repeating element
public class NonRepeatingELement {
public static void findUsingXOR(int [] a){
if(a.length==0)
return;
int xor = a[0];
for (int i = 1; i
9) Median of two sorted Arrays
10) Peak element
11) Local Minima
Check if elements are consecutive
public class CheckIfArrayElementsAreConsecutive { public boolean areConsecutive(int input[]){ int min = Integer.MAX_VALUE; for(int i=0; i < input.length; i++){ if(input[i] < min){ min = input[i]; } } for(int i=0; i < input.length; i++){ if(Math.abs(input[i]) - min >= input.length){ return false; } if(input[Math.abs(input[i]) - min] < 0){ return false; } input[Math.abs(input[i]) - min] = -input[Math.abs(input[i]) - min]; } for(int i=0; i < input.length ; i++){ input[i] = Math.abs(input[i]); } return true; }
Sum Problems :
Find a triplet that sum to a given value
Given an array and a value, find if there is a triplet in array whose sum is equal to the given value. If there is such a triplet present in array, then print the triplet and return true. Else return false. For example, if the given array is {12, 3, 4, 1, 6, 9} and given sum is 24, then there is a triplet (12, 3 and 9) present in array whose sum is 24.
14) Four Sum
15) First Positive Number
16) Repeating & missing Value
Preview:
package com.vidushi.takshila.Arrays; public class MaximumSubArray { //Kadane's Algorithm /* * int [] A = {−2, 1, −3, 4, −1, 2, 1, −5, 4}; Output: contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6. * */ public static void main(String args[]){ //int arrA[] = {1,2,-3,-4,2,7,-2,3}; int arrA[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; System.out.println(" "+kadane(arrA)); } public static int kadane(int[] arrA){ int max_end_here = 0; int max_so_far =0; for(int i=0;ilength;i++){ max_end_here = max_end_here + arrA[i]; if(max_end_here < 0 ) max_end_here = 0; if(max_so_far return max_so_far; } }
18) Convert an unsorted array into an array such that ac
Preview:
public void convert1(int arr[]){ Arrays.sort(arr); for(int i=1; i < arr.length; i+=2){ if(i+1 < arr.length){ swap(arr, i, i+1); } } } private void swap(int arr[],int low,int high){ int temp = arr[low]; arr[low] = arr[high]; arr[high] = temp; }
19) Inversions where i < j < k and input[i] > input[j] > input[k]
Preview:
*/
public int findInversions(int input[]) {
int inversion = 0;
for (int i = 1; i < input.length - 1 ; i++) {
int larger = 0;
for (int k = 0; k < i; k++) {
if (input[k] > input[i]) {
larger++;
}
}
System.out.println("~~~~"+larger);
int smaller = 0;
for (int k = i+1; k < input.length; k++) {
if (input[k] < input[i]) {
smaller++;
}
}
System.out.println("************"+smaller);
inversion += smaller*larger;
}
return inversion;
}
No comments:
Post a Comment