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.
1function mergeSort(arr) {
2 if (arr.length < 2) {
3 return arr;
4 }
5 const mid = Math.floor(arr.length / 2);
6 const left = arr.slice(0, mid);
7 const right = arr.slice(mid);
8 return merge(mergeSort(left), mergeSort(right));
9}
10
11function merge(left, right) {
12 const result = [];
13 let i = 0;
14 let j = 0;
15 while (i < left.length && j < right.length) {
16 if (left[i] < right[j]) {
17 result.push(left[i]);
18 i++;
19 } else {
20 result.push(right[j]);
21 j++;
22 }
23 }
24 return result.concat(left.slice(i)).concat(right.slice(j));
25}
26
27const arr = [12, 11, 13, 5, 6, 7];
28console.log("Sorted array is", mergeSort(arr));The JavaScript implementation uses recursive functions to perform Merge Sort. The array is split into smaller arrays, sorted, and merged back together.
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 JavaScript code utilizes two pointers to find two elements in a sorted array that sum to a target value. It iteratively positions pointers based on the comparison of current sums to the target.