optimistiks

export function reorganizeString(inputString) {
  // build a hash map where keys are characters, and values are their frequencies
  const map = {};
  for (let i = 0; i < inputString.length; ++i) {
    const char = inputString[i];
    map[char] = (map[char] ?? 0) + 1;
  }

  // initialize max heap by pushing character frequencies together with characters
  // so heap will always contain a character with max frequency value on top

optimistiks

export function kClosest(points, k) {
  const heap = new MaxHeap();

  // put initial k points into max heap with their distances
  // now we have largest distance seen so far at the top
  for (let i = 0; i < k; ++i) {
    const distance = getDistance(points[i]);
    heap.offer([distance, points[i]]);
  }

optimistiks

import MinHeap from "./min_heap.js";

export function topKFrequent(arr, k) {
  // create map where we store numbers from arr as keys,
  // and their frequencies in arr as values
  const map = {};

  // fill up frequency map
  for (let i = 0; i < arr.length; ++i) {
    const char = arr[i];

optimistiks

export function findKthLargest(arr, k) {
  // we are going to have min heap of size k
  // it means the top of the heap is going to be the minimum element
  // of all k elements in the heap
  // which is exactly the kth largest element that we need
  const heap = new MinHeap();

  for (let i = 0; i < k; ++i) {
    // initialize the heap with the first k elements from the array
    heap.offer(arr[i]);

optimistiks

export function kthSmallestElement(root, k) {
  const items = []
  // traverse tree in order, creating a sorted arrat
  inorder(root, (value) => items.push(value))
  // grab k-1th item as a result
  return items[k - 1];
}

function inorder(root, callback) {
  const stack = [];

optimistiks

export function binarySearchRotated(nums, target) {
  let low = 0;
  let high = nums.length - 1;

  if (nums.length === 0) {
    // nothing to do if the array is empty
    return -1;
  }

  // iteration stops once low gets larger than high (we only increase low and we only decrease high)

optimistiks

export function firstBadVersion(n) {
  // -- DO NOT CHANGE THIS SECTION
  versionApi.n = n;
  // --

  let start = 1;
  let end = n;
  let count = 0;

  while (start < end) {

optimistiks

class RandomPickWithWeight {
  constructor(w) {
    // w is an array of numbers, each number is a weight of the index where it's stored
    // so our task is to return a random index with respect to weights,
    // so the most "heavy" index is the most probable to be returned
    this.weights = w
    // build an array of rolling sums
    this.sums = []
    for (let i = 0; i < w.length; ++i) {
      const prevSum = this.sums[i - 1] || 0

optimistiks

export function findClosestElements(nums, k, num) {
  // we are going to be searching for windows
  // this range indicates elements that can be first elements in a window
  // hence the last element in the range is length-k
  // so if a window starts from a last element in the range,
  // the window does not go out of bounds
  let searchRangeFirstElementIndex = 0;
  let searchRangeLastElementIndex = nums.length - k;

  while (searchRangeFirstElementIndex < searchRangeLastElementIndex) {

optimistiks

export function singleNonDuplicate(nums) {
  let start = 0;
  let end = nums.length - 1;

  while (start < end) {
    let mid = Math.floor((end - start) / 2) + start;
    if (mid % 2 !== 0) {
      mid -= 1;
    }
    if (nums[mid] !== nums[mid + 1]) {