I want found solution O (n)
algorithm for this problem but unable to do.
After the cataclysm, there are only two ways to travel around the world:
-
magic ferries that move between neighboring islands (naturally, the ferry can move in both directions), so from the island that is in the i-th place in the cosmic row, you can get to the i-1 and i+1 islands;
-
portals through which you can teleport between islands regardless of the distance, but only if before the cataclysm these islands formed one continent (interestingly, the continents in this world had numbers, not names).
It is necessary to find the minimum number of movements from the first island to the last.example 1
11 -86 50 986 7 23 24 25 1846 201 9 19 11 86 2000 201 11 2010 234 156 11 456 488 478 985 6564 45341 3 201 8
answer 4
example 2
1 3 4 5 4 3
answer 2
The solution to the problem using a graph will be rejected because storing the list of nodes and the queue requires a lot of memory.Memory limit in this task 64 mb. Simply put, the solution using a graph is not optimal in terms of memory usage.
My question is there another algorithm to solve this problem. We know that the longest path is equal to the number of elements (islands) in the array.
const readline = require("readline").createInterface(process.stdin, process.stdout)
readline.on("line", line => {
let arr = line.split(" ").map(Number)
// console.time()
const graph = createGraph(arr)
const last = arr.length - 1
arr = null
const nodeState = new Map()
const startNode = { id: 0, distanceToSource: Number.POSITIVE_INFINITY, visited: false, open: false, heapId: -1 };
startNode.distanceToSource = 0
nodeState.set(0, startNode)
startNode.open = true
const queue = Queue()
queue.push(startNode);
while (queue.length) {
const parent = queue.pop()
parent.visited = true
if (parent.id === last) break
graph.get(parent.id).forEach(curr => {
let currNode = nodeState.get(curr);
if (!currNode) {
currNode = { id: curr, distanceToSource: Number.POSITIVE_INFINITY, visited: false, open: false, heapId: -1 };
nodeState.set(curr, currNode);
}
if (currNode.visited) return
if (currNode.open === false) {
queue.push(currNode);
currNode.open = true;
}
const distance = parent.distanceToSource + 1;
if (distance >= currNode.distanceToSource) return;
//currNode.parent = parent.id;
currNode.distanceToSource = distance;
// currNode.fScore = distance //+ heuristic(curr, arr.length - 1);
queue.updateItem(currNode.heapId)
});
graph.delete(parent.id)
}
// console.timeEnd()
console.log(nodeState.get(last).distanceToSource)
readline.close()
}).on("close", () => process.exit(0))
function createGraph(arr) {
const mapArr = new Map()
for (let i = 0; i < arr.length; i++) {
if (!mapArr.has(arr[i])) mapArr.set(arr[i], [i])
else mapArr.get(arr[i]).push(i)
}
const graph = new Map()
for (let i = 0; i < arr.length; i++) {
const node = []
if (i + 1 < arr.length)
node.push(i + 1)
if (i - 1 >= 0)
node.push(i - 1)
const findKey = mapArr.get(arr[i])
node.push(...findKey.filter(x => x != i - 1 || x != i + 1))
graph.set(i, node.filter(x => x != i).sort((a, b) => b - a))
}
return graph
}
const heuristic = (from, to) => to - from
function Queue() {
class PriorityQueue {
constructor() {
this.data = []
this.length = this.data.length;
}
compare = (a, b) => { return a.distanceToSource - b.distanceToSource }
notEmpty() {
return this.length > 0
}
pop() {
if (this.length === 0) return undefined;
const top = this.data[0];
this.length--;
if (this.length > 0) {
this.data[0] = this.data[this.length];
this.data[0].heapId = 0
this.down(0);
}
this.data.pop();
return top;
}
push(item) {
this.data.push(item);
item.heapId = this.length
this.length++;
this.up(this.length - 1);
}
up(pos) {
const item = this.data[pos];
while (pos > 0) {
const parent = (pos - 1) >> 1;
const current = this.data[parent];
if (this.compare(item, current) >= 0) break;
this.data[pos] = current;
current.heapId = pos
pos = parent;
}
item.heapId = pos
this.data[pos] = item;
}
down(pos) {
const halfLength = this.length >> 1;
const item = this.data[pos];
while (pos < halfLength) {
let left = (pos << 1) + 1;
const right = left + 1;
let best = this.data[left];
if (right < this.length && this.compare(this.data[right], best) < 0) {
left = right;
best = this.data[right];
}
if (this.compare(best, item) >= 0) break;
this.data[pos] = best;
best.heapId = pos
pos = left;
}
item.heapId = pos
this.data[pos] = item;
}
updateItem(pos) {
this.down(pos);
this.up(pos);
}
}
return new PriorityQueue();
}