heap:

Minimum Number of Refueling Stops

A car travels from a starting position to a destination which is target miles east of the starting position. Along the way, there are gas stations. Each station[i] represents a gas station that is station[i][0] miles east of the starting position, and has station[i][1] liters of gas. The car starts with an infinite tank of gas, which initially has startFuel liters of fuel in it. It uses 1 liter of gas per 1 mile that it drives.

by lek tin in "algorithm" access_time 3-min read

Top K Frequent Words

Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first. Example 1 Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 2 Output: ["i", "love"] Explanation: "i" and "love" are the two most frequent words. Note that "i" comes before "love" due to a lower alphabetical order.

by lek tin in "algorithm" access_time 2-min read

Campus Bikes

On a campus represented as a 2D grid, there are N workers and M bikes, with N <= M. Each worker and bike is a 2D coordinate on this grid. Our goal is to assign a bike to each worker. Among the available bikes and workers, we choose the (worker, bike) pair with the shortest Manhattan distance between each other, and assign the bike to that worker. (If there are multiple (worker, bike) pairs with the same shortest Manhattan distance, we choose the pair with the smallest worker index; if there are multiple ways to do that, we choose the pair with the smallest bike index).

by lek tin in "algorithm" access_time 2-min read

Super Ugly Number

Write a program to find the nthsuper ugly number. Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. Example: Input: n = 12, primes = [2,7,13,19] Output: 32 Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12 super ugly numbers given primes = [2,7,13,19] of size 4. Note 1 is a super ugly number for any given primes. The given numbers in primes are in ascending order.

by lek tin in "algorithm" access_time 1-min read

Ugly Number II

Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. Example: Input: n = 10 Output: 12 Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers. Note 1 is typically treated as an ugly number. n does not exceed 1690. Solution import heapq class Solution: def nthUglyNumber(self, n: int) -> int: if n <= 0: return 0 if n == 1: return 1 q = [1] visited = {1: True} removed = 0 ans = 0 while removed !

by lek tin in "algorithm" access_time 1-min read

Find Median From Data Stream

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value. Example [2,3,4], the median is 3 [2,3], the median is (2 + 3) / 2 = 2.5 Design a data structure that supports the following two operations: void addNum(int num) - Add a integer number from the data stream to the data structure.

by lek tin in "algorithm" access_time 2-min read

23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Example: Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6 Solution: Idea #1 - Brute force with sorting first: Time complexity : O(NlogN) Space complexity : O(N) Idea #2 - Compare head nodes one by one: Time complexity : O(kN) Space complexity : O(N) - creating a new linked list or O(1) in-place Idea #3 - Merge lists one by one:

by lek tin in "algorithm" access_time 3-min read