LogoBytesFor Developers
HomeBytesheetsRoadmapsUI TemplatesUI ToolsStack Discussion
10 Topics
Chapter•540 Minutes

Hard DSA — Advanced Data Structures & Algorithmic Specializations

Master specialized structures including Segment Trees, Binary Indexed Trees (Fenwick Trees), Tries with Wildcard Backtracking, Monotonic Stacks, and LFU/LRU Cache Engine designs.

01. Sliding Window Maximum

Difficulty:HardPattern:Monotonic DequeTime:O(n)Space:O(k)

You are given an array of integers nums, and a sliding window of size k moving from left to right. Return the max sliding window values.

How It Works & Algorithmic Design

Solves using Monotonic Decreasing Double-Ended Queue (Deque):

  1. Deque Invariant: Maintain index values in deque such that elements nums[deque[i]] are strictly decreasing.
  2. Window Processing (For index $i$ from $0$ to $n-1$):
    • Remove Out-of-Bound: If deque[0] <= i - k, pop front.
    • Maintain Decreasing Order: While nums[i] >= nums[deque[last]], pop back.
    • Push: deque.push(i).
    • Collect Max: If $i \ge k - 1$, push nums[deque[0]] to result.

Why This Approach Works Best

Maintains sliding window maximums in linear $O(n)$ time using $O(k)$ space without $O(n \log k)$ heap delays.

Example Walkthrough
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Sliding window length 3.
Window Maxes: [1,3,-1]->3, [3,-1,-3]->3, [-1,-3,5]->5, [-3,5,3]->5, [5,3,6]->6, [3,6,7]->7
Sub-array maximums.
Output: [3, 3, 5, 5, 6, 7]
Result array.

Answer: Sliding Window Maximum Monotonic Deque implementation

function maxSlidingWindow(nums, k) {
  const res = [];
  const deque = []; // Stores indices
  for (let i = 0; i < nums.length; i++) {
    if (deque.length && deque[0] <= i - k) deque.shift();
    while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) deque.pop();
    deque.push(i);
    if (i >= k - 1) res.push(nums[deque[0]]);
  }
  return res;
}
💡 Store indices in double-ended queue keeping corresponding values strictly decreasing.
Key Takeaways
  • Deque maintains element indices in strictly decreasing value order.
  • Front of deque always holds current window maximum.
  • Linear time complexity $O(n)$ as every index gets pushed and popped at most once.

02. Largest Rectangle in Histogram

Difficulty:HardPattern:Monotonic StackTime:O(n)Space:O(n)

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

How It Works & Algorithmic Design

Solves using Monotonic Increasing Stack:

  1. Sentinel Padding: Append height 0 at end of array to flush stack elements at conclusion.
  2. Stack Stores Indices: Maintain stack keeping corresponding heights in increasing order.
  3. Loop Bar Heights $i$:
    • While stack.top height is greater than heights[i]:
      • Pop height h = heights[stack.pop()].
      • Width = stack.isEmpty ? i : i - stack.top - 1.
      • maxArea = Math.max(maxArea, h * width).
    • Push current index $i$.

Why This Approach Works Best

Monotonic stack processes every bar height boundary in single-pass linear $O(n)$ time and $O(n)$ space.

Example Walkthrough
Input Heights: [2, 1, 5, 6, 2, 3]
Histogram bar heights.
Max Area Rectangle: Bars at idx 2 and 3 (heights 5, 6) form 5 * 2 = 10 area.
Largest rectangle bounded by height 5.
Output: 10
Max rectangular area.

Answer: Largest Rectangle in Histogram implementation

function largestRectangleArea(heights) {
  const stack = [];
  let maxArea = 0;
  const H = [...heights, 0];
  for (let i = 0; i < H.length; i++) {
    while (stack.length && H[stack[stack.length - 1]] > H[i]) {
      const h = H[stack.pop()];
      const w = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
      maxArea = Math.max(maxArea, h * w);
    }
    stack.push(i);
  }
  return maxArea;
}
💡 Use a monotonic increasing stack to calculate max rectangular area bounded by bar heights.
Key Takeaways
  • Stack elements are strictly increasing in height.
  • Trailing zero height flushes remaining stack elements.
  • Single pass linear $O(n)$ time and $O(n)$ space.

