JioCoder 450 DSA Concepts, Part 1: Basics to Stacks (Phases 1–9)
Concept lessons for Phases 1 to 9 of the JioCoder 450 DSA roadmap: basics, sorting, binary search, linked lists, recursion, bits and stacks, with JavaScript code.
This is Part 1 of the concept lessons for the JioCoder 450 DSA Roadmap. It covers Phases 1 to 9. Each lesson explains the idea, the key points to remember, its time complexity and a JavaScript implementation. The numbers match the question numbers in the roadmap checklist.
Phase 1: Foundations#
1. User Input / Output#
Every program reads data, works on it and prints a result. On coding platforms the input arrives as text (usually through standard input) and you print the answer to standard output.
- In the browser you read with
prompt()and print withconsole.log(). In Node.js you read the whole input withfs.readFileSync(0, 'utf8'). - Input is always text. Convert it with
Number()orparseInt()before doing maths, otherwise'2' + '3'gives'23'. - Most platforms (LeetCode, GFG function problems) hand you the input as function arguments, so you only write the function and return the answer.
const fs = require('fs');
const [a, b] = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
console.log(a + b);2. Data Types#
A data type tells the computer what kind of value a variable holds and what you can do with it.
- JavaScript primitives:
number,bigint,string,boolean,undefined,null,symbol. Everything else (arrays, objects, functions) is an object. numberis a 64-bit float. Integers are exact only up to 2^53 - 1 (Number.MAX_SAFE_INTEGER). Beyond that, useBigInt(e.g.10n ** 20n).- In C++/Java,
intholds about ±2.1 × 10^9 andlong long/longabout ±9.2 × 10^18. Overflow is a common bug in DSA problems, so check the constraints. - Use
typeof xto check a type.typeof nullreturns'object', a well-known quirk.
let n = 42; // number
let big = 2n ** 64n; // bigint
let s = "dsa"; // string
let ok = true; // boolean
console.log(typeof n, typeof big, typeof s, typeof ok);3. If Else statements#
if / else if / else runs different code depending on a condition. It's how a program makes decisions.
- Conditions are checked from top to bottom; the first true branch runs and the rest are skipped.
- Use
===(strict equality) in JavaScript, not==, to avoid type coercion surprises like0 == ''being true. - Falsy values in JS:
false,0,'',null,undefined,NaN. Everything else is truthy. - For simple two-way choices, the ternary
cond ? a : bkeeps code short.
function grade(marks) {
if (marks >= 90) return 'A';
else if (marks >= 75) return 'B';
else if (marks >= 50) return 'C';
else return 'Fail';
}4. Switch Statement#
switch compares one value against many fixed cases. It's cleaner than a long chain of if / else if when you're matching exact values.
- Each
caseneeds abreak, otherwise execution falls through into the next case. defaultruns when no case matches.- JavaScript
switchuses strict comparison (===). - Use it for menus, day names, operator handling (
+ - * /) and similar exact matches.
function calc(a, op, b) {
switch (op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
default: throw new Error('Unknown operator');
}
}5. What are arrays, strings?#
An array stores many values in order, each reachable by an index starting at 0. A string is a sequence of characters, which behaves much like a read-only array of characters.
- Reading or writing
arr[i]is O(1). Inserting or deleting in the middle is O(n) because the other elements shift. push/popat the end are O(1);shift/unshiftat the start are O(n).- JavaScript strings are immutable:
s[0] = 'x'does nothing. Build a new string, or convert to an array withs.split(''), change it, thenjoin(''). - Building a string with
+=in a loop is fine for small inputs; for large ones, collect parts in an array andjoinonce.
const arr = [5, 3, 8];
arr.push(1); // [5, 3, 8, 1]
const s = "hello";
const rev = s.split('').reverse().join(''); // "olleh"
console.log(arr[2], s.length, rev);6. For loops#
A for loop repeats a block a known number of times. It has three parts: start, condition and update.
for (let i = 0; i < n; i++)runs n times, with i going 0 to n-1.for...ofloops over values (arrays, strings);for...inloops over keys and shouldn't be used on arrays.- Nested loops multiply work: two nested loops over n items do n² steps. This is where time complexity starts to matter.
breakexits the loop;continueskips to the next iteration.
// sum of 1..n
let sum = 0;
for (let i = 1; i <= 10; i++) sum += i;
for (const ch of "abc") console.log(ch);7. While loops#
A while loop repeats as long as a condition is true. Use it when you don't know in advance how many times it will run.
- Make sure something inside the loop moves it toward stopping, or it runs forever.
do...whileruns the body at least once before checking the condition.- Classic uses: processing digits of a number, two-pointer scans, reading until input ends.
// count digits of n
function countDigits(n) {
n = Math.abs(n);
let count = 0;
do { count++; n = Math.floor(n / 10); } while (n > 0);
return count;
}8. Functions (Pass by Reference and Value)#
A function is a named, reusable block of code that takes inputs (parameters) and can return an output.
- Pass by value: the function gets a copy. Changing it inside doesn't affect the caller. In JS, primitives (numbers, strings, booleans) behave this way.
- Pass by reference: the function gets access to the original. In JS, objects and arrays are passed as a copy of the reference, so mutating them (
arr.push(1)) affects the caller. - Reassigning the parameter (
arr = []) inside the function does not change the caller's variable. - In C++,
void f(int &x)passes by reference;void f(int x)passes by value.
function changeNum(x) { x = 100; }
function changeArr(a) { a.push(4); }
let n = 1, arr = [1, 2, 3];
changeNum(n); // n is still 1
changeArr(arr); // arr is now [1, 2, 3, 4]9. Time Complexity#
Time complexity describes how the running time of an algorithm grows as the input size n grows. We write it in Big-O notation and care about the worst case.
- Drop constants and smaller terms: 3n² + 5n + 2 becomes O(n²).
- Common orders, fastest to slowest: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!).
- A loop over n items is O(n). Two nested loops are O(n²). Halving the range each step (binary search) is O(log n).
- Rule of thumb: about 10⁸ simple operations run in one second. If n = 10⁵, O(n²) = 10¹⁰ is too slow, but O(n log n) is fine.
- Space complexity measures extra memory in the same way.
Complexity: n ≤ 10 → O(n!) ok · n ≤ 20 → O(2ⁿ) · n ≤ 500 → O(n³) · n ≤ 10⁴ → O(n²) · n ≤ 10⁶ → O(n log n) · larger → O(n) or O(log n)
// O(n)
for (let i = 0; i < n; i++) {}
// O(n^2)
for (let i = 0; i < n; i++) for (let j = 0; j < n; j++) {}
// O(log n)
for (let i = 1; i < n; i *= 2) {}10. Patterns#
Pattern problems (stars, numbers, letters printed in triangles and pyramids) train you to control nested loops: the outer loop picks the row, the inner loops decide what goes in that row.
- Step 1: count the rows. That's the outer loop.
- Step 2: for one row i, work out how many spaces and how many symbols it has, written as a formula of i.
- Step 3: print spaces, then symbols, then a newline.
- Practise right triangles, inverted triangles, pyramids, diamonds, number triangles and hollow shapes until the row formula comes naturally.
// pyramid of height n
function pyramid(n) {
for (let i = 1; i <= n; i++) {
console.log(' '.repeat(n - i) + '*'.repeat(2 * i - 1));
}
}
pyramid(4);11. C++ STL#
The C++ Standard Template Library gives ready-made containers and algorithms so you don't write them from scratch in contests and interviews.
- Containers:
vector(dynamic array),stack,queue,deque,priority_queue(max-heap by default),set/map(sorted, O(log n)),unordered_set/unordered_map(hash, O(1) average). - Algorithms:
sort,reverse,lower_bound,upper_bound,max_element,accumulate,next_permutation. - JavaScript equivalents: Array for vector/stack/queue,
SetandMapfor hash set/map. JS has no built-in heap or sorted set, so you write a small heap class when needed.
// C++
// vector<int> v = {3,1,2}; sort(v.begin(), v.end());
// unordered_map<int,int> freq; freq[x]++;
// JavaScript equivalent
const v = [3, 1, 2].sort((a, b) => a - b);
const freq = new Map();
for (const x of v) freq.set(x, (freq.get(x) || 0) + 1);12. Java Collections#
Java's Collections Framework provides the standard data structures as classes, much like C++'s STL.
ArrayList(dynamic array),LinkedList,ArrayDeque(use for both stack and queue),PriorityQueue(min-heap by default).HashMap/HashSetgive O(1) average lookups;TreeMap/TreeSetkeep keys sorted with O(log n) operations.Collections.sort(),Arrays.sort()andCollections.reverse()cover most sorting needs.- If you code in JavaScript: Array, Map and Set cover most of this; write your own heap for priority-queue problems.
// Java
// PriorityQueue<Integer> pq = new PriorityQueue<>();
// Map<String,Integer> map = new HashMap<>();
// JavaScript
const map = new Map([["a", 1]]);
const seen = new Set([1, 2, 3]);
console.log(map.get("a"), seen.has(2));20. Understand recursion by print something N times#
Recursion is when a function calls itself to solve a smaller version of the same problem. Each call waits on the call stack until the smaller call returns.
- Every recursive function needs a base case that stops it. Without one you get a stack overflow.
- Each call must move toward the base case (for example n → n - 1).
- Draw a recursion tree for small inputs; it shows exactly which calls happen and in what order.
- Code before the recursive call runs on the way down; code after it runs on the way back up. That's why printing before vs after the call reverses the order.
function printN(i, n) {
if (i > n) return; // base case
console.log("JioCoder", i);
printN(i + 1, n); // smaller problem
}
printN(1, 5);29. Hashing Theory#
Hashing stores data so you can look it up in O(1) on average. A hash function turns a key into an index of an internal array where the value is kept.
- Precompute counts once, then answer each 'how many times does x appear?' query in O(1) instead of scanning the array every time.
- For small integer ranges, a plain array works as a hash:
count[x]++. For large or non-integer keys, use aMapor object. - Collisions happen when two keys map to the same index. They're handled by chaining (a list at each slot) or open addressing (probe for the next free slot).
- Worst case for a hash lookup is O(n) if everything collides, but on average it's O(1).
Complexity: Build: O(n) · Each lookup: O(1) average
function frequencies(arr) {
const freq = new Map();
for (const x of arr) freq.set(x, (freq.get(x) || 0) + 1);
return freq;
}
const f = frequencies([1, 2, 2, 3, 3, 3]);
console.log(f.get(3)); // 3Phase 2: Sorting#
32. Selection Sort#
Repeatedly find the smallest element in the unsorted part and swap it to the front.
- After pass i, the first i + 1 elements are sorted and final.
- Always does about n²/2 comparisons, even if the array is already sorted.
- Makes at most n - 1 swaps, useful when writes are expensive. Not stable.
Complexity: Time O(n²) in all cases · Space O(1)
function selectionSort(a) {
for (let i = 0; i < a.length - 1; i++) {
let min = i;
for (let j = i + 1; j < a.length; j++) if (a[j] < a[min]) min = j;
[a[i], a[min]] = [a[min], a[i]];
}
return a;
}33. Bubble Sort#
Compare neighbours and swap them if they're in the wrong order. After each pass the largest remaining element 'bubbles' to the end.
- Add a
swappedflag: if a whole pass makes no swaps, the array is sorted and you can stop early. - With that flag, the best case on an already sorted array is O(n).
- Stable: equal elements keep their order.
Complexity: Time O(n²) worst/average, O(n) best · Space O(1)
function bubbleSort(a) {
for (let i = a.length - 1; i > 0; i--) {
let swapped = false;
for (let j = 0; j < i; j++) {
if (a[j] > a[j + 1]) { [a[j], a[j + 1]] = [a[j + 1], a[j]]; swapped = true; }
}
if (!swapped) break;
}
return a;
}34. Insertion Sort#
Build the sorted part one element at a time: take the next element and shift larger elements right until you find its place.
- Works like sorting playing cards in your hand.
- Very fast on nearly sorted data (close to O(n)), which is why real sort functions use it for small chunks.
- Stable and in-place.
Complexity: Time O(n²) worst, O(n) best · Space O(1)
function insertionSort(a) {
for (let i = 1; i < a.length; i++) {
const key = a[i];
let j = i - 1;
while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; }
a[j + 1] = key;
}
return a;
}35. Merge Sort#
Divide and conquer: split the array in half, sort each half recursively, then merge the two sorted halves.
- Merging two sorted arrays takes O(n) with two pointers.
- There are log n levels of splitting, each doing O(n) merge work, so total O(n log n) in every case.
- Stable, but needs O(n) extra space for merging.
- The merge step is reused in Count Inversions and Reverse Pairs.
Complexity: Time O(n log n) always · Space O(n)
function mergeSort(a) {
if (a.length <= 1) return a;
const mid = a.length >> 1;
const L = mergeSort(a.slice(0, mid)), R = mergeSort(a.slice(mid));
const out = [];
let i = 0, j = 0;
while (i < L.length && j < R.length) out.push(L[i] <= R[j] ? L[i++] : R[j++]);
return out.concat(L.slice(i), R.slice(j));
}36. Recursive Bubble Sort#
Same idea as bubble sort, written with recursion: one pass pushes the largest element to the end, then recurse on the first n - 1 elements.
- Base case: an array of size 1 is sorted.
- Good practice for turning a loop into recursion.
- Same complexity as normal bubble sort, plus O(n) stack space.
Complexity: Time O(n²) · Space O(n) recursion stack
function bubbleRec(a, n = a.length) {
if (n <= 1) return a;
for (let j = 0; j < n - 1; j++)
if (a[j] > a[j + 1]) [a[j], a[j + 1]] = [a[j + 1], a[j]];
return bubbleRec(a, n - 1);
}37. Recursive Insertion Sort#
Sort the first n - 1 elements recursively, then insert the nth element into its correct place.
- Base case: n ≤ 1.
- The insertion step is exactly the inner loop of normal insertion sort.
Complexity: Time O(n²) · Space O(n) recursion stack
function insertionRec(a, n = a.length) {
if (n <= 1) return a;
insertionRec(a, n - 1);
const key = a[n - 1];
let j = n - 2;
while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; }
a[j + 1] = key;
return a;
}38. Quick Sort#
Pick a pivot, partition the array so smaller elements go left and larger go right, then recursively sort both sides.
- After partitioning, the pivot is in its final sorted position.
- Average O(n log n). Worst case O(n²) happens when the pivot is always the smallest or largest (e.g. sorted input with first-element pivot). A random pivot avoids this in practice.
- In-place and usually faster than merge sort in practice, but not stable.
Complexity: Time O(n log n) average, O(n²) worst · Space O(log n) stack
function quickSort(a, lo = 0, hi = a.length - 1) {
if (lo >= hi) return a;
const pivot = a[hi];
let i = lo;
for (let j = lo; j < hi; j++) if (a[j] < pivot) { [a[i], a[j]] = [a[j], a[i]]; i++; }
[a[i], a[hi]] = [a[hi], a[i]];
quickSort(a, lo, i - 1);
quickSort(a, i + 1, hi);
return a;
}Phase 3: Arrays#
46. Linear Search#
Check each element one by one until you find the target or reach the end.
- Works on any array, sorted or not.
- Return the index when found, or -1 if not found.
Complexity: Time O(n) · Space O(1)
function linearSearch(a, x) {
for (let i = 0; i < a.length; i++) if (a[i] === x) return i;
return -1;
}56. Kadane's Algorithm, maximum subarray sum#
Walk through the array keeping a running sum. If the running sum becomes negative, drop it and start fresh, because a negative prefix can only make later subarrays smaller.
- Track
best(answer so far) andcur(best sum of a subarray ending here). cur = max(a[i], cur + a[i])is the whole idea.- Handles all-negative arrays if you initialise
bestwitha[0], not 0. - To print the subarray, remember where
curwas last reset.
Complexity: Time O(n) · Space O(1)
function maxSubArray(a) {
let best = a[0], cur = 0;
for (const x of a) {
cur = Math.max(x, cur + x);
best = Math.max(best, cur);
}
return best;
}Phase 4: Binary Search#
79. Binary Search to find X in sorted array#
On a sorted array, look at the middle element. If it's the target you're done; if it's smaller, the target can only be on the right; otherwise on the left. Each step throws away half the range.
- Keep
loandhi, loop whilelo <= hi. - Compute mid as
lo + ((hi - lo) >> 1)to avoid overflow in other languages. - Only works when the data is sorted (or more generally, monotonic).
Complexity: Time O(log n) · Space O(1)
function binarySearch(a, x) {
let lo = 0, hi = a.length - 1;
while (lo <= hi) {
const mid = lo + ((hi - lo) >> 1);
if (a[mid] === x) return mid;
if (a[mid] < x) lo = mid + 1; else hi = mid - 1;
}
return -1;
}80. Implement Lower Bound#
Lower bound is the first index where a[i] >= x. If every element is smaller, it's n.
- Binary search, but when
a[mid] >= xyou record mid as a possible answer and keep searching left. - It's also the position where x should be inserted to keep the array sorted (Search Insert Position).
- Floor, ceil, first occurrence and count of occurrences are all small variations of lower and upper bound.
Complexity: Time O(log n)
function lowerBound(a, x) {
let lo = 0, hi = a.length - 1, ans = a.length;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (a[mid] >= x) { ans = mid; hi = mid - 1; } else lo = mid + 1;
}
return ans;
}81. Implement Upper Bound#
Upper bound is the first index where a[i] > x (strictly greater).
- Same code as lower bound with
>=changed to>. upperBound(x) - lowerBound(x)gives the number of times x appears in a sorted array.
Complexity: Time O(log n)
function upperBound(a, x) {
let lo = 0, hi = a.length - 1, ans = a.length;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (a[mid] > x) { ans = mid; hi = mid - 1; } else lo = mid + 1;
}
return ans;
}92. Find square root of a number in log n#
This is the first 'binary search on the answer' problem. The answer lies in a range [1, n], and the check 'is mid * mid <= n?' is true up to some point and false after it. Binary search finds that boundary.
- Pattern: define the answer range, write a yes/no check for a candidate, make sure the check is monotonic, then binary search.
- The same template solves Koko Eating Bananas, Aggressive Cows, Book Allocation, Capacity to Ship Packages and more.
- For 'minimise the maximum' problems, search for the smallest value where the check passes. For 'maximise the minimum', the largest.
Complexity: Time O(log n)
function sqrtFloor(n) {
let lo = 1, hi = n, ans = 0;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (mid * mid <= n) { ans = mid; lo = mid + 1; } else hi = mid - 1;
}
return ans;
}Phase 6: Linked List#
126. Introduction to LinkedList#
A linked list stores elements in nodes. Each node holds a value and a pointer to the next node. Unlike arrays, nodes aren't next to each other in memory.
- The list is reached through its
head. The last node points tonull. - Insert or delete at the head is O(1). Accessing the kth element is O(k) because you must walk from the head.
- Used where frequent inserts/deletes matter: LRU caches, browser history, undo stacks.
- Converting an array to a linked list is a good first exercise.
Complexity: Access O(n) · Insert/delete at head O(1)
class Node {
constructor(val, next = null) { this.val = val; this.next = next; }
}
function fromArray(arr) {
const dummy = new Node(0);
let tail = dummy;
for (const x of arr) { tail.next = new Node(x); tail = tail.next; }
return dummy.next;
}127. Inserting a node in LinkedList#
To insert, create a new node and fix two pointers: the new node points to the next node, and the previous node points to the new node.
- At head:
newNode.next = head; head = newNode. - At position k: walk to node k - 1, then rewire.
- At tail: walk to the last node (O(n)) unless you keep a tail pointer.
- Always set
newNode.nextfirst so you don't lose the rest of the list.
Complexity: Head O(1) · Position k O(k)
function insertAt(head, k, val) { // k is 0-based
if (k === 0) return new Node(val, head);
let cur = head;
for (let i = 0; i < k - 1 && cur; i++) cur = cur.next;
if (cur) cur.next = new Node(val, cur.next);
return head;
}128. Deleting a node in LinkedList#
To delete a node, make the previous node skip it: prev.next = prev.next.next.
- Deleting the head:
head = head.next. - A dummy node before the head removes the special case for deleting the head.
- If you're given only the node to delete (not the head), copy the next node's value into it and delete the next node instead.
Complexity: Time O(n) to find the node, O(1) to unlink
function deleteValue(head, val) {
const dummy = new Node(0, head);
let prev = dummy;
while (prev.next && prev.next.val !== val) prev = prev.next;
if (prev.next) prev.next = prev.next.next;
return dummy.next;
}131. Introduction to DLL#
A doubly linked list (DLL) node has two pointers: next and prev. You can walk in both directions and delete a node in O(1) if you already hold it.
- Every insert or delete updates up to four pointers, so draw it before coding.
- Costs more memory per node than a singly linked list.
- Used in LRU Cache (a hash map plus a DLL) and browser back/forward history.
class DNode {
constructor(val) { this.val = val; this.prev = null; this.next = null; }
}
function dllFromArray(arr) {
let head = null, tail = null;
for (const x of arr) {
const n = new DNode(x);
if (!head) head = tail = n;
else { tail.next = n; n.prev = tail; tail = n; }
}
return head;
}135. Middle of a LinkedList (Tortoise-Hare)#
Use two pointers: slow moves one step, fast moves two. When fast reaches the end, slow is at the middle. This 'tortoise and hare' trick is used across many linked list problems.
- Also detects cycles: if fast ever meets slow, there's a loop.
- With an even number of nodes, this version returns the second middle.
Complexity: Time O(n) · Space O(1)
function middle(head) {
let slow = head, fast = head;
while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
return slow;
}Phase 7: Recursion & Backtracking#
165. Learn All Patterns of Subsequences (Theory)#
A subsequence keeps some elements in their original order. For each element you make one choice: pick it or don't pick it. That gives 2ⁿ subsequences and a recursion tree with two branches at every level.
- Print all: at index i, recurse once with the element added, once without.
- Print one that satisfies a condition: return true from the recursion as soon as one is found and stop exploring.
- Count how many satisfy a condition: return 1 at a valid base case, 0 otherwise, and add the results of both branches.
- This pick / not-pick tree is the foundation of subset, combination-sum and later DP on subsequences.
Complexity: Time O(2ⁿ) · Space O(n) recursion depth
function subsequences(a) {
const res = [];
(function go(i, cur) {
if (i === a.length) { res.push([...cur]); return; }
cur.push(a[i]); go(i + 1, cur); // pick
cur.pop(); go(i + 1, cur); // not pick
})(0, []);
return res;
}Phase 8: Bit Manipulation#
182. Introduction to Bit Manipulation (Theory)#
Computers store numbers in binary. Bit manipulation works directly on those bits with operators that run in O(1).
&(AND): 1 only if both bits are 1.|(OR): 1 if either is 1.^(XOR): 1 if the bits differ.~(NOT) flips all bits.x << kmultiplies by 2ᵏ;x >> kdivides by 2ᵏ (floor).- Check bit i:
(x >> i) & 1. Set bit i:x | (1 << i). Clear bit i:x & ~(1 << i). Toggle:x ^ (1 << i). - XOR facts:
a ^ a = 0,a ^ 0 = a, and order doesn't matter. That's why XOR-ing all elements finds the one that appears once. x & (x - 1)removes the lowest set bit, so it's 0 exactly when x is a power of 2.- Negative numbers use two's complement:
-x = ~x + 1. In JavaScript, bit operators work on 32-bit integers.
const x = 13; // 1101
console.log((x >> 2) & 1); // bit 2 is 1
console.log(x & (x - 1)); // 12 (1100), lowest set bit removed
console.log([4, 1, 2, 1, 2].reduce((a, b) => a ^ b)); // 4197. Sieve of Eratosthenes#
Find all primes up to n by crossing out multiples. Start with every number marked prime; for each prime p, mark p², p² + p, p² + 2p, ... as not prime.
- You only need to loop p up to √n, because any composite ≤ n has a factor ≤ √n.
- Start crossing from p² because smaller multiples were already crossed by smaller primes.
- Storing the smallest prime factor (SPF) instead of true/false lets you factorise any number ≤ n in O(log n).
Complexity: Time O(n log log n) · Space O(n)
function sieve(n) {
const isPrime = new Array(n + 1).fill(true);
isPrime[0] = isPrime[1] = false;
for (let p = 2; p * p <= n; p++)
if (isPrime[p]) for (let m = p * p; m <= n; m += p) isPrime[m] = false;
return isPrime;
}Phase 9: Stack & Queue#
200. Implement Stack using Arrays#
A stack is Last In, First Out (LIFO): the last item pushed is the first popped, like a stack of plates.
- Operations: push, pop, top/peek, isEmpty, all O(1).
- With a fixed-size array, keep an index
top. Pushing when full is overflow; popping when empty is underflow. - Used for undo, the browser back button, function calls, bracket matching and expression evaluation.
Complexity: All operations O(1)
class Stack {
constructor() { this.a = []; }
push(x) { this.a.push(x); }
pop() { return this.a.length ? this.a.pop() : -1; }
top() { return this.a.length ? this.a[this.a.length - 1] : -1; }
isEmpty() { return this.a.length === 0; }
}201. Implement Queue using Arrays#
A queue is First In, First Out (FIFO): items leave in the order they arrived, like a line at a ticket counter.
- Keep two indexes:
front(next to remove) andrear(where to add). - A circular array (
rear = (rear + 1) % size) reuses space freed at the front. - In JavaScript,
array.shift()is O(n). For big queues, use a head index instead of shifting. - Queues power BFS, task scheduling and print queues.
Complexity: Enqueue/dequeue O(1)
class Queue {
constructor() { this.a = []; this.head = 0; }
push(x) { this.a.push(x); }
pop() { return this.head < this.a.length ? this.a[this.head++] : -1; }
size() { return this.a.length - this.head; }
}208. Infix to Postfix Conversion#
Infix is how we write maths (a + b * c). Postfix puts the operator after its operands (a b c * +) and needs no brackets, which makes it easy for a computer to evaluate with a stack.
- Prefix puts the operator first:
+ a * b c. - Infix → postfix: output operands directly. For an operator, pop operators of higher or equal precedence from the stack first, then push it.
(is pushed; on), pop until(. - Evaluating postfix: push numbers; on an operator, pop two, apply, push the result.
- All six conversions (infix, prefix, postfix in each direction) use a stack in a similar way.
Complexity: Time O(n) · Space O(n)
function infixToPostfix(s) {
const prec = { '^': 3, '*': 2, '/': 2, '+': 1, '-': 1 };
const st = [], out = [];
for (const c of s) {
if (/[a-z0-9]/i.test(c)) out.push(c);
else if (c === '(') st.push(c);
else if (c === ')') { while (st.at(-1) !== '(') out.push(st.pop()); st.pop(); }
else {
while (st.length && st.at(-1) !== '(' && prec[st.at(-1)] >= prec[c] && c !== '^') out.push(st.pop());
st.push(c);
}
}
while (st.length) out.push(st.pop());
return out.join('');
}214. Next Greater Element#
This introduces the monotonic stack: a stack whose elements stay in increasing or decreasing order. It answers 'what is the next greater/smaller element?' for every position in one pass.
- Scan from the right. Pop every stack element ≤ the current one (they can never be the answer for anything to the left). The stack top is now the next greater element. Push the current element.
- Each element is pushed and popped at most once, so the whole thing is O(n).
- The same pattern solves Next Smaller Element, Stock Span, Largest Rectangle in Histogram, Trapping Rain Water and Sum of Subarray Minimums.
Complexity: Time O(n) · Space O(n)
function nextGreater(a) {
const res = new Array(a.length).fill(-1), st = [];
for (let i = a.length - 1; i >= 0; i--) {
while (st.length && st.at(-1) <= a[i]) st.pop();
if (st.length) res[i] = st.at(-1);
st.push(a[i]);
}
return res;
}Go back to the JioCoder 450 roadmap to tick off the problems, or continue with Concepts Part 2 (Phases 10 to 18).
Key takeaways#
- Big-O tells you whether a solution will pass before you write it.
- Merge sort and quick sort are the sorting algorithms interviews care about.
- Binary search works on any monotonic yes/no check, not just sorted arrays.
- Linked list problems are pointer problems: draw them first.
- Every subset problem is a pick / not-pick recursion tree.