Per48edjes

| transaction_id | customer_id | transaction_date | amount |
| -------------- | ----------- | ---------------- | ------ |
| 653            | 4           | 2019-8-9         | 5800   |
| 856            | 15          | 2019-7-26        | 1044   |
| 181            | 9           | 2019-7-25        | 1673   |
| 923            | 43          | 2019-7-21        | 2238   |
| 916            | 34          | 2019-7-22        | 2936   |
| 907            | 8           | 2019-8-29        | 5936   |
| 25             | 35          | 2019-7-17        | 8273   |
| 783            | 37          | 2019-7-3         | 4070   |

Per48edjes

from collections import defaultdict

def node():
  return defaultdict(node)
  
def word_exists(word, node):
    if not word:
        return None in node
    return word_exists(word[1:], node[word[0]])

Per48edjes

Per48edjes

TL;DR: Dijkstra's alone isn't sufficient to solve the all-pairs shortest paths problem, but on an undirected graph, you're right that there is information contained about some of the pairwise shortest paths (i.e., those involving the source vertex as the source or the destination). Depending on the queries (if you know them ahead of time and they were sufficiently contained in a small subgraph), perhaps, you could run Dijkstra fewer than $|V|$ times to answer them.

---

Hmmmm... I'm don't think Dijkstra alone would give you all-pairs shortest paths (APSPs) among all vertices inside the envelope[1] as it proceeds (or even at the end). The distance estimates are from a single, source vertex $s$, so in an undirected graph you could get some of the pairwise shortest paths, namely, those involving $s$ (e.g., $d(s, v) = d(v, s)$ for any $v$ in the envelope), but not all of them. Maybe you could get away with it if you knew all the pairs you cared about involved $s$?

Johnson's is an APSP algori

Per48edjes

import math


class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        n = len(arr)
        spanned_indices = [[1,1] for _ in range(n + 1)]
        mono_i_stack = []
 for i, num in enumerate(arr + [-math.inf]):

Per48edjes

class Solution:

    def minOperations(self, nums: List[int]) -> int:

        def opMin(freq: int) -> int:
            assert freq > 1, f"{opMin.__name__} only takes freq > 1"
            call_stack = [(freq, 0)]
            while call_stack:
 k, ops = call_stack.pop()

Per48edjes

Per48edjes

-- Minimal nvim config with lazy
-- Assumes a directory in $NVIM_DATA_MINIMAL
-- Start with
--
-- export NVIM_DATA_MINIMAL=$(mktemp -d)
-- export NVIM_APP_NAME="nvim-ht-minimal"
-- nvim -u minimal.lua
--
-- Then exit out of neovim and start again.

Per48edjes

from typing import Optional


class MinHeap:

    """
    A MinHeap is a complete binary tree where the value of each node is less than or equal
    to the value of its children. (The root node is the minimum element in the heap.)

    This implementation supports the following operations:

Per48edjes

# This is the same thing as finding the (len(nums) - (k-1))th order statistic.
#   - Note: We need to transform "Kth Largest, 1-indexed" into "Kth Smallest, 0-indexed"
# Idea: Use randomized quickselect! It has O(n) expected time

import random


class Solution:

    # O(n) time, O(1) space