03. Maximal Rectangle in 2D Binary Matrix

Difficulty:HardPattern:2D Matrix to Histogram DPTime:O(m * n)Space:O(n)

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

How It Works & Algorithmic Design

Solves using Dynamic Row Histogram Updating + Histogram Stack:

  1. Histogram Array: Maintain dp array of size cols initialized to 0.
  2. Row Traversal: Loop row by row:
    • For each cell in row: if matrix[r][c] === '1', dp[c] += 1; else dp[c] = 0.
    • Calculate maxArea = Math.max(maxArea, largestRectangleArea(dp)) using Histogram Monotonic Stack.
  3. Return: Maximum overall area found.

Why This Approach Works Best

Transforms 2D matrix search into $M$ consecutive histogram sub-problems executing in optimal $O(M \times N)$ time and $O(N)$ space.

Example Walkthrough
Input Matrix: [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Binary grid.
Max Area: 3x2 rectangle of 1s yields 6 area.
Max contiguous rectangle.
Output: 6
Max rectangular area.

Answer: Maximal Rectangle implementation

function maximalRectangle(matrix) {
  if (!matrix.length || !matrix[0].length) return 0;
  const cols = matrix[0].length;
  const dp = new Array(cols).fill(0);
  let maxArea = 0;
  for (let r = 0; r < matrix.length; r++) {
    for (let c = 0; c < cols; c++) {
      dp[c] = matrix[r][c] === '1' ? dp[c] + 1 : 0;
    }
    maxArea = Math.max(maxArea, largestRectangleArea(dp));
  }
  return maxArea;
}

function largestRectangleArea(heights) {
  const stack = [];
  let maxArea = 0;
  const H = [...heights, 0];
  for (let i = 0; i < H.length; i++) {
    while (stack.length && H[stack[stack.length - 1]] > H[i]) {
      const h = H[stack.pop()];
      const w = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
      maxArea = Math.max(maxArea, h * w);
    }
    stack.push(i);
  }
  return maxArea;
}
💡 Build height array per matrix row and evaluate largest histogram rectangle.
Key Takeaways
  • Converts 2D matrix search into 1D dynamic histogram problems.
  • Resetting column height to 0 on matrix cell '0' enforces contiguous 1s.
  • Time complexity $O(M \times N)$.

04. LFU Cache (Least Frequently Used)

Difficulty:HardPattern:Doubly Linked List + MapTime:O(1) Get / PutSpace:O(capacity)

Design and implement a data structure for a Least Frequently Used (LFU) cache supporting get and put operations in $O(1)$ time complexity.

How It Works & Algorithmic Design

Solves using Hash Map + Doubly Linked Frequency Lists:

  1. Key Map: keyMap[key] = node (stores value, frequency, key reference).
  2. Frequency Map: freqMap[freq] = DoublyLinkedList (LRU ordered list for nodes sharing the same access frequency).
  3. Track Min Frequency: Maintain variable minFreq.
  4. Operations:
    • get(key): If present, increment node frequency, update doubly linked lists, update minFreq, return node value.
    • put(key, val): If key exists, update value and bump frequency. If new and full capacity reached, remove tail node from freqMap[minFreq]. Insert new node with frequency 1 and set minFreq = 1.

Why This Approach Works Best

Doubly linked frequency buckets achieve strict constant $O(1)$ time for both cache lookup and frequency displacement.

Example Walkthrough
Operations: put(1,1), put(2,2), get(1), put(3,3)
Capacity 2 LFU cache.
Eviction: key 2 has freq 1, key 1 has freq 2. Key 2 evicted when adding key 3.
Least frequent node removed.
Output: get(1)->1, get(2)->-1 (evicted), get(3)->3
Cache responses.

Answer: LFU Cache $O(1)$ implementation

class LFUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.minFreq = 0;
    this.keyMap = new Map();
    this.freqMap = new Map();
  }
  _update(node) {
    const oldFreq = node.freq;
    const oldList = this.freqMap.get(oldFreq);
    oldList.delete(node);
    if (oldFreq === this.minFreq && oldList.size === 0) this.minFreq++;
    node.freq++;
    if (!this.freqMap.has(node.freq)) this.freqMap.set(node.freq, new Set());
    this.freqMap.get(node.freq).add(node);
  }
  get(key) {
    if (!this.keyMap.has(key)) return -1;
    const node = this.keyMap.get(key);
    this._update(node);
    return node.val;
  }
  put(key, value) {
    if (this.capacity === 0) return;
    if (this.keyMap.has(key)) {
      const node = this.keyMap.get(key);
      node.val = value;
      this._update(node);
    } else {
      if (this.keyMap.size >= this.capacity) {
        const minList = this.freqMap.get(this.minFreq);
        const evictNode = minList.values().next().value;
        minList.delete(evictNode);
        this.keyMap.delete(evictNode.key);
      }
      const newNode = { key, val: value, freq: 1 };
      this.keyMap.set(key, newNode);
      this.minFreq = 1;
      if (!this.freqMap.has(1)) this.freqMap.set(1, new Set());
      this.freqMap.get(1).add(newNode);
    }
  }
}
💡 Store frequency nodes in doubly linked list buckets mapped by frequency keys for O(1) eviction.
Key Takeaways
  • Use frequency maps storing doubly linked lists to track duplicate frequency tie breaks.
  • Increments minFreq when lowest frequency bucket empties out.
  • Guarantees $O(1)$ operations for get and put.

