DSA Interview Questions in JavaScript
Coding round problems solved in JavaScript, from arrays and strings to linked lists, trees and dynamic programming, with brute-force and optimised approaches and how to explain them to the interviewer.
Big O in plain words
What is Big O notation?
Big O describes how an algorithm's work grows as the input grows, ignoring constants and small terms. It answers: "If the input becomes 10 times bigger, roughly how much slower does this get?"
The examples below count the basic operations each function does for different input sizes:
function constant(arr) {
return arr[0];
}
function linear(arr) {
let ops = 0;
for (const x of arr) ops++;
return ops;
}
function quadratic(arr) {
let ops = 0;
for (const a of arr) for (const b of arr) ops++;
return ops;
}
for (const n of [10, 100, 1000]) {
const arr = Array.from({ length: n }, (_, i) => i);
console.log(`n=${n}: O(1) -> 1 op, O(n) -> ${linear(arr)} ops, O(n^2) -> ${quadratic(arr)} ops`);
}n=10: O(1) -> 1 op, O(n) -> 10 ops, O(n^2) -> 100 ops
n=100: O(1) -> 1 op, O(n) -> 100 ops, O(n^2) -> 10000 ops
n=1000: O(1) -> 1 op, O(n) -> 1000 ops, O(n^2) -> 1000000 opsWhen n grows 10 times, O(n) does 10 times more work, but O(n²) does 100 times more. That's why an O(n²) solution that passes small test cases can time out on large ones.
The common classes, fastest to slowest: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n), O(n²) quadratic, O(2ⁿ) exponential.
Big O describes how the running time or memory grows with input size, keeping only the dominant term. O(n) grows in proportion to the input, O(n squared) grows with its square, so for large inputs the growth rate matters far more than constant factors.
Likely follow-up: Why do we drop constants, so that O(2n) is just O(n)?
How do you work out the time complexity of a piece of code?
A practical method:
- A simple statement is O(1).
- A loop over n items is O(n) times the cost of its body.
- Nested loops multiply: a loop inside a loop over the same data is O(n²).
- Loops one after another add, and you keep the biggest: O(n) + O(n²) is O(n²).
- Halving the problem each step gives O(log n).
- Remember the hidden cost of built-ins:
includes,indexOf,sliceand spread are O(n) each.
function hasDuplicateSlow(arr) {
for (let i = 0; i < arr.length; i++) {
if (arr.slice(i + 1).includes(arr[i])) return true;
}
return false;
}
function hasDuplicateFast(arr) {
const seen = new Set();
for (const x of arr) {
if (seen.has(x)) return true;
seen.add(x);
}
return false;
}
const data = Array.from({ length: 5000 }, (_, i) => i);
console.log(hasDuplicateSlow(data), hasDuplicateFast(data));
console.log(hasDuplicateFast([3, 1, 3]));false false
truehasDuplicateSlow looks like one loop, but slice and includes inside it are each O(n), so it's really O(n²). hasDuplicateFast is O(n) because Set lookups are O(1) on average.
I count how often the innermost work runs: nested loops multiply, sequential steps add and I keep the largest term, and halving gives log n. I also watch for hidden loops in built-ins like includes, slice and spread.
Likely follow-up: What is the time complexity of array.shift(), and why?
Arrays and strings
Maximum subarray sum (Kadane's algorithm)
Given an array of integers (some negative), find the contiguous subarray with the largest sum.
Example: [-2, 1, -3, 4, -1, 2, 1, -5, 4] → 6, from [4, -1, 2, 1].
Idea: walk through the array keeping the best sum of a subarray ending here. At each number, either extend the previous subarray or start fresh from this number, whichever is bigger. Track the best seen overall.
function maxSubarraySum(nums) {
let current = nums[0];
let best = nums[0];
for (let i = 1; i < nums.length; i++) {
current = Math.max(nums[i], current + nums[i]);
best = Math.max(best, current);
}
return best;
}
console.log(maxSubarraySum([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
console.log(maxSubarraySum([5, 4, -1, 7, 8]));
console.log(maxSubarraySum([-3, -1, -2]));6
23
-1Time: O(n) · Space: O(1). Starting from nums[0] (not 0) handles all-negative arrays correctly: the answer is the largest single number.
I keep the best sum of a subarray ending at the current index: either the number alone or the number plus the previous best, whichever is larger, and track the overall maximum. It's one pass, O(n) time and O(1) space, and starting from the first element handles all-negative input.
Likely follow-up: How would you also return the start and end indexes of that subarray?
Move all zeroes to the end
Move every 0 to the end of the array in place, keeping the order of the other elements.
Example: [0, 1, 0, 3, 12] → [1, 3, 12, 0, 0].
Idea: keep a pointer insert for where the next non-zero should go. Copy each non-zero forward, then fill the rest with zeroes.
function moveZeroes(nums) {
let insert = 0;
for (const n of nums) {
if (n !== 0) nums[insert++] = n;
}
while (insert < nums.length) nums[insert++] = 0;
return nums;
}
console.log(moveZeroes([0, 1, 0, 3, 12]).join(","));
console.log(moveZeroes([0, 0, 1]).join(","));
console.log(moveZeroes([1, 2, 3]).join(","));1,3,12,0,0
1,0,0
1,2,3Time: O(n) · Space: O(1). Using filter plus padding would be simpler but creates a new array, which breaks the "in place" requirement.
I use a write pointer: for every non-zero number I write it at the pointer and advance it, which keeps their order, then I fill the remaining positions with zeroes. It's O(n) time and O(1) extra space.
Likely follow-up: Can you do it with fewer writes when there are very few zeroes?
Hashing and two pointers
Two sum (unsorted array)
Return the indexes of the two numbers that add up to target. Exactly one answer exists.
Idea: for each number, check whether its complement (target - number) has already been seen, using a Map from value to index.
function twoSum(nums, target) {
const seen = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (seen.has(complement)) return [seen.get(complement), i];
seen.set(nums[i], i);
}
return [];
}
console.log(twoSum([2, 7, 11, 15], 9).join(","));
console.log(twoSum([3, 2, 4], 6).join(","));
console.log(twoSum([-1, -2, -3, -4, -5], -8).join(","));0,1
1,2
2,4Time: O(n) · Space: O(n). The brute force checks every pair: O(n²).
I store each number's index in a Map as I go, and before storing, check whether target minus the current number is already there. One pass gives O(n) time with O(n) space.
Likely follow-up: How would you return all unique pairs instead of one?
Two sum on a sorted array (two pointers)
The array is sorted. Find two numbers that add up to target, using O(1) extra space.
Idea: start one pointer at each end. If the sum is too small, move the left pointer right (bigger numbers); if too big, move the right pointer left.
function twoSumSorted(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
const sum = nums[left] + nums[right];
if (sum === target) return [nums[left], nums[right]];
if (sum < target) left++;
else right--;
}
return null;
}
console.log(twoSumSorted([1, 3, 4, 6, 8, 11], 10).join("+"));
console.log(twoSumSorted([2, 7, 11, 15], 26).join("+"));
console.log(twoSumSorted([1, 2, 3], 100));4+6
11+15
nullTime: O(n) · Space: O(1). Each step safely discards one number, because sortedness tells us it can't be part of any answer.
Because the array is sorted, I use two pointers from both ends: if the sum is too small I move left forward, if too big I move right back. Each move eliminates one candidate, so it's O(n) time with O(1) space.
Likely follow-up: Why is it safe to discard the number when you move a pointer?
Stacks, queues and linked lists
Implement a stack
A stack is last in, first out (LIFO), like a pile of plates: you add (push) and remove (pop) only at the top. Uses: undo history, the browser back button, function calls, matching brackets.
A JavaScript array already behaves like a stack with push and pop, both O(1). Wrapping it in a class gives a clear, limited interface.
class Stack {
#items = [];
push(item) {
this.#items.push(item);
}
pop() {
if (this.isEmpty()) throw new Error("Stack is empty");
return this.#items.pop();
}
peek() {
return this.#items.at(-1);
}
isEmpty() {
return this.#items.length === 0;
}
get size() {
return this.#items.length;
}
}
const history = new Stack();
history.push("/home");
history.push("/ebooks");
history.push("/checkout");
console.log(history.pop(), history.peek(), history.size);
try {
new Stack().pop();
} catch (error) {
console.log(error.message);
}/checkout /ebooks 2
Stack is emptyAll operations are O(1). Throwing on an empty pop (instead of returning undefined) makes bugs obvious.
A stack is last in, first out. I implement it with an array using push and pop at the end, which are O(1), and expose push, pop, peek, isEmpty and size. Stacks suit undo, back navigation, recursion and bracket matching.
Likely follow-up: Why shouldn't you implement a stack with unshift and shift?
Min stack
Design a stack that also returns the minimum element in O(1).
Idea: keep a second stack of minimums. Each push records the minimum at that moment, so popping restores the previous minimum automatically.
class MinStack {
#items = [];
#mins = [];
push(value) {
this.#items.push(value);
const currentMin = this.#mins.length ? this.#mins.at(-1) : Infinity;
this.#mins.push(Math.min(value, currentMin));
}
pop() {
this.#mins.pop();
return this.#items.pop();
}
top() {
return this.#items.at(-1);
}
getMin() {
return this.#mins.at(-1);
}
}
const stack = new MinStack();
stack.push(5);
stack.push(2);
stack.push(8);
stack.push(1);
console.log(stack.getMin());
stack.pop();
console.log(stack.getMin(), stack.top());
stack.pop();
stack.pop();
console.log(stack.getMin());1
2 8
5Every operation is O(1); space is O(n) for the second stack.
Alongside the main stack I keep a stack of minimums, pushing the smaller of the new value and the current minimum each time. Popping both together means getMin is always the top of the min stack, so every operation is O(1).
Likely follow-up: Can you reduce the extra space by only pushing to the min stack when needed?
Trees and recursion
Preorder, inorder and postorder traversal
A binary tree node has a value and up to two children. Depth-first traversals differ only in when you visit the node itself:
- Preorder: node, left, right (copying a tree, prefix expressions)
- Inorder: left, node, right (gives a binary search tree in sorted order)
- Postorder: left, right, node (deleting a tree, evaluating expressions)
const node = (val, left = null, right = null) => ({ val, left, right });
// 4
// / \
// 2 6
// / \ / \
// 1 3 5 7
const root = node(4, node(2, node(1), node(3)), node(6, node(5), node(7)));
function preorder(n, out = []) {
if (!n) return out;
out.push(n.val);
preorder(n.left, out);
preorder(n.right, out);
return out;
}
function inorder(n, out = []) {
if (!n) return out;
inorder(n.left, out);
out.push(n.val);
inorder(n.right, out);
return out;
}
function postorder(n, out = []) {
if (!n) return out;
postorder(n.left, out);
postorder(n.right, out);
out.push(n.val);
return out;
}
console.log("pre: ", preorder(root).join(" "));
console.log("in: ", inorder(root).join(" "));
console.log("post:", postorder(root).join(" "));pre: 4 2 1 3 6 5 7
in: 1 2 3 4 5 6 7
post: 1 3 2 5 7 6 4Each traversal is O(n) time and O(h) space for the recursion, where h is the tree's height.
All three are depth-first and differ only in when the node is visited: before its children in preorder, between them in inorder, and after them in postorder. Inorder on a binary search tree gives sorted values. Each is O(n) time and O(height) space.
Likely follow-up: Write inorder traversal iteratively using a stack.
Level order traversal (breadth-first search)
Return the values level by level, top to bottom.
Idea: use a queue. Process the tree one level at a time: the queue's length at the start of each round is the number of nodes on that level.
const node = (val, left = null, right = null) => ({ val, left, right });
const root = node(3, node(9), node(20, node(15), node(7)));
function levelOrder(root) {
if (!root) return [];
const levels = [];
let queue = [root];
while (queue.length) {
levels.push(queue.map((n) => n.val));
const next = [];
for (const n of queue) {
if (n.left) next.push(n.left);
if (n.right) next.push(n.right);
}
queue = next;
}
return levels;
}
console.log(JSON.stringify(levelOrder(root)));
console.log(JSON.stringify(levelOrder(null)));[[3],[9,20],[15,7]]
[]Building a fresh next array for each level avoids shift(), which is O(n) on arrays. Time: O(n) · Space: O(w), the widest level.
I do a breadth-first search with a queue, processing one level per round: record the current level's values and collect their children as the next level. It's O(n) time and the space is the width of the widest level.
Likely follow-up: How would you print the tree in zigzag order, alternating direction each level?
Sorting and searching
Binary search
Find the index of target in a sorted array, or -1.
Idea: compare with the middle element; discard the half that can't contain the target. Each step halves the search space.
function binarySearch(sorted, target) {
let low = 0;
let high = sorted.length - 1;
while (low <= high) {
const mid = low + Math.floor((high - low) / 2);
if (sorted[mid] === target) return mid;
if (sorted[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}
const prices = [99, 149, 199, 249, 299, 349, 599];
console.log(binarySearch(prices, 299));
console.log(binarySearch(prices, 99));
console.log(binarySearch(prices, 100));
console.log(binarySearch([], 5));4
0
-1
-1Time: O(log n) · Space: O(1). Writing low + (high - low) / 2 instead of (low + high) / 2 avoids overflow in languages with fixed-size integers, and interviewers like seeing it. Watch the boundaries: low <= high, and mid ± 1 so the loop always shrinks.
I keep low and high bounds, compare the middle element with the target, and move one bound past the middle to discard half each time, stopping when they cross. It's O(log n) and only works on sorted data.
Likely follow-up: How would you find where the target should be inserted if it's missing?
First and last position of a target
In a sorted array with duplicates, find the first and last index of target, in O(log n).
Idea: run binary search twice. When you find the target, don't stop: keep searching left for the first occurrence, or right for the last.
function findBound(nums, target, findFirst) {
let low = 0;
let high = nums.length - 1;
let result = -1;
while (low <= high) {
const mid = (low + high) >> 1;
if (nums[mid] === target) {
result = mid;
if (findFirst) high = mid - 1;
else low = mid + 1;
} else if (nums[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
const searchRange = (nums, target) => [findBound(nums, target, true), findBound(nums, target, false)];
console.log(searchRange([5, 7, 7, 8, 8, 8, 10], 8).join(","));
console.log(searchRange([5, 7, 7, 8, 8, 10], 6).join(","));
console.log(searchRange([2, 2, 2], 2).join(","));3,5
-1,-1
0,2Last − first + 1 also gives the count of the target in O(log n). Time: O(log n) · Space: O(1).
I run two binary searches. When the middle equals the target, I record it and keep searching to the left for the first occurrence, or to the right for the last. Both are O(log n), and their difference gives the count.
Likely follow-up: How would you count elements in a value range [a, b] in a sorted array?
All 80 problems in the ebook
Big O in plain words
- What is Big O notation?
- How do you work out the time complexity of a piece of code?
- What does O(log n) mean?
- What is space complexity?
- What are best, average and worst case?
- What does amortised O(1) mean?
- What are the complexities of common JavaScript operations?
- What is the complexity of naive recursive Fibonacci?
Arrays and strings
- Maximum subarray sum (Kadane's algorithm)
- Move all zeroes to the end
- Best time to buy and sell a stock
- Product of array except self
- Spiral order of a matrix
- Merge overlapping intervals
- Longest common prefix
- Reverse the words in a sentence
- String compression
- Longest palindromic substring
- Pascal's triangle
- Majority element (Boyer-Moore voting)
- Plus one
- Leaders in an array
- Equilibrium index
- Find the missing and repeating numbers
Hashing and two pointers
- Two sum (unsorted array)
- Two sum on a sorted array (two pointers)
- Three sum
- Container with most water
- Longest substring without repeating characters
- Subarray sum equals k
- Group anagrams
- Top K frequent elements
- Longest consecutive sequence
- Remove duplicates from a sorted array in place
- Is one string a subsequence of another?
- Minimum size subarray with sum at least target
- Intersection of two arrays
- Contains a duplicate within k positions
- Trapping rain water
- Isomorphic strings
Stacks, queues and linked lists
- Implement a stack
- Min stack
- Next greater element
- Evaluate an expression in Reverse Polish Notation
- Implement a queue using two stacks
- Sliding window maximum
- Implement a singly linked list
- Reverse a linked list
- Detect a cycle in a linked list
- Find the middle of a linked list
- Merge two sorted linked lists
- Remove the nth node from the end
- Check whether a linked list is a palindrome
- Simplify a Unix file path
Trees and recursion
- Preorder, inorder and postorder traversal
- Level order traversal (breadth-first search)
- Maximum depth of a binary tree
- Invert a binary tree
- Check whether a tree is symmetric
- Validate a binary search tree
- Lowest common ancestor in a binary search tree
- Path sum
- Diameter of a binary tree
- Insert into and search a binary search tree
- Generate all subsets
- Generate all permutations of a string
- Tower of Hanoi
- Number of islands
Sorting and searching
- Binary search
- First and last position of a target
- Search in a rotated sorted array
- Integer square root with binary search
- Bubble sort
- Insertion sort
- Merge sort
- Quick sort
- Sort an array of 0s, 1s and 2s (Dutch national flag)
- Kth largest element (quickselect)
- Find a peak element
- Sort objects by several fields