Data structures and Algorithms

1. Reverse the Array.   Problem link :- Reverse the array Algorithm idea :- C code //Reverse the array #include<stdio.h> void rev_arr(int arr[], int start, int end) { int temp; while(start < end) { temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start++; end--; } } void print_arr(int arr[], int size) { int i; for(i=0; i<size; i++) printf("\t%d",arr[i]); printf("\n"); } void main() { int arr1[30]; int n, i; printf("Enter the size of the array\n"); scanf("%d",&n); printf("Enter the elements of the array\n"); for(i=0; i<n; i++) scanf("%d",&arr1[i]); printf("Array before reversing\n"); print_arr(arr1, n); rev_arr(arr1, 0, n-1); printf("\nArray after reversing\n"); print_arr(arr1, n); } Java code //Reverse the array package programs;...

  2. Find the Minimum and Maximum element of the Array.  Problem link :- Minimum and Maximum element of the Array.         We are going to solve all this problems using functions. And in C and C++ we cannot return more than one variable from a function. So I have called function by reference(call by reference / call by address).         But geeks for geeks used structure to return 2 variables simultaneously (indirect). C code //Find the maximum element in an array #include<stdio.h> void min_max(int arr[], int *min, int *max, int n) { int i; if(n == 1) { *min = arr[0]; *max = arr[0]; } if(arr[0] < arr[1]) { *min = arr[0]; *max = arr[1]; } else { *min = arr[1]; *max = arr[0]; } for(i=2; i<n; i++) { if(arr[i] > *max) *max = arr[i]; else if(arr[i] < *min) *min = arr[i]; } } voi...

3. Find the K th smallest element of the array. Problem link :- click here C code //Kth Smallest element #include<stdio.h> void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } int partition(int A[], int start, int end) { int pivot, i, j; pivot = A[end]; i = start - 1; j = start; for(j=start; j<end; j++) { if(A[j] < pivot) { i++; swap(&A[i], &A[j]); } } i++; swap(&A[i], &A[end]); return i; } int kth_smallest(int A[], int start, int end, int k) { int pos, length; if(start < end) { pos = partition(A, start, end); length = pos + 1; if(k == length) return A[pos]; if(k < length) return kth_smallest(A, start, pos-1, k); else return kth_smallest(A, pos+1, end, k); } } void main() { int arr1[30]; int n; int i; int ans, k; printf("Enter...

3.b) Find the K th Largest element in the array. Problem link :- ಸಿಕ್ಕಿದರೆ ಕಳುಹಿಸಿ //kth largest element #include<stdio.h> void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } int partition(int A[], int start, int end) { int pivot, i, j; pivot = A[end]; i = start - 1; j = start; for(j=start; j<end; j++) { if(A[j] < pivot) { i++; swap(&A[i], &A[j]); } } i++; swap(&A[i], &A[end]); return i; } int kth_largest(int A[], int start, int end, int k) { int pos, length; if(start < end) { pos = partition(A, start, end); length = pos + 1; if(k == length) return A[pos]; if(k < length) return kth_largest(A, start, pos-1, k); else return kth_largest(A, pos+1, end, k); } } void main() { int arr1[30]; int n, i; int k, ans, corrk; printf("Enter the si...

4.Sort an array of 0's, 1's & 2's. Problem link :- click here C code #include<stdio.h> void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } void sort_012(int A[], int n) { int i, j, m; i = 0; j = n-1; m = 0; while(m<=j) { if(A[m] == 0) { swap(&A[i], &A[m]); i++; m++; } else if(A[m] == 1) { m++; } else { swap(&A[j], &A[m]); j--; } } } void main() { int arr[30]; int n, i; printf("Enter the size of the array\n"); scanf("%d",&n); printf("Enter the elements of the array(only 0, 1, or 2)\n"); for(i=0; i<n; i++) scanf("%d",&arr[i]); printf("Given Array\n"); for(i=0; i<n; i++) printf("\t%d",arr[i]); printf("\n...

5.Move negative elements to one side of the array. Problem link :- click here Problem method :- Partition(quick sort, quick select) C code //move negative elements #include<stdio.h> void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } void move_neg(int A[], int start, int end) { int i, j, pivot; pivot = 0; i = start-1; j = start; for(j=start; j<end; j++) { if(A[j] < pivot) { i++; swap(&A[i], &A[j]); } } i++; swap(&A[i], &A[end]); } void main() { int arr[30]; int n, i; printf("Enter the size of the array\n"); scanf("%d",&n); printf("Enter the elements of the array\n"); for(i=0; i<n; i++) scanf("%d",&arr[i]); printf("Given Array\n"); for(i=0; i<n; i++) printf("\t%d",arr[i]); printf("\n"); move_...