05. Word Search II (Board Search with Trie)

Difficulty:HardPattern:Trie + Grid DFS BacktrackingTime:O(M * N * 4^L)Space:O(W * L)

Given an $m \times n$ board of characters and a list of strings words, return all words on the board.

How It Works & Algorithmic Design

Solves using Prefix Trie Tree + Grid Backtracking DFS:

  1. Build Prefix Trie: Insert all words into Trie. Store complete word reference at terminal leaf nodes.
  2. Grid Traversal DFS dfs(r, c, trieNode):
    • Base Case: if cell out of bounds or board[r][c] === '#' or character not in trieNode.children, return.
    • Matching Child: step into childNode.
    • Word Discovered: if childNode.word !== null, push to result and set childNode.word = null (prevents duplicates).
    • Mark visited board[r][c] = '#' and recurse 4 directions.
    • Restore cell board[r][c] = originalChar.

Why This Approach Works Best

Trie prefix matching prunes search paths across thousands of words simultaneously in $O(M \cdot N \cdot 4^L)$ worst-case.

Example Walkthrough
Input Grid: [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Grid and word dictionary.
Words Found: "oath", "eat"
Valid board word paths.
Output: ["oath", "eat"]
Discovered words.

Answer: Word Search II Trie implementation

function findWords(board, words) {
  const root = {};
  for (const w of words) {
    let node = root;
    for (const c of w) {
      if (!node[c]) node[c] = {};
      node = node[c];
    }
    node.word = w;
  }
  const res = [];
  const m = board.length, n = board[0].length;
  function dfs(r, c, node) {
    const ch = board[r][c];
    if (!node[ch]) return;
    node = node[ch];
    if (node.word) {
      res.push(node.word);
      node.word = null;
    }
    board[r][c] = '#';
    const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nc >= 0 && nr < m && nc < n && board[nr][nc] !== '#') {
        dfs(nr, nc, node);
      }
    }
    board[r][c] = ch;
  }
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      dfs(r, c, root);
    }
  }
  return res;
}
💡 Build Prefix Trie and perform 4-directional grid DFS backtracking to find matching words.
Key Takeaways
  • Store complete word string directly inside Trie leaf node.
  • Set node.word = null when found to avoid duplicate results.
  • Trie prefix checks prune invalid board branches fast.

06. Range Sum Query - Mutable (Segment Tree / Fenwick Tree)

Difficulty:HardPattern:Fenwick Tree / Segment TreeTime:O(log n) Update/QuerySpace:O(n)

