Sponsored
Sponsored
This approach involves breaking down the problem into smaller sub-problems, solving each sub-problem recursively, and combining the results to solve the larger problem. It's often used in sorting and searching algorithms, such as Merge Sort and Quick Sort.
Time Complexity: O(n log n) for the average and worst case.
Space Complexity: O(n) due to the temporary arrays used for merging.
1class MergeSort {
2
3 void merge(int arr[], int l, int m, int r) {
4 int n1 = m - l + 1;
5 int n2 = r - m;
6 int L[] = new int[n1];
7 int R[] = new int[n2];
8 for (int i = 0; i < n1; ++i)
9 L[i] = arr[l + i];
10 for (int j = 0; j < n2; ++j)
11 R[j] = arr[m + 1 + j];
12
13 int i = 0, j = 0;
14 int k = l;
15 while (i < n1 && j < n2) {
16 if (L[i] <= R[j]) {
17 arr[k] = L[i];
18 i++;
19 } else {
20 arr[k] = R[j];
21 j++;
22 }
23 k++;
24 }
25
26 while (i < n1) {
27 arr[k] = L[i];
28 i++;
29 k++;
30 }
31
32 while (j < n2) {
33 arr[k] = R[j];
34 j++;
35 k++;
36 }
37 }
38
39 void sort(int arr[], int l, int r) {
40 if (l < r) {
41 int m = (l+r)/2;
42 sort(arr, l, m);
43 sort(arr, m + 1, r);
44 merge(arr, l, m, r);
45 }
46 }
47
48 static void printArray(int arr[]) {
49 int n = arr.length;
50 for (int i=0; i<n; ++i)
51 System.out.print(arr[i] + " ");
52 System.out.println();
53 }
54
55 public static void main(String args[]) {
56 int arr[] = {12, 11, 13, 5, 6, 7};
57
58 System.out.println("Given Array");
59 printArray(arr);
60
61 MergeSort ob = new MergeSort();
62 ob.sort(arr, 0, arr.length-1);
63
64 System.out.println("Sorted array");
65 printArray(arr);
66 }
67}The Java implementation performs Merge Sort by splitting the array, sorting, and merging. It uses methods for the sort and merge operations.
This approach involves using two pointers or indices to traverse an array or linked list from two ends towards the center. It’s often applied to solve problems like palindrome checking, two-sum in a sorted array, and finding pairs in a sorted array.
Time Complexity: O(n) as each element is examined once in the worst case.
Space Complexity: O(1) because we're only using a fixed amount of additional space.
1
This C code demonstrates using a two-pointer technique in a sorted array to find two numbers that sum up to a target. It initializes pointers at each end of the array and adjusts them till the required sum is found or pointers cross.