6.Union and Intersection of sorted arrays. Problem link :- click here This problem is similar to second part of the merge sort(you have to make some changes). Merge sort video is placed at the bottom. C code //Union and Intersection #include<stdio.h> void print_union(int A[], int B[], int m, int n) { int i, j; i=0; j=0; while(i<m && j<n) { if(A[i] < B[j]) { printf("\t%d",A[i]); i++; } else if(B[j] < A[i]) { printf("\t%d",B[j]); j++; } else if(A[i] == B[j]) { printf("\t%d",A[i]); i++; j++; } } while(i<m) { printf("\t%d",A[i]); i++; } while(j<n) { printf("\t%d",B[j]); j++; } } void print_intersection(int A[], int B[], int m, int n)...

7. Cyclically rotate an array by one. Problem link :- click here This problem is too easy. C code //Rotate #include<stdio.h> void rotate(int A[], int n) { int x, i; x = A[n-1]; for(i=n-1; i>=0; i--) A[i] = A[i-1]; A[0] = x; } void main() { int arr[30]; int n, i; printf("Enter the size of the array\n"); scanf("%d",&n); printf("Enter the elements of the array\n"); for(i=0; i<n; i++) scanf("%d",&arr[i]); printf("Given Array\n"); for(i=0; i<n; i++) printf("\t%d",arr[i]); printf("\n"); rotate(arr, n); printf("\n\nArray after rotation\n"); for(i=0; i<n; i++) printf("\t%d",arr[i]); printf("\n\n"); } Java code //Rotate cyclically by 1 package programs; import java.util.*; public class Array__7 { static void rotate(int arr[], int n) { int i, last; la...

8. Largest sum contiguous subarray. Problem link :- click here C code //kadane's algorithm #include<stdio.h> int maxSubarraySum(int A[], int n) { int i, cur_sum, max_sum; cur_sum = 0; max_sum = A[0]; for(i=0; i<n; i++) { cur_sum = cur_sum + A[i]; if(cur_sum > max_sum) { max_sum = cur_sum; } if(cur_sum < 0) { cur_sum = 0; } } return max_sum; } void main() { int arr[30]; int n, i, ans; printf("Enter the size of the array\n"); scanf("%d",&n); printf("Enter the elements of the array\n"); for(i=0; i<n; i++) scanf("%d",&arr[i]); printf("Given Array\n"); for(i=0; i<n; i++) printf("\t%d",arr[i]); ans = maxSubarraySum(arr, n); printf("\n\nMaximum sum contiguous sub array of the given array is %d\n", ans); } Java code /...

10. Minimum jumps to reach the end. Problem link :- click here C code //min jumps to end #include<stdio.h> int max(int a, int b) { if(a>b) return a; return b; } int min_jump(int a[], int n) { int i, step, max_range, jump; if(n <= 1) return 0; if(a[0] == 0) return -1; jump = 1; step = a[0]; max_range = a[0]; //maximum reachable index for(i=1; i<n; i++) { if(i == n-1) return jump; max_range = max(max_range, i+a[i]); step--; if(step == 0) { jump++; if(i>=max_range) return -1; if(max_range >= n-1) return jump; step = max_range - i; } } return jump; } void main() { int arr[30]; int i, n, ans; printf("Enter the size of the array\n"); scanf("%d",&n); printf("Enter the elements of the array\n");...

11. Duplicate in an array. Problem link :- click here Note :- We have to include "Stdlib.h" library to use "abs" function. C code //Duplicate in an array #include<stdio.h> #include<stdlib.h> void print_repeating(int arr[], int n) { int i; for(i=0; i<n; i++) { if(arr[abs(arr[i])] >= 0) arr[abs(arr[i])] = -arr[abs(arr[i])]; else printf("\t%d",abs(arr[i])); } } void main() { int arr[30]; int n, i; printf("Enter the size of the array\n"); scanf("%d",&n); printf("Enter the elements of the array\n"); for(i=0; i<n; i++) scanf("%d",&arr[i]); printf("Given Array\n"); for(i=0; i<n; i++) printf("\t%d",arr[i]); printf("\n"); printf("\n\nDuplicates elements in array are :- \n"); print_repeating(arr, n); } Java code //Duplicate pa...