Given an integer array nums, handle multiple queries of updating an element value and calculating the sum of elements between indices left and right inclusive.

How It Works & Algorithmic Design

Solves using a Binary Indexed Tree (Fenwick Tree / BIT):

  1. BIT Mechanics: Array tree of size $n+1$ storing prefix sums. Index index relationships use lowest set bit: i & (-i).
  2. update(index, val):
    • Delta = val - nums[index].
    • nums[index] = val.
    • Loop $i = \text{index} + 1$ up to $n$: tree[i] += delta, advance i += i & (-i).
  3. sumRange(left, right):
    • Query prefix sum $Q(x)$: sum tree[i] stepping down i -= i & (-i).
    • Return $Q(\text{right} + 1) - Q(\left\text{left}\right)$.

Why This Approach Works Best

Achieves logarithmic $O(\log n)$ time for both updates and range sum queries with minimal $O(n)$ space.

Example Walkthrough
Operations: nums = [1,3,5] -> sumRange(0,2) -> update(1,2) -> sumRange(0,2)
Dynamic range queries.
Results: sumRange(0,2)=9. After update index 1 to 2, sumRange(0,2)=8.
Updated sum range.
Output: [9, 8]
Query outputs.

Answer: Fenwick Tree / Binary Indexed Tree implementation

class NumArray {
  constructor(nums) {
    this.n = nums.length;
    this.nums = [...nums];
    this.tree = new Array(this.n + 1).fill(0);
    for (let i = 0; i < this.n; i++) {
      this._initAdd(i + 1, nums[i]);
    }
  }
  _initAdd(i, val) {
    while (i <= this.n) {
      this.tree[i] += val;
      i += i & (-i);
    }
  }
  update(index, val) {
    const delta = val - this.nums[index];
    this.nums[index] = val;
    let i = index + 1;
    while (i <= this.n) {
      this.tree[i] += delta;
      i += i & (-i);
    }
  }
  _prefixSum(i) {
    let sum = 0;
    while (i > 0) {
      sum += this.tree[i];
      i -= i & (-i);
    }
    return sum;
  }
  sumRange(left, right) {
    return this._prefixSum(right + 1) - this._prefixSum(left);
  }
}
💡 Construct Binary Indexed Tree using bitwise least significant bit operations for dynamic range sums.
Key Takeaways
  • Fenwick Tree allows $O(\log n)$ point updates and $O(\log n)$ range queries.
  • Bitwise lowest set bit operator i & (-i) navigates tree parent/child paths.
  • Simpler to write than 4x size Segment Trees.

07. Count of Smaller Numbers After Self

Difficulty:HardPattern:Modified Merge SortTime:O(n log n)Space:O(n)

Given an integer array nums, return an integer array counts where counts[i] is the number of smaller elements to the right of nums[i].

How It Works & Algorithmic Design

Solves using Modified Merge Sort with Right-Side Inversion Counting:

  1. Index Tracking: Create array of index pairs [value, originalIndex].
  2. Merge Step: Merge sorted left half and right half:
    • When picking element from left half because left[i].val <= right[j].val:
      • Accumulate count: counts[left[i].index] += rightCount (number of elements taken from right half so far).
    • When picking element from right half: increment rightCount++.
  3. Return: Populated counts array.

Why This Approach Works Best

Merge sort counts inversions across array splits in optimal $O(n \log n)$ time and $O(n)$ space.

Example Walkthrough
Input: [5, 2, 6, 1]
Target array.
Right Smaller Counts: 5 has 2 smaller (2,1); 2 has 1 smaller (1); 6 has 1 smaller (1); 1 has 0
Count per element.
Output: [2, 1, 1, 0]
Result array.

Answer: Count Smaller Numbers Merge Sort implementation

