leetcode 1642

DoubleLinkedList.ts

class LinkNode<TValue> {
  value: TValue;
  prev: LinkNode<TValue> | null;
  next: LinkNode<TValue> | null;

  constructor(value: TValue) {
    this.value = value;
  }
}

interface IPrioryQueue {
  get head(): LinkNode<number> | null;
  get tail(): LinkNode<number> | null;

  enqueue(n: number): void;
  peekMin(): number | undefined;
  dequeueMin(): number | undefined;
  peekMax(): number | undefined;
  dequeueMax(): number | undefined;
}

class PrioryQueue implements IPrioryQueue {
  // asc, from head to tail
  protected _head: LinkNode<number> | null = null;

  get head(): LinkNode<number> | null {
    return this._head;
  }

  protected _tail: LinkNode<number> | null = null;

  get tail(): LinkNode<number> | null {
    return this._tail;
  }

  enqueue(n: number): void {
    const listNode = new LinkNode(n);

    // first
    if (this.head == null || this.tail == null) {
      this._head = listNode;
      this._tail = listNode;
      return;
    }

    // new head
    if (listNode.value <= this.head.value) {
      this.head.prev = listNode;
      listNode.next = this.head;
      this._head = listNode;
      return;
    }

    // new tail
    if (listNode.value >= this.tail.value) {
      this.tail.next = listNode;
      listNode.prev = this.tail;
      this._tail = listNode;
      return;
    }

    const diffWithHead = listNode.value - this.head.value;
    const diffWithTail = this.tail.value - listNode.value;

    // close to head
    if (diffWithHead <= diffWithTail) {
      let pointer = this.head;

      while (pointer.next != null) {
        if (
          pointer.value <= listNode.value &&
          listNode.value <= pointer.next.value
        ) {
          listNode.next = pointer.next;
          listNode.prev = pointer;
          pointer.next.prev = listNode;
          pointer.next = listNode;
          return;
        }
        pointer = pointer.next;
      }

      pointer.next = listNode;
      listNode.prev = pointer;
      return;
    }

    // close to tail
    if (diffWithTail < diffWithHead) {
      let pointer = this.tail;

      while (pointer.prev != null) {
        if (
          pointer.prev.value <= listNode.value &&
          listNode.value <= pointer.value
        ) {
          listNode.next = pointer;
          listNode.prev = pointer.prev;
          pointer.prev.next = listNode;
          pointer.prev = listNode;
          return;
        }
        pointer = pointer.prev;
      }

      pointer.prev = listNode;
      listNode.next = pointer;
      return;
    }

    // didn't fit any condition
    throw new Error("enqueue error");
  }

  peekMin(): number | undefined {
    return this.head?.value;
  }

  dequeueMin(): number | undefined {
    if (this.head == null) return undefined;

    const old = this.head;
    const next = this.head.next;
    if (next != null) next.prev = null;
    this._head = next;

    return old.value;
  }

  peekMax(): number | undefined {
    return this.tail?.value;
  }

  dequeueMax(): number | undefined {
    if (this.tail == null) return undefined;

    const old = this.tail;
    const prev = this.tail.prev;
    if (prev != null) prev.next = null;
    this._tail = prev;

    return old.value;
  }
}

type Constructor<T> = new (...args: any[]) => T;

function withSumming<T extends Constructor<IPrioryQueue>>(Base: T) {
  return class Summable extends Base {
    protected _sum: number = 0;

    get sum(): number {
      return this._sum;
    }

    enqueue(n: number): void {
      super.enqueue(n);
      this._sum += n;
    }

    dequeueMin(): number | undefined {
      const min = super.dequeueMin();
      this._sum -= min ?? 0;
      return min;
    }

    dequeueMax(): number | undefined {
      const max = super.dequeueMax();
      this._sum -= max ?? 0;
      return max;
    }
  };
}

function withCounting<T extends Constructor<IPrioryQueue>>(Base: T) {
  return class Countable extends Base {
    private _count: number = 0;

    get count(): number {
      return this._count;
    }

    enqueue(n: number): void {
      super.enqueue(n);
      this._count += 1;
    }

    dequeueMin(): number | undefined {
      const min = super.dequeueMin();
      if (min != null) this._count -= 1;
      return min;
    }

    dequeueMax(): number | undefined {
      const max = super.dequeueMax();
      if (max != null) this._count -= 1;
      return max;
    }
  };
}

// Mixin
const SuperPrioryQueue = withCounting(withSumming(PrioryQueue));

function furthestBuilding(
  heights: number[],
  bricks: number,
  ladders: number
): number {
  let sum = 0;
  const pq = new SuperPrioryQueue();

  for (let index = 0; index < heights.length; index++) {
    if (index === 0) continue;

    const currentHeight = heights[index];
    const lastHeight = heights[index - 1];
    const cost = currentHeight <= lastHeight ? 0 : currentHeight - lastHeight;

    sum += cost;
    pq.enqueue(cost);
    if (pq.count > ladders) {
      pq.dequeueMin();
    }

    if (bricks < sum - pq.sum) {
      return index - 1;
    }
  }

  return heights.length - 1;
}

