× logo Home HTML CSS Javascript React-App Angular logo
logo

Mastering Top 10 Javascript Algorithms

**Algorithm Name**: Array Maximum Visitable Webpages

* **Questions**:
- N: Are there any constraints on the size of the input?
- L: Is the input sorted in any way?
- Are there any negative numbers?

* **Time Complexity**:
- Brute Force: O(n^2)
- Optimized: O(n log n)

* **Space Complexity**:
- Brute Force: O(n)
- Optimized: O(n)

* **Approaches**:
- Optimized: The optimized approach is to sort the array in ascending order on the basis of the time spent on each site, and then keep on adding it to a running sum until we run out of batteries, or we have visited all of the sites.
To do this, we make use of a priority queue(a max-heap data structure is maintained with the help of a PriorityQueue library of JAVA).

- Brute Force:
The brute force way of solving this question is to visit every possible combination of sites.
However, this is a very inefficient solution as it has a high time complexity of O(2^n).

* **Explanation**:
We need to begin visiting the sites such that we visit the sites with the least time required first. But, the site visit order doesn't matter.

Thus, we can ensure that we stick on to a policy of visiting the site requiring the least time first by making use of a Priority Queue which places the sites requiring lesser time at the first place always.

* **Sample Code**: language-javascript

getMaxVisitableWebpages = (N, L) => {
// We sort the array in ascending order
L.sort((a, b) => a - b);
let visitedWebpagesCount = 0, batteryInUse = 0;
// We iterate through the sorted array
for(let i = 0; i < L.length; i++) {
if(batteryInUse + L[i] <= N) {

// Consuming the webpage only when we have enough battery batteryInUse += L[i];
visitedWebpagesCount++;
} else {
// Exiting the loop when the battery isn't enough
break;
}
}
return visitedWebpagesCount;
}

//Unit Test
Get the result with a sample input:
console.log(getMaxVisitableWebpages(10, [1, 2, 3, 4, 5, 6])); // Output: 4
console.log(getMaxVisitableWebpages(10, [1, 9, 5, 2])); // Output: 3

* **Example**:
- Input: N = 10, L = [1, 2, 3, 4, 5, 6]
- Output: 4





logo