Sliding window
This technique involves creating a window of a fixed size and sliding it over an array or string while performing operations on its elements. It is useful in problems that require finding subarrays or substrings that meet certain criteria, such as the maximum sum subarray problem.
// O(n*k) solution for finding maximum sum of
// a subarray of size k
// Returns maximum sum in a subarray of size k.
function maxSum( arr, n, k){
let max_sum = Number.MIN_VALUE;
for (let i = 0; i < n - k + 1; i++) {
let current_sum = 0;
for (let j = 0; j < k; j++)
current_sum = current_sum + arr[i + j];
max_sum = Math.max(current_sum, max_sum);
}
return max_sum;
}
let arr = [ 1, 4, 2, 10, 2, 3, 1, 0, 20 ];
let k = 4;
let n = arr.length;
document.write(maxSum(arr, n, k));
List of problems on LeetCode: https://leetcode.com/tag/sliding-window/
Two-pointers
This technique involves using two-pointers that move through an array or string in a coordinated way. It is useful in problems that require finding pairs or triplets of elements that meet certain criteria, such as the two-sum problem.
//Two pointer technique based solution to find
function isPairSumExist(arr, arrLength, X)
{
//First pointer
var i = 0;
//Cecond pointer
var j = arrLength - 1;
while (i < j) {
// If we find a pair
if (arr[i] + arr[j] == X)
return true;
// If sum of elements at current
// pointers is less, move towards i++
else if (arr[i] + arr[j] < X)
i++;
// If sum of elements at current
// pointers is more,move towards j--
else
j--;
}
return false;
}
var arr = [ 2, 3, 5, 8, 9, 10, 11 ];
var val = 17;
var arrSize =7;
document.write(isPairSum(arr, arrSize, val));
List of problems on LeetCode: https://leetcode.com/tag/two-pointers/
Binary search
This technique involves dividing a sorted array or range of values in half at each step, discarding the half that does not contain the target value, and repeating the process until the target value is found or the range is empty. It is useful in problems that involve searching or finding a specific value in a sorted array, such as the search in a rotated sorted array problem.
function binarySearch(arr, l, r, x){
if (r >= l) {
let mid = l + Math.floor((r - l) / 2);
// If the element is present at the middle
// itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then search left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
//Search in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// Not found
return -1;
}
List of problems on LeetCode: https://leetcode.com/tag/binary-search/
Breadth-first search
This technique involves exploring a graph or tree by visiting all the nodes at a given distance from the starting node before moving on to the nodes at the next distance. It is useful in problems that require finding the shortest path or distance between two nodes in a graph, such as a word ladder problem.
function bfsOfGraph(V, adj) {
let bfs_traversal = [];
let vis = [];
for (let i = 0; i < V; i++) {
vis.push(false);
}
for (let i = 0; i < V; ++i) {
// To check if already visited
if (!vis[i]) {
let q = [];
vis[i] = true;
q.push(i);
// BFS starting from ith node
while (!q.empty()) {
let g_node = q[0];
q.shift();
bfs_traversal.push(g_node);
for (let j = 0; j < adj[g_node].length;
j++) {
let it = adj[g_node][j];
if (!vis[it]) {
vis[it] = true;
q.push(it);
}
}
}
}
}
return bfs_traversal;
List of problems on LeetCode: https://leetcode.com/tag/breadth-first-search/
Depth-first search
This technique involves exploring a graph or tree by visiting as far as possible along each branch before backtracking. It is useful in problems that involve searching for a specific pattern or structure in a graph or tree, such as the maximum depth of a binary tree problem.
var inorderTraversal = function(root) {
let result = [];
dfs(root, result);
return result;
};
let dfs = (tree, result) => {
if(tree !== null) {
//Use tecursion for Deph-first search
dfs(tree.left, result);
result.push(tree.val);
dfs(tree.right, result);
}
}
List of problems on LeetCode: https://leetcode.com/tag/depth-first-search/
Top comments (0)