function countSmaller(nums) {
  const n = nums.length;
  const counts = new Array(n).fill(0);
  const items = nums.map((val, idx) => ({ val, idx }));
  function mergeSort(arr) {
    if (arr.length <= 1) return arr;
    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
    const merged = [];
    let i = 0, j = 0, rightCount = 0;
    while (i < left.length && j < right.length) {
      if (right[j].val < left[i].val) {
        rightCount++;
        merged.push(right[j++]);
      } else {
        counts[left[i].idx] += rightCount;
        merged.push(left[i++]);
      }
    }
    while (i < left.length) {
      counts[left[i].idx] += rightCount;
      merged.push(left[i++]);
    }
    while (j < right.length) merged.push(right[j++]);
    return merged;
  }
  mergeSort(items);
  return counts;
}
💡 Count right-side smaller element inversions during Merge Sort index array consolidation.
Key Takeaways
  • Tracks original indices using value-index object pairs.
  • Increments rightCount whenever smaller element from right sub-array is merged first.
  • Optimal $O(n \log n)$ runtime.

08. Median of Two Sorted Arrays

Difficulty:HardPattern:Binary Search PartitionTime:O(log(min(m, n)))Space:O(1)

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays in $O(\log(\min(m, n)))$ time.

How It Works & Algorithmic Design

Solves using Binary Search Partitioning on Shorter Array:

  1. Ensure Shorter Array: Swap arrays if nums1.length > nums2.length so nums1 is shorter.
  2. Binary Search: Search partition point $i$ in nums1 between $0$ and $m$:
    • Set j = Math.floor((m + n + 1) / 2) - i in nums2.
    • Calculate boundary values: maxLeft1, minRight1, maxLeft2, minRight2.
  3. Partition Check:
    • If maxLeft1 <= minRight2 and maxLeft2 <= minRight1, valid median partition found!
    • Odd combined length: median = Math.max(maxLeft1, maxLeft2).
    • Even combined length: median = (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.
    • If maxLeft1 > minRight2: move search left (high = i - 1).
    • Else: move search right (low = i + 1).

Why This Approach Works Best

Halves partition choices on smaller array achieving optimal $O(\log(\min(m, n)))$ runtime.

Example Walkthrough
Input Arrays: nums1 = [1, 3], nums2 = [2]
Sorted arrays.
Merged Order: [1, 2, 3]
Median is middle element 2.
Output: 2.0
Combined median.

Answer: Median of Two Sorted Arrays implementation

function findMedianSortedArrays(nums1, nums2) {
  if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
  const m = nums1.length, n = nums2.length;
  let low = 0, high = m;
  while (low <= high) {
    const i = Math.floor((low + high) / 2);
    const j = Math.floor((m + n + 1) / 2) - i;
    const maxLeft1 = i === 0 ? -Infinity : nums1[i - 1];
    const minRight1 = i === m ? Infinity : nums1[i];
    const maxLeft2 = j === 0 ? -Infinity : nums2[j - 1];
    const minRight2 = j === n ? Infinity : nums2[j];
    if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
      if ((m + n) % 2 === 1) return Math.max(maxLeft1, maxLeft2);
      return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2;
    } else if (maxLeft1 > minRight2) {
      high = i - 1;
    } else {
      low = i + 1;
    }
  }
  return 0.0;
}
💡 Binary search partition indices on shorter array to divide total elements into balanced left/right halves.
Key Takeaways
  • Always run binary search on the shorter array to ensure $O(\log(\min(m, n)))$ execution.
  • Use -Infinity and Infinity boundary sentinels to simplify edge partitions.
  • Requires no memory allocation ($O(1)$ space).

09. Minimum Cost to Hire K Workers

Difficulty:HardPattern:Ratio Sorting + Max-HeapTime:O(n log n)Space:O(k)

There are n workers given by quality and wage arrays. You want to hire exactly k workers such that every worker is paid at least their minimum wage and worker pay is proportional to their quality. Return the minimum cost to form a valid team.

How It Works & Algorithmic Design

Solves using Ratio Sorting + Max-Heap Quality Tracking:

  1. Ratio Computation: For each worker, compute wage / quality ratio. Sort workers by this unit ratio in ascending order.
  2. Max-Heap: Track top $k$ smallest qualities seen so far using Max-Heap maxHeap and running sum totalQuality.
  3. Greedy Traversal: For each worker ratio $R$:
    • Add quality to maxHeap and totalQuality += quality.
    • If maxHeap.size > k, pop largest quality top and subtract totalQuality -= top.
    • If maxHeap.size === k: calculate candidate cost totalQuality * R and update minCost.

