Sorting, Searching, Stacks, Queues, and Linked Lists

// Suppose we're sorting students by name:
// Input: [{name: 'Alice', id: 2}, {name: 'Alice', id: 1}, {name: 'Bob', id: 3}]
// Merge Sort (stable): Alice(2), Alice(1), Bob  — id 2 comes before id 1
// QuickSort (unstable): Alice(1), Alice(2), Bob — might reorder the Alices

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

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;

  // Merge while both arrays have elements
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {  // <= ensures stability
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  // Add remaining elements
  result.push(...left.slice(i), ...right.slice(j));
  return result;
}

// Worst case: QuickSort on already sorted array with first element as pivot
// [1, 2, 3, 4, 5]
// Pivot = 1: left = [], right = [2, 3, 4, 5]  -> recurse on [2, 3, 4, 5]
// Pivot = 2: left = [], right = [3, 4, 5]      -> recurse on [3, 4, 5]
// Each partition removes only ONE element → O(n²) behavior!

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
  return arr;
}

function partition(arr, low, high) {
  // Random pivot to avoid worst case
  const randomIndex = low + Math.floor(Math.random() * (high - low + 1));
  [arr[randomIndex], arr[high]] = [arr[high], arr[randomIndex]];

  const pivot = arr[high];
  let i = low - 1;

  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }

  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

// Problem: Find two numbers that sum to target
// Naive: O(n²) nested loops
// Better: O(n log n) sort + two pointers

function twoSum(arr, target) {
  arr.sort((a, b) => a - b);  // O(n log n)
  let left = 0, right = arr.length - 1;

  while (left < right) {
    const sum = arr[left] + arr[right];
    if (sum === target) return [arr[left], arr[right]];
    if (sum < target) left++;
    else right--;
  }
  return null;  // No pair found
}

const stack = [];
stack.push(1);      // Add to top: O(1)
stack.pop();        // Remove from top: O(1)
stack[stack.length - 1];  // Peek top: O(1)

// WRONG: Don't use array.shift() — it's O(n)!
const queue = [];
queue.push(1);      // O(1)
queue.shift();      // O(n) ← BAD! All elements shift down

// RIGHT: Use index tracking or a proper queue
class Queue {
  constructor() { this.items = {}; this.head = 0; this.tail = 0; }
  enqueue(val) { this.items[this.tail++] = val; }
  dequeue() {
    if (this.head === this.tail) return undefined;
    const val = this.items[this.head];
    delete this.items[this.head++];
    return val;
  }
  isEmpty() { return this.head === this.tail; }
}

// Problem: For each element, find the next greater element
// Input: [1, 3, 2, 4]
// Output: [3, 4, -1, -1]  (next greater or -1)

function nextGreaterElement(arr) {
  const result = new Array(arr.length).fill(-1);
  const stack = [];

  for (let i = 0; i < arr.length; i++) {
    // While stack is not empty and current > top of stack
    while (stack.length && arr[i] > arr[stack[stack.length - 1]]) {
      const prevIdx = stack.pop();
      result[prevIdx] = arr[i];  // Found next greater!
    }
    stack.push(i);  // Push current index
  }

  return result;
}
// Time: O(n), Space: O(n) — each element pushed/popped once

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

// Create a linked list: 1 -> 2 -> 3
const head = new ListNode(1, new ListNode(2, new ListNode(3)));

function mergeIntervals(intervals) {
  if (!intervals.length) return [];

  intervals.sort((a, b) => a[0] - b[0]);  // Sort by start
  const result = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    const last = result[result.length - 1];
    const current = intervals[i];

    if (current[0] <= last[1]) {
      // Overlapping: merge
      last[1] = Math.max(last[1], current[1]);
    } else {
      // No overlap: add as new interval
      result.push(current);
    }
  }

  return result;
}

function meetingRooms2(intervals) {
  if (!intervals.length) return 0;

  intervals.sort((a, b) => a[0] - b[0]);

  // Min-heap of end times (use simple array + manual heap or use library)
  const endTimes = [intervals[0][1]];

  for (let i = 1; i < intervals.length; i++) {
    const [start, end] = intervals[i];

    // If earliest meeting ends before or at current start, reuse room
    if (endTimes[0] <= start) {
      // Remove min
      endTimes[0] = endTimes[endTimes.length - 1];
      endTimes.pop();
      minHeapifyDown(endTimes, 0);
    }

    // Add this meeting's end time
    endTimes.push(end);
    minHeapifyUp(endTimes, endTimes.length - 1);
  }

  return endTimes.length;  // Rooms needed = size of heap
}