function furthestBuilding2(
  heights: number[],
  bricks: number,
  ladders: number
): number {
  const result = heights.reduce(
    (acc, current, index, array) => {
      console.log(acc.pq);
      if (index === 0) return acc;
      if (acc.stopped) return acc;

      const lastHeight = array[index - 1];
      const cost = current <= lastHeight ? 0 : current - lastHeight;

      acc.sum += cost;
      acc.pq.enqueue(cost);
      if (acc.pq.count > ladders) {
        acc.pq.dequeueMin();
      }

      if (bricks >= acc.sum - acc.pq.sum) {
        acc.furthest = index;
        return acc;
      }

      acc.stopped = true;
      return acc;
    },
    {
      sum: 0,
      pq: new SuperPrioryQueue(),
      furthest: 0,
      stopped: false,
    }
  );

  return result.furthest;
}

heap.ts

class Heap<TValue> {
  store: TValue[] = [];

  get size() {
    return this.store.length;
  }

  // if true, parent stays in parent, child stays in child
  // if false, parent need to swap with child
  private compareFn: (parent: TValue, child: TValue) => boolean;

  constructor(compareFn: (a: TValue, b: TValue) => boolean) {
    this.compareFn = compareFn;
  }

  enqueue(n: TValue): void {
    this.store.push(n);
    this.heapifyUp(this.store.length - 1);
  }

  dequeue(): TValue | undefined {
    if (this.store.length === 0) return undefined;

    const head = this.store.shift();
    if (this.store.length === 0) return head;

    const tail = this.store.pop()!;
    this.store.unshift(tail);
    this.heapifyDown(0);

    return head;
  }

  private heapifyUp(currentIndex: number) {
    if (currentIndex === 0) return;

    const parentIndex =
      currentIndex % 2 === 1 ? (currentIndex - 1) / 2 : (currentIndex - 2) / 2;
    const targetIndex = this.compareIndex(parentIndex, currentIndex);
    if (targetIndex == null) return;
    if (targetIndex === parentIndex) return;

    this.swap(currentIndex, parentIndex);
    this.heapifyUp(parentIndex);
  }

  private heapifyDown(currentIndex: number) {
    const leftIndex = currentIndex * 2 + 1;
    const rightIndex = currentIndex * 2 + 2;

    const childIndex = this.compareIndex(leftIndex, rightIndex);
    if (childIndex == null) return;

    const targetIndex = this.compareIndex(currentIndex, childIndex);
    if (targetIndex == null) return;
    if (targetIndex === currentIndex) return;

    this.swap(currentIndex, targetIndex);
    this.heapifyDown(targetIndex);
  }

  private compareIndex(aIndex: number, bIndex: number): number | null {
    const a = this.store[aIndex];
    const b = this.store[bIndex];

    if (a == null && b == null) return null;
    if (a == null) return bIndex;
    if (b == null) return aIndex;

    return this.compareFn(a, b) ? aIndex : bIndex;
  }

  private swap(aIndex: number, bIndex: number): void {
    const a = this.store[aIndex];
    const b = this.store[bIndex];
    this.store[aIndex] = b;
    this.store[bIndex] = a;
  }
}

function furthestBuilding(
  heights: number[],
  bricks: number,
  ladders: number
): number {
  const result = heights.reduce(
    (acc, current, index, array) => {
      if (index === 0) return acc;
      if (acc.stopped) return acc;

      const lastHeight = array[index - 1];
      const cost = current <= lastHeight ? 0 : current - lastHeight;
      if(cost === 0) {
        acc.furthest = index;
        return acc;
      }

      acc.sum += cost;
      acc.heap.enqueue(cost);
      acc.heapSum += cost;

      if (acc.heap.size > ladders) {
        const min = acc.heap.dequeue()!;
        acc.heapSum -= min;
      }

      if (bricks >= acc.sum - acc.heapSum) {
        acc.furthest = index;
        return acc;
      }

      acc.stopped = true;
      return acc;
    },
    {
      sum: 0,
      heap: new Heap<number>((a, b) => a <= b),
      heapSum: 0,
      furthest: 0,
      stopped: false,
    }
  );

  return result.furthest;
}

PrioryQueueArray.ts

class PrioryQueueArray {
  // asc
  private store: number[] = [];

  enqueue(n: number): void {
    let inserted = false;

    for (const [i, e] of this.store.entries()) {
      if (n <= e) {
        this.store.splice(i, 0, n);
        inserted = true;
        break;
      }
    }
    if (inserted) return;

    this.store.push(n);
  }

  peekMin(): number | undefined {
    return this.store[0];
  }

  dequeueMin(): number | undefined {
    return this.store.shift();
  }

  peekMax(): number | undefined {
    return this.store[this.store.length - 1];
  }

  dequeueMax(): number | undefined {
    return this.store.pop();
  }
}

function furthestBuilding(
  heights: number[],
  bricks: number,
  ladders: number
): number {
  const prioryQueue = new PrioryQueueArray();

  for (const [i, e] of heights.entries()) {
    if (i === 0) continue;

    const prev = heights[i - 1];
    const cost = prev >= e ? 0 : e - prev;

    // using nothing
    if (cost === 0) continue;

    // using ladder
    if (ladders > 0) {
      ladders -= 1;
      prioryQueue.enqueue(cost);
      continue;
    }

    const min = prioryQueue.peekMin();

    // using ladder for now, replace old ladder by bricks
    if (min != null && cost > min && bricks >= min) {
      prioryQueue.dequeueMin();
      prioryQueue.enqueue(cost);
      bricks -= min;
      continue;
    }

    // using bricks
    if (bricks >= cost) {
      bricks -= cost;
      continue;
    }

    // can't go further
    return i - 1;
  }

  return heights.length - 1;
}