How to useNaive Sparse Table in Javascript
In this approach, we are using the Naive Sparse Table approach, we create a 2D table to precompute and store minimum values for all subarrays in an input array. This allows efficient querying of minimum values for any subarray.
Example: In this example, we are using the above-explained apporach.
Javascript
function myFunction(arr) { const n = arr.length; const table = new Array(n).fill(0).map(() => new Array(n).fill(0)); // Initialize table with the original array for (let i = 0; i < n; i++) { table[i][i] = arr[i]; } // Build the table using a nested loop for (let len = 2; len <= n; len++) { for (let i = 0; i + len - 1 < n; i++) { const j = i + len - 1; table[i][j] = Math.min(table[i][j - 1], table[i + 1][j]); } } return table; } function sparseTable(table, left, right) { return table[left][right]; } const arr = [33, 5, 4, 2, 6]; const result = myFunction(arr); console.log(sparseTable(result, 1, 4)); |
Output
2
Sparse Table Using JavaScript Array
In this article, we are going to learn about Sparse Table using JavaScript array. Sparse Table is a data structure in JavaScript used for efficient range queries (e.g., minimum or maximum) on an array. It precomputes and stores values to answer queries quickly, reducing time complexity.
Example:
Input: arr[] = {7, 2, 3, 0, 5, 10, 3, 12, 18};
query[] = [0, 4], [4, 7], [7, 8]
Output: Minimum of [0, 4] is 0
Minimum of [4, 7] is 3
Minimum of [7, 8] is 12
Table of Content
- Using Naive Sparse Table
- Using Dynamic Programming
We will explore all the above methods along with their basic implementation with the help of examples.