0%

By Long Luo

Here shows 3 Approaches to slove this problem: BFS(Dijkstra), Binary Search, Union Find.

# BFS(Dijkstra)

## Analysis

• Time Complexity: $O(mnlog(mn))$.
• Space Complexity: $O(mn)$.

By Long Luo

# Intuition

The Data Pair $\textit{people}[h, k]$, $h_i$ represents the i-th person of height $h_i$, $k_i$ represents the other people in front who have a height greater than or equal to $h_i$.

Pattern:

When face such kind of problem with Data Pair, sorting first will simplify the problem.

Usually, we will sort the first element in ascending order, while the second element in descending order, or sort the first element in descending order with the second element in ascending order.

# Greedy

We sort the $\textit{people}$ pairs first by $height$ in descending order, and $k$ in ascending order.

According to the descending order of $height$, for each person, the number of people before him is the number of people whose height is greater than or equal to him.

According to the ascending order of $k$, because the $k$ is increase later, which can reduce the number of insert operations.

Take the example:

After sorting:

Insert one by one:

By Long Luo

Here shows 3 Approaches to slove this problem: Sorting, Priority Queue, Divide and Conquer.

# Sort

Sort the array first, then the k-th element.

## Analysis

• Time Complexity: $O(nlogn)$.
• Space Complexity: $O(logn)$.

By Long Luo

# Intuition

While we are moving, we will need to use bricks or ladders several times. Suppose we have to move to the next building, which means we must use one ladder or $\Delta h$ bricks, so there is a question, whether to use ladders or bricks?

If the gap of buildings is large, we may use the ladder, otherwise we use the bricks.

We can consider ladder as a one-time unlimited number of bricks, That is, if we have l ladders, we will use the ladder on the $l$ times where $\Delta h$ is the largest, and use the bricks in the rest.

Therefore, we got the answer. We maintain no more than $l$ largest $\Delta h$ using priority queues, and these are where the ladders are used. For the remaining $\Delta h$, we need to use bricks, so we need to accumulate them, if the $sum$ exceeds the number of bricks $b$, then we have move to the furthest building.

The code is as follows:

By Long Luo

Here shows 3 Approaches to slove this problem: DFS, BFS and Dynamic Programming.

# DFS

TLE!

Sorting the array first, then use DFS:

Memory DFS:

## Analysis

• Time Complexity: O(amount * n)
• Space Complexity: O(amount)

By Long Luo

# Intuition

This problem is a classic and typical dynamic programming problem. We can break the large problem into sub-problems.

We can use both the Top-Down and Bottom-Up approach to solve this problem.

# Top-Down Approach

1. State definition:

$dp[i][j]$ represents the minimum path sum of row $i$ and column $j$.

1. State Analysis:

$dp[0][0]=c[0][0]$

1. The State Transfer Equation:

$dp[i][j] = \begin{cases} dp[i-1][0] + c[i][0] & j=0 \\ dp[i-1][i-1] + c[i][i] & j==i \\ min(dp[i-1][j-1],dp[i-1][j]) + c[i][j] & 0 < j < i \\ \end{cases}$

so we can easily write such code:

In fact, $dp[i][j]$ is only relevant to $dp[i-1][j]$, but $dp[i-2][j]$ and previous states are irrelevant, so we don’t have to store these states. We can only use extra $O(2n)$ space: two one-dimensional arrays of length $n$ for the transfer, and map $i$ to one of the one-dimensional arrays according to the parity, then $i-1$ is mapped to the other one-dimensional array.

We enumerate $j$ decreasingly from $i$ to $0$, so that we only need a one-dimensional array $dp$ of length $n$ to complete the state transition.

$dp[j] = min(dp[j-1], dp[j]) + c[i][j]$

By Long Luo

# Intuition

To simulate the CPU operations, there comes $3$ questions:

2. How to maintain the enqueued tasks?

Let’s answer the $3$ questions:

1. We assign the tasks to the CPU by $\textit{enqueueTime}$, so we sort the array first by $\textit{enqueueTime}$. However, we will lose the $\textit{index}$ of the task.

We can parse the task by creating a new class $\texttt{Job}$, whose members are $\textit{id}$, $\textit{enqueueTime}$, $\textit{processTime}$.

1. We put all the tasks assigned to the CPU into a Priority Queue and poll out the task whose $\textit{processTime}$ is the least each time.

2. We can maintain a $\textit{curTime}$ variable, which represents the current time with initial value is $0$.

If the CPU has no tasks to execute, we set the $\textit{curTime}$ to $\textit{enqueueTime}$ of the next task in the array that has not yet been assigned to the CPU.

After this, we put all $\textit{enqueueTime} \le \textit{curTime}$ tasks into the Priority Queue.

By Long Luo

Here shows 4 Approaches to slove this problem: Brute Force, HashMap, Binary Search, Two Pointers.

# Brute Force

It’s easy to use Brute Force to find the answer, however, the time complexity is $O(n^2)$, so the BF solution will Time Limit Exceeded!

## Analysis

• Time Complexity: $O(n^2)$.
• Space Complexity: $O(1)$.

# HashMap

We can use a extra $\texttt{HashMap}$ to record the element we traversalled.

By Long Luo

# Brute Force

## Analysis

• Time Complexity: $O(nlogn)$.
• Space Complexity: $O(n)$.

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. ???

By Long Luo

This article is the solution 5 Approaches: BF use Long, BF use Int, Binary Search use Long, Binary Search use Int, Recursion of Problem 29. Divide Two Integers , Chinese version is 3种方法：暴力法，二分搜索，递归 .

Here shows 5 Approaches to slove this problem: BF use long, BF use int, Binary Search use Long, Binary Search use Int, Recursion.

# Intuition

To divide two integers without using multiplication, division, and mod operator, so we can subtract the $\textit{divisor}$ from the $\textit{dividend}$ util the $\textit{result} \ge 0$.

# Brute Force use Long

We can make the $\textit{dividend}$ and $\textit{divisor}$ positive, and cast to long, then process.

The solution will Time Limit Exceeded, we have to deal with some corner cases.

## Analysis

• Time Complexity: $O(x / y)$.
• Space Complexity: $O(1)$.