You are tasked with implementing a function moveZeros(arr) that moves all 0s in an array to the end without changing the order of other elements. Your solution should be optimized for performance and handle edge cases.
Write the function such that:
Zeros must be moved to the end.
The relative order of non-zero elements must remain the same.
Optimize your solution with minimal iterations if possible.
You need to return the modified array as the output.
function moveZeros(arr) {
const nonZeros = arr.filter(element => element !== 0);
const zeroCount = arr.length - nonZeros.length;
return nonZeros.concat(Array(zeroCount).fill(0));
}const chai = require("chai");
const assert = chai.assert;
describe("moveZeros", function() {
it("should move all zeros to the end", function() {
assert.deepEqual(moveZeros([false, 1, 0, 1, 2, 0, 1, 3, "a"]), [false, 1, 1, 2, 1, 3, "a", 0, 0]);
});
it("should handle an array with no zeros", function() {
assert.deepEqual(moveZeros([1, 2, 3, 4, 5]), [1, 2, 3, 4, 5]);
});
it("should handle an array with all zeros", function() {
assert.deepEqual(moveZeros([0, 0, 0, 0]), [0, 0, 0, 0]);
});
it("should handle an empty array", function() {
assert.deepEqual(moveZeros([]), []);
});
it("should handle mixed data types", function() {
assert.deepEqual(moveZeros([0, "a", 0, 1, 0, 3]), ["a", 1, 3, 0, 0, 0]);
});
});You are given a 2D grid-based map, where:
0 represents walkable space.
1 represents an obstacle (you cannot walk through it).
Your task is to implement a function that computes the shortest path from the top-left corner of the map to the bottom-right corner, moving only up, down, left, or right (no diagonal moves).
Your function should return:
The length of the shortest path from the start (0,0) to the end (n-1, m-1).
Return -1 if there is no valid path available.
Input
grid - A 2D array of integers representing the map. (0 <= n, m <= 20)
Example:
[[0, 1, 0, 0].
[0, 0, 1, 0],
[0, 1, 0, 0],
[0, 0, 0, 0]]
Output
An integer representing the length of the shortest path or -1 if there’s no valid path.
Constraints
You can only move up, down, left, right.
You cannot move diagonally.
If you encounter a 1 in the grid, you cannot move into it.
You can solve this problem using Breadth-First Search (BFS), which is ideal for shortest path traversal problems in an unweighted 2D grid.
function shortestPath(grid) {
const rows = grid.length;
const cols = grid[0].length;
if (rows === 0 || cols === 0) return -1;
// Starting point blocked
if (grid[0][0] === 1 || grid[rows - 1][cols - 1] === 1) return -1;
// Edge case: Single cell scenario
if (rows === 1 && cols === 1) return 0;
const directions = [
[0, 1], // right
[0, -1], // left
[1, 0], // down
[-1, 0] // up
];
const queue = [[0, 0, 0]]; // Row, Col, Steps
const visited = Array.from({ length: rows }, () => Array(cols).fill(false));
visited[0][0] = true;
while (queue.length > 0) {
const [row, col, steps] = queue.shift();
if (row === rows - 1 && col === cols - 1) {
return steps; // Found the destination
}
for (const [dr, dc] of directions) {
const newRow = row + dr;
const newCol = col + dc;
if (
newRow >= 0 &&
newRow < rows &&
newCol >= 0 &&
newCol < cols &&
!visited[newRow][newCol] &&
grid[newRow][newCol] === 0
) {
visited[newRow][newCol] = true;
queue.push([newRow, newCol, steps + 1]);
}
}
}
return -1; // No path found
}const chai = require("chai");
const assert = chai.assert;
describe("shortestPath", function() {
it("should find the shortest path in a clear path grid", function() {
const grid = [
[0, 0, 0, 0],
[0, 1, 0, 0],
[0, 0, 1, 0],
[0, 0, 0, 0]
];
assert.strictEqual(shortestPath(grid), 6);
});
it("should return -1 if no path exists", function() {
const grid = [
[0, 1, 0, 0],
[1, 1, 1, 0],
[0, 1, 1, 0],
[0, 0, 0, 0]
];
assert.strictEqual(shortestPath(grid), -1);
});
it("should handle an empty single-cell map", function() {
const grid = [[0]];
assert.strictEqual(shortestPath(grid), 0);
});
it("should handle edge cases with large obstacles blocking the path", function() {
const grid = [
[0, 1, 1, 1],
[0, 1, 1, 1],
[0, 1, 1, 1],
[0, 0, 0, 0]
];
assert.strictEqual(shortestPath(grid), 6);
});
it("should handle large valid paths in a clear 20x20 grid", function() {
const grid = Array.from({ length: 20 }, () => Array(20).fill(0));
assert.strictEqual(shortestPath(grid), 38);
});
});