Why This Approach Works Best

Sorting ratios ensures wage minimums are respected while Max-Heap prunes high quality workers to optimize total cost in $O(n \log n)$ time.

Example Walkthrough
Input: quality = [10,20,5], wage = [70,50,30], k = 2
Workers data.
Min Cost Team: Hire worker 1 (ratio 2.5) and worker 2 (ratio 6.0) -> cost 105.0.
Minimal wage cost.
Output: 105.00000
Minimum total cost.

Answer: Minimum Cost to Hire K Workers implementation

function mincostToHireWorkers(quality, wage, k) {
  const workers = quality.map((q, i) => ({ q, r: wage[i] / q }));
  workers.sort((a, b) => a.r - b.r);
  const heap = []; // Simulated Max-Heap
  let totalQuality = 0;
  let minCost = Infinity;
  for (const w of workers) {
    heap.push(w.q);
    heap.sort((a, b) => b - a);
    totalQuality += w.q;
    if (heap.length > k) {
      totalQuality -= heap.shift();
    }
    if (heap.length === k) {
      minCost = Math.min(minCost, totalQuality * w.r);
    }
  }
  return minCost;
}
💡 Sort workers by wage-to-quality ratio and use max-heap to keep quality sum minimal.
Key Takeaways
  • Team cost is determined by max worker ratio $\times$ total team quality.
  • Max-heap evicts highest quality worker to keep total team quality minimal.
  • Sorting ratios guarantees worker wage constraints are met.

10. The Skyline Problem

Difficulty:HardPattern:Line Sweep / Max-Heap EventTime:O(n log n)Space:O(n)

A city's skyline is the outer contour of the silhouette formed by all the buildings when viewed from a distance. Given the positions and heights of all the buildings [left, right, height], return the key points that characterize the skyline.

How It Works & Algorithmic Design

Solves using Building Event Sorting + Active Max-Heap:

  1. Event Points: Split building [L, R, H] into two boundary events: (L, -H) (start event) and (R, H) (end event).
  2. Sort Events: Sort event points primarily by X-coordinate. For ties, sort start events before end events with higher heights first.
  3. Max-Heap & Max Height Track:
    • Maintain maxHeap of active building heights initialized with 0.
    • For each event point (x, h):
      • If start event (h < 0), add $|h|$ to heap.
      • If end event (h > 0), remove $h$ from heap.
      • Get currentMax = maxHeap.peek().
      • If currentMax !== prevMax: contour height changed! Record key point [x, currentMax] and set prevMax = currentMax.

Why This Approach Works Best

Event sorting handles building overlaps cleanly, generating critical key points in $O(n \log n)$ time.

Example Walkthrough
Input Buildings: [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Building bounds.
Key Points: Height changes occur at x=2,3,7,9,12,15,20,24.
Outer silhouette contour.
Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
Skyline key points.

Answer: The Skyline Problem implementation

function getSkyline(buildings) {
  const events = [];
  for (const [l, r, h] of buildings) {
    events.push([l, -h]);
    events.push([r, h]);
  }
  events.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]);
  const res = [];
  const heights = [0];
  let prevMax = 0;
  for (const [x, h] of events) {
    if (h < 0) {
      heights.push(-h);
    } else {
      const idx = heights.indexOf(h);
      if (idx !== -1) heights.splice(idx, 1);
    }
    heights.sort((a, b) => b - a);
    const currentMax = heights[0];
    if (currentMax !== prevMax) {
      res.push([x, currentMax]);
      prevMax = currentMax;
    }
  }
  return res;
}
💡 Process building left and right edge sweep events using a Max-Heap to track silhouette contour changes.
Key Takeaways
  • Use negative height values to distinguish building start events from end events.
  • Record key point when active building height maximum changes.
  • Line sweep executes in $O(n \log n)$ time.

STAY UPDATED WITH BYTES!

© 2026 Bytes4Dev. All rights reserved.

v.0.4.0