12. Merge 2 sorted arrays.   Problem link :- click here C code //merge two sorted arrays #include<stdio.h> void merge(int a[], int b[], int m, int n) { int i, j; //i->b j->a int last; for(i=n; i>=0; i--) { j = m-2; last = a[j]; for(j=m-2; j>=0 && b[i]<a[j]; j--) { a[j+1] = a[j]; } if(j!=m-2 || last>b[i]) { a[j+1] = b[i]; b[i] = last; } } } void main() { int arr1[30], arr2[30]; int m, n; int i; printf("Enter the size of the array 1\n"); scanf("%d",&m); printf("Enter the elements of the array 1\n"); for(i=0; i<m; i++) scanf("%d",&arr1[i]); printf("Enter the size of the array 2\n"); scanf("%d",&n); printf("Enter the elements of the array 2\n"); for(i=0; i<n; i++) scanf("%...

13. Merge Intervals Problem link :- click here package programs; import java.util.*; class Interval { int start; int end; Interval() {} Interval(int a, int b) { this.start = a; this.end = b; } } public class Array__13 { static List<Interval> mergeIntervals(List<Interval> intervals) { if(intervals.size() <= 1 || intervals ==null) return intervals; Collections.sort(intervals, Comparator.comparing((Interval x)->x.start)); List<Interval> result = new ArrayList<>(); Interval inHand = intervals.get(0); for(Interval iterate : intervals) { if(inHand.end >= iterate.start) inHand.end = Math.max(inHand.end, iterate.end); else { result.add(inHand); inHand = iterate; } } result.add(inHand); return result; } public static void main(String[] args) { List<Interval> intervals = new ArrayList<>(); intervals.add(new Interval(8, 10)); intervals.add(new Interval(1, 3)); ...

14. Next Permutation Problem link :- click here package programs; import java.util.*; public class Array__14 { static void nextPermutation(int[] arr) { int key, i; if(arr.length <= 1) return; for(i=arr.length-2; i>=0; i--) //step 1 { if(arr[i] < arr[i+1]) break; } key = i; if(i == -1) //in question 2nd para { reverse(arr, 0, arr.length-1); //we can reverse the array //instead of sorting it return; } for(i=arr.length-1; i>key; i--) //step 2 { if(arr[i] > arr[key]) { swap(arr, i, key); break; } } reverse(arr, key+1, arr.length-1); //step 3 return; } public static void main(String[] args) { int i, n; Scanner s = new Scanner(System.in); System.out .println("Enter the size of the array : "); n = s.nextInt(); int array[] = new int[n]; System.out.println("Enter the elements of the array\n...

15. Inversion count Problem link :- click here package programs; import java.util.*; public class Array__15 { static int merge(int arr[], int left, int mid, int right) { int inversion_count=0; int n1 = mid - left; int n2 = right - mid + 1; int a[] = new int[n1]; int b[] = new int[n2]; int i, j, k; j = left; for(i=0; i<n1; i++) { a[i] = arr[j]; j++; } for(i=0; i<n2; i++) { b[i] = arr[j]; j++; } i = 0; j = 0; k = left; while( i<n1 && j<n2 ) { if( a[i] <= b[j] ) arr[k++] = a[i++]; else { inversion_count = inversion_count + (n1 - i); arr[k++] =...

16. Best time to buy and sell shares Problem link :- click here //Best time to buy and sell shares package programs; import java.util.*; public class Array__16 { static int maxProfit(int arr[]) { int i, min, profit; min = Integer.MAX_VALUE; profit = 0; for(i=0; i<arr.length; i++) { if(arr[i] < min) min = arr[i]; if(arr[i]-min > profit) profit = arr[i]-min; } return profit; } public static void main(String[] args) { int i, n, ans; Scanner s = new Scanner(System.in); System.out .println("Enter the size of the array : "); n = s.nextInt(); int array[] = new int[n]; System.out.println("Enter the elements of the array\n"); for(i=0; i<n; i++) array[i] = s.nextInt(); System.out.println("Given array :"); print_array(array, n); System.out.println("\n"); ans = maxProfit(array); System.out.println("Maximum profit : " + ans); } static void print_array(int[]...

17. Count pairs with given sum Problem link :- click here package programs; import java.util.*; public class Array__17 { static int getPairsCount(int arr[], int n, int sum) { HashMap<Integer, Integer> frequencyMap = new HashMap<>(); for(int i=0; i<n; i++) { if(!frequencyMap.containsKey(arr[i])) frequencyMap.put(arr[i], 1); else frequencyMap.put(arr[i], frequencyMap.get(arr[i])+1); } int twiceCount =0; for(int i=0; i<n; i++) { if( frequencyMap.containsKey(sum - arr[i]) ) twiceCount += frequencyMap.get(sum - arr[i]); if( sum-arr[i] == arr[i] ) twiceCount--; } return twiceCount/2; } public static void main(String[] args) { int i, n, ans, sum; Scanner s = new Scanner(System.in); System.out .print("Enter the size of the array : "); n = s.nextInt(); int array[] = new int[n]; System.out.println("Enter the elements of the array\n"); for(i=0; i<n; i++) array[i] = s.nex...

18. Common elements in 3 sorted arrays Problem link :- click here package programs; import java.util.*; public class Array__18 { static void printInsection(int a[], int b[], int c[]) { int i, j, k; i = 0; j = 0; k = 0; while(i<a.length && j<b.length && k<c.length) { if( a[i]==b[j] && b[j]==c[k] ) { System.out.print(a[i] + "\t"); i++; j++; k++; } else if( a[i] < b[j] ) i++; else if( b[j] < c[k] ) j++; else if( c[k] < a[i] ) k++; } } public static void main(String[] args) { int m, n, o; Scanner s = new Scanner(System.in); System.out.print("Enter the size of the array 1 : "); m = s.nextInt(); int array_1[] = new int[m]; System.out.println("Enter the elements of the array 1 :"); readArray(array_1, m); System.out.print("Enter the size of the array 2 : "); n = s.nextInt(); int array_2[] = new int[n]; S...

19. Rearrange array in alternating positive and negative items with O(1) extra space Problem link :- click here package programs; import java.util.*; public class Array__19 { static void rearrange(int arr[], int n) { int wrong_index = -1; for(int i=0; i<n; i++) { if(wrong_index != -1) { if( ( arr[wrong_index]>=0 && arr[i]<0 ) || ( arr[wrong_index]<0 && arr[i]>=0 ) ) { rightRotate(arr, wrong_index, i); if( i - wrong_index >=2) wrong_index += 2; else wrong_index = -1; } } else if( ( i%2==0 && arr[i]>=0 ) || ( i%2==1 && arr[i]<0 ) ) { wrong_index = i; } } } static void rightRotate(int arr[], int from, int to) { int temp = arr[to]; for(int i=to; i>from; i--) arr[i] = arr[i-1]; arr[from] = temp; } public static void main(String[] args) { int i, n; Scanner s = new Scanner(System.in); System.out.print...

20. Subarray with 0 sum Problem link :- click here package programs; import java.util.*; public class Array__20 { static Boolean subArrayWithSunZero(int arr[], int n) { HashSet<Integer> sum_in_each_step = new HashSet<>(); int sum = 0; for(int i=0; i<n; i++) { sum = sum + arr[i]; if(sum==0 || arr[i]==0 || sum_in_each_step.contains(sum)) return true; //since we cannot subtract elements added before //if we store sum of each step in some data structure //and if it repeats // which means we added nothing but zero // which in-turn means we just passed a // sub-array with sum zero sum_in_each_step.add(sum); } return false; } ...

21. Factorials of large number Problem link :- click here package programs; import java.util.ArrayList; public class Array__21 { static ArrayList<Integer> factorialOfLargeNumbers(int n) { ArrayList<Integer> product = new ArrayList<Integer>(); //very important step I searched for this mistake for nearly 1 hour product.add(1); //multiplying from 2 because why do you multiply any number with 1 for(int i=2; i<=n; i++) { //multiplying one by one multiply(product, i); } return product; } static void multiply(ArrayList<Integer> product, int multiplier) { int carry =0; for(int i=0; i<product.size(); i++) { //storing product with a digit(with carry added) in temporary variable int temp = (product.get(i) * multiplier) +...

22. Maximum product sub array Problem link :- click here package programs; import java.util.*; public class Array__22 { static int maxProduct(int arr[], int n) { int product, max_product; int neg_flag, zero_flag; product = 1; max_product = 0; //our final answer //neg_flag=0 -> no negative element //neg_flag=1 -> there is 1 negative element neg_flag = 0; int neg = 0; //to store the negative element //zero_flag=0 -> at least there is one nonzero positive element //zero_flag=1 -> there are only nonzero elements and negative elements zero_flag = 1; for(int i=0; i<n; i++) { //if we come across zero in the middle //then product till that element will be zero //so we will start multiplying from elements //...

23. Longest consecutive subsequence Problem link :- click here package programs; import java.util.*; public class Array__23 { static int longestConsecutiveSubsequence(int arr[], int n) { HashSet<Integer> hash_set = new HashSet<>(); //adding all the elements of the array to the hash_set for(int i=0; i<n; i++) hash_set.add(arr[i]); int max = 0; //our result //iterating through the array for(int i=0; i<n; i++) { //hash_set.contains(arr[i]-1) -> // means arr[i] is not the starting point //hence we are going to the starting point // by using not(!) in the same condition if(!hash_set.contains(arr[i]-1)) { //taking first element in 'j' int j = arr[i...

24. Elements that appear more than n/k times Problrm link :- click here //optimal solution to this problem is //using hash map package programs; import java.util.*; class eleCount { int element; int count; } public class Array__24 { static void elementsThatAppearsMoreThanNDivdedBykTimes(int arr[], int n, int k) { //creating a array of best (k-1) elements eleCount temp[] = new eleCount[k-1]; //initializing the count all the elements of best (k-1) array to zero for(int i=0; i<k-1; i++) { //we just created array of objects we have to create //object of each and every element of the array eleCount element = new eleCount(); element.element = -10; element.count = 0; temp[i] = element; } //SELSCTING BEST (k-1) ELEMENTS for(int i=0; i<n; i++) ...

25. Maximum profit by buying and selling a share at most twice Problem link :- click here package programs; import java.util.*; public class Array__25 { static int maxProfitByByuingOrSellingSharesAtMostTwice(int price[], int n) { //as our idea is do one transaction from end and other from start //we need a array to keep updating the maximum profit int profit[] = new int[n]; //lets initialize last element as zero as my 1st transaction is from end //you can make first element as zero if your 1st transaction is from beginning profit[n-1] = 0; /*1st TRANSACTION FROM END you have to store max if your transaction is from end since you are moving to left & you should sell shares to your right but you don't know the value and you will get more profit when the price is maximum while selling hence you are storing maximum...

26. Array subset of another array Problem link :- click here package programs; import java.util.*; public class Array__26 { static Boolean arraySubsetOfAnotherArray(int a[], int b[], int n1, int n2) { /*we have to check whether 'b' is a subset of 'a' a is a super set b can be a subset of a which means n1 must be greater than b*/ if(n1<n2) return false; /*lets push all the elements of 'a' to a hash-set and we will iterate through 'b' and if any element of 'b' is not present in 'a' then 'b' is not a subset of 'a'*/ HashSet<Integer> hash_set = new HashSet<>(); //we don't need to check whether any element is repeated //as they are giving us set (in set elements don't re...

27. Triplet sum in Array Problem link :- click here package programs; import java.util.*; public class Array__27 { static Boolean triplet(int arr[], int n, int sum) { quickSort(arr, 0, n-1); for(int i=0; i<n-2; i++) { int j = i+1; int k = n-1; while(j<k) { if(arr[i] + arr[j] + arr[k] == sum) { System.out.println("\n\nTriplet is : " + arr[i] + " " + arr[j] + " " + arr[k] ); return true; } else if(arr[i] + arr[j] + arr[k] < sum) j++; else k--; } } return false; } static void quickSort(int arr[], int start, int end) { int pos; if(start < end) { pos = partition(arr, start, end); quickSort(arr, start, pos-1); quickSort(arr, pos+1, end); } } static int partition(int arr[], int start, int end) { int pivot, i, j; pivot = arr[end]; i = start-1; j = start; for(j=start; j<end; j++) { if(arr[j] < pivot) { i++; int temp = arr...

28. Trapping rain water Problem link :- click here package programs; import java.util.*; public class Array__28 { /*we are going to find the amount of water trapped above each elemen(wall) for each element we will find the highest wall to its left and the highest wall to its right we will find the highest wall to left of each element and store it in a array right each element another array*/ static int waterTrapped(int arr[], int n) { //Note :- we cannot trap water above left-most and right-most element(wall) if(n<3) return 0; //create array for left and right highest wall int left[] = new int[n]; int right[] = new int[n]; //left array initialization left[0] = arr[0]; for(int i=1; i<n; i++...

29. Chocolate distribution problem Problem link :- click here \ package programs; import java.util.*; public class Array__29 { /* we will sort the array first and take every possible sub-array of size 'm' and since we have already sorted the array. we can get the minimum and maximum of that sub-array easily. we will return minimum of these values. */ static int minDifference(int arr[], int n, int m) { /* sorting the array using class ------> Arrays (which is a member of Java Collections Framework) method --> sort() */ Arrays.sort(arr); int min_difference = Integer.MAX_VALUE; /* we already know the size of the sub-array i.e., m. and we are iterating from 'i' which means 'i' is our first element's index so our last element's i...