Skip to main content
FREE Mock interview & resume review with Sumit. Free right now, no payment needed.Book a slot

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.

Sumit KumarUpdated Oct 22, 202624 min readDSA
JioCoder 450 DSA Concepts, Part 1: Basics to Stacks (Phases 1–9)

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 with console.log(). In Node.js you read the whole input with fs.readFileSync(0, 'utf8').
  • Input is always text. Convert it with Number() or parseInt() 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.
JavaScript
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.
  • number is a 64-bit float. Integers are exact only up to 2^53 - 1 (Number.MAX_SAFE_INTEGER). Beyond that, use BigInt (e.g. 10n ** 20n).
  • In C++/Java, int holds about ±2.1 × 10^9 and long long/long about ±9.2 × 10^18. Overflow is a common bug in DSA problems, so check the constraints.
  • Use typeof x to check a type. typeof null returns 'object', a well-known quirk.
JavaScript
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 like 0 == '' being true.
  • Falsy values in JS: false, 0, '', null, undefined, NaN. Everything else is truthy.
  • For simple two-way choices, the ternary cond ? a : b keeps code short.
JavaScript
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 case needs a break, otherwise execution falls through into the next case.
  • default runs when no case matches.
  • JavaScript switch uses strict comparison (===).
  • Use it for menus, day names, operator handling (+ - * /) and similar exact matches.
JavaScript
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/pop at the end are O(1); shift/unshift at the start are O(n).
  • JavaScript strings are immutable: s[0] = 'x' does nothing. Build a new string, or convert to an array with s.split(''), change it, then join('').
  • Building a string with += in a loop is fine for small inputs; for large ones, collect parts in an array and join once.
JavaScript
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...of loops over values (arrays, strings); for...in loops 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.
  • break exits the loop; continue skips to the next iteration.
JavaScript
// 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...while runs the body at least once before checking the condition.
  • Classic uses: processing digits of a number, two-pointer scans, reading until input ends.
JavaScript
// 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.
JavaScript
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)

JavaScript
// 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.
JavaScript
// 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, Set and Map for hash set/map. JS has no built-in heap or sorted set, so you write a small heap class when needed.
JavaScript
// 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/HashSet give O(1) average lookups; TreeMap/TreeSet keep keys sorted with O(log n) operations.
  • Collections.sort(), Arrays.sort() and Collections.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.
JavaScript
// 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.
JavaScript
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 a Map or 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

JavaScript
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)); // 3

Phase 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)

JavaScript
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 swapped flag: 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)

JavaScript
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)

JavaScript
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)

JavaScript
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

JavaScript
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

JavaScript
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

JavaScript
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#

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)

JavaScript
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) and cur (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 best with a[0], not 0.
  • To print the subarray, remember where cur was last reset.

Complexity: Time O(n) · Space O(1)

JavaScript
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;
}

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 lo and hi, loop while lo <= 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)

JavaScript
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] >= x you 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)

JavaScript
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)

JavaScript
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)

JavaScript
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 to null.
  • 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)

JavaScript
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.next first so you don't lose the rest of the list.

Complexity: Head O(1) · Position k O(k)

JavaScript
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

JavaScript
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.
JavaScript
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)

JavaScript
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

JavaScript
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 << k multiplies by 2ᵏ; x >> k divides 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.
JavaScript
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)); // 4

197. 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)

JavaScript
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)

JavaScript
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) and rear (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)

JavaScript
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)

JavaScript
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)

JavaScript
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;
}
Next

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.

Article discussion

(0)

Join the discussion — login to comment and help other developers.

Login to comment