// Simple min-heap helpers
function minHeapifyUp(heap, idx) {
  while (idx > 0) {
    const parentIdx = Math.floor((idx - 1) / 2);
    if (heap[parentIdx] <= heap[idx]) break;
    [heap[parentIdx], heap[idx]] = [heap[idx], heap[parentIdx]];
    idx = parentIdx;
  }
}

function minHeapifyDown(heap, idx) {
  while (2 * idx + 1 < heap.length) {
    let smallest = idx;
    const left = 2 * idx + 1, right = 2 * idx + 2;
    if (heap[left] < heap[smallest]) smallest = left;
    if (right < heap.length && heap[right] < heap[smallest]) smallest = right;
    if (smallest === idx) break;
    [heap[idx], heap[smallest]] = [heap[smallest], heap[idx]];
    idx = smallest;
  }
}

function threeSum(nums) {
  nums.sort((a, b) => a - b);
  const result = [];

  for (let i = 0; i < nums.length - 2; i++) {
    // Skip duplicate first element
    if (i > 0 && nums[i] === nums[i - 1]) continue;

    // Optimization: if first num > 0, no triplet sums to 0
    if (nums[i] > 0) break;

    // Two-sum with two pointers
    let left = i + 1, right = nums.length - 1;
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      if (sum === 0) {
        result.push([nums[i], nums[left], nums[right]]);

        // Skip duplicates
        while (left < right && nums[left] === nums[left + 1]) left++;
        while (left < right && nums[right] === nums[right - 1]) right--;

        left++;
        right--;
      } else if (sum < 0) {
        left++;
      } else {
        right--;
      }
    }
  }

  return result;
}

function findKthLargest(nums, k) {
  // Convert "kth largest" to kth smallest from end
  const target = nums.length - k;
  return quickSelect(nums, 0, nums.length - 1, target);
}

function quickSelect(arr, low, high, targetIdx) {
  if (low === high) return arr[low];

  // Random pivot to avoid worst case
  const randomIdx = low + Math.floor(Math.random() * (high - low + 1));
  [arr[randomIdx], arr[high]] = [arr[high], arr[randomIdx]];

  const pi = partition(arr, low, high);

  if (targetIdx === pi) return arr[pi];
  if (targetIdx < pi) return quickSelect(arr, low, pi - 1, targetIdx);
  return quickSelect(arr, pi + 1, high, targetIdx);
}

function partition(arr, low, high) {
  const pivot = arr[high];
  let i = low - 1;

  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }

  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

function isValid(s) {
  const stack = [];
  const pairs = { ')': '(', ']': '[', '}': '{' };

  for (const char of s) {
    if (char === '(' || char === '[' || char === '{') {
      stack.push(char);
    } else {
      if (!stack.length || stack.pop() !== pairs[char]) return false;
    }
  }

  return stack.length === 0;
}

function dailyTemperatures(temps) {
  const result = new Array(temps.length).fill(0);
  const stack = [];  // Store indices

  for (let i = 0; i < temps.length; i++) {
    // While stack not empty and current temp > stack top temp
    while (stack.length && temps[i] > temps[stack[stack.length - 1]]) {
      const prevIdx = stack.pop();
      result[prevIdx] = i - prevIdx;  // Days until warmer
    }
    stack.push(i);
  }

  return result;
}

function reverseList(head) {
  let prev = null, curr = head;

  while (curr) {
    const next = curr.next;  // Save next
    curr.next = prev;         // Reverse the link
    prev = curr;              // Move prev forward
    curr = next;              // Move curr forward
  }

  return prev;  // New head
}

function mergeTwoLists(list1, list2) {
  const dummy = new ListNode(0);
  let curr = dummy;

  while (list1 && list2) {
    if (list1.val <= list2.val) {
      curr.next = list1;
      list1 = list1.next;
    } else {
      curr.next = list2;
      list2 = list2.next;
    }
    curr = curr.next;
  }

  // Attach remaining
  curr.next = list1 || list2;

  return dummy.next;
}

function hasCycle(head) {
  let slow = head, fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow === fast) return true;  // Cycle detected
  }

  return false;  // No cycle
}