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.
1#include <stdio.h>
2
3void merge(int arr[], int l, int m, int r) {
4 int i, j, k;
5 int n1 = m - l + 1;
6 int n2 = r - m;
7 int L[n1], R[n2];
8 for (i = 0; i < n1; i++)
9 L[i] = arr[l + i];
10 for (j = 0; j < n2; j++)
11 R[j] = arr[m + 1+ j];
12 i = 0; j = 0; k = l;
13 while (i < n1 && j < n2) {
14 if (L[i] <= R[j]) {
15 arr[k] = L[i];
16 i++;
17 } else {
18 arr[k] = R[j];
19 j++;
20 }
21 k++;
22 }
23 while (i < n1) {
24 arr[k] = L[i];
25 i++;
26 k++;
27 }
28 while (j < n2) {
29 arr[k] = R[j];
30 j++;
31 k++;
32 }
33}
34
35void mergeSort(int arr[], int l, int r) {
36 if (l < r) {
37 int m = l+(r-l)/2;
38 mergeSort(arr, l, m);
39 mergeSort(arr, m+1, r);
40 merge(arr, l, m, r);
41 }
42}
43
44void printArray(int A[], int size) {
45 int i;
46 for (i=0; i < size; i++)
47 printf("%d ", A[i]);
48 printf("\n");
49}
50
51int main() {
52 int arr[] = {12, 11, 13, 5, 6, 7};
53 int arr_size = sizeof(arr)/sizeof(arr[0]);
54
55 printf("Given array is \n");
56 printArray(arr, arr_size);
57
58 mergeSort(arr, 0, arr_size - 1);
59
60 printf("Sorted array is \n");
61 printArray(arr, arr_size);
62 return 0;
63}The code provided implements the Merge Sort algorithm using a divide and conquer strategy. The array is split into halves, sorted, and merged.
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
public class TwoSum {
public int[] TwoSumIndices(int[] nums, int target) {
int left = 0, right = nums.Length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
return new int[] {left, right};
} else if (sum < target) {
left++;
} else {
right--;
}
}
return new int[] {-1, -1};
}
static void Main() {
var solution = new TwoSum();
int[] nums = {2, 3, 4, 5, 6, 7};
int target = 9;
int[] result = solution.TwoSumIndices(nums, target);
Console.WriteLine("Indices: {0}, {1}", result[0], result[1]);
}
}The C# implementation uses the two-pointer technique to efficiently find two indices in a sorted array that add up to a specified target. It's straightforward and effective for such problems.