Some Coding Problems

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

Method: DFS

class Solution:

def __init__(self):

self.anw = []

self.dir = [(-1, 0), (1, 0), (0, 1), (0, -1)]

self.pac = []

self.atl = []

self.visited = []

self.m = 0

self.n = 0

def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:

self.m = len(heights)

self.n = len(heights[0])

self.pac = [[0] * self.n for _ in range(self.m)]

self.atl = [[0] * self.n for _ in range(self.m)]

self.visited = [[0] * self.n for _ in range(self.m)]

if not self.m and self.n:

return []

for i in range(0, 1):

for j in range(self.n):

self.dfs(heights, i, j, True) # pacific

self.visited = [[0] * self.n for _ in range(self.m)]

for i in range(self.m):

for j in range(0, 1):

self.dfs(heights, i, j, True)

self.visited = [[0] * self.n for _ in range(self.m)]

for i in range(self.m-1, self.m):

for j in range(self.n):

self.dfs(heights, i, j, False) # Atlantic

self.visited = [[0] * self.n for _ in range(self.m)]

for i in range(self.m):

for j in range(self.n-1, self.n):

self.dfs(heights, i, j, False)

for i in range(self.m):

for j in range(self.n):

if self.pac[i][j] == 1 and self.atl[i][j] == 1:

self.anw.append([i,j])

return self.anw

def dfs(self, heights, x, y, flag):

if self.visited[x][y] == 1:

return

self.visited[x][y] = 1

if flag:

self.pac[x][y] = 1

else:

self.atl[x][y] = 1

for i in range(4):

dx = x + self.dir[i][0]

dy = y + self.dir[i][1]

if dx >= self.m or dx < 0 or dy >= self.n or dy < 0:

continue

if heights[x][y] > heights[dx][dy]:

continue

self.dfs(heights, dx, dy, flag)

return

You are given an array nums of positive integers. In one operation, you can choose any number from nums and reduce it to exactly half the number. (Note that you may choose this reduced number in future operations.)

Return the minimum number of operations to reduce the sum of nums by at least half.

Method: Simulation & Priority Queue/Heap

class Solution:

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

if not nums:

return 0

reduce_ = 0.0

anw = 0

cur_sum = sum(nums)

heap = []

for n in nums:

heapq.heappush(heap, -n) # max heap

while heap:

anw += 1

max_ = heapq.heappop(heap)

reduce_ += (-max_ / 2)

heapq.heappush(heap, max_ / 2)

if reduce_ >= cur_sum / 2:

return anw

else:

continue

return 0

There is an n x n 0-indexed grid with some artifacts buried in it. You are given the integer n and a 0-indexed 2D integer array artifacts describing the positions of the rectangular artifacts where artifacts[i] = [r1i, c1i, r2i, c2i] denotes that the ith artifact is buried in the subgrid where:

• (r1i, c1i) is the coordinate of the top-left cell of the ith artifact and

• (r2i, c2i) is the coordinate of the bottom-right cell of the ith artifact.

You will excavate some cells of the grid and remove all the mud from them. If the cell has a part of an artifact buried underneath, it will be uncovered. If all the parts of an artifact are uncovered, you can extract it.

Given a 0-indexed 2D integer array dig where dig[i] = [ri, ci] indicates that you will excavate the cell (ri, ci), return the number of artifacts that you can extract.

The test cases are generated such that:

• No two artifacts overlap.

• Each artifact only covers at most 4 cells.

• The entries of dig are unique.

Method: hashmap record which has been digged

class Solution:

def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:

visit = [[-1] * n for _ in range(n)]

for i in range(len(dig)):

visit[dig[i][0]][dig[i][1]] = 1

anw = 0

for j in range(len(artifacts)):

cur = artifacts[j]

flag = True

for l in range(cur[0], cur[2]+1):

for k in range(cur[1], cur[3]+1):

if visit[l][k] != 1:

flag = False

break

if flag:

anw += 1

return anw

You are given a 0-indexed 2D array grid of size 2 x n, where grid[r][c] represents the number of points at position (r, c) on the matrix. Two robots are playing a game on this matrix.

Both robots initially start at (0, 0) and want to reach (1, n-1). Each robot may only move to the right ((r, c) to (r, c + 1)) or down ((r, c) to (r + 1, c)).

At the start of the game, the first robot moves from (0, 0) to (1, n-1), collecting all the points from the cells on its path. For all cells (r, c) traversed on the path, grid[r][c] is set to 0. Then, the second robot moves from (0, 0) to (1, n-1), collecting the points on its path. Note that their paths may intersect with one another.

The first robot wants to minimize the number of points collected by the second robot. In contrast, the second robot wants to maximize the number of points it collects. If both robots play optimally, return the number of points collected by the second robot.

Method: Prefix sum, double pointer

class Solution:

def gridGame(self, grid: List[List[int]]) -> int:

if not grid:

return 0

left = 0

right = len(grid[0]) - 1

sum1 = 0 # second row sum from left to right

sum2 = 0 # first row sum from right to left

while left < right:

if sum1 + grid[1][left] < sum2 + grid[0][right]: # move smaller pointer

sum1 += grid[1][left]

left += 1

else:

sum2 += grid[0][right]

right -= 1

return max(sum1, sum2) # return max

We have n buildings numbered from 0 to n - 1. Each building has a number of employees. It's transfer season, and some employees want to change the building they reside in.

You are given an array requests where requests[i] = [fromi, toi] represents an employee's request to transfer from building from i to building to i.

All buildings are full, so a list of requests is achievable only if for each building, the net change in employee transfers is zero. This means the number of employees leaving is equal to the number of employees moving in. For example if n = 3 and two employees are leaving building 0, one is leaving building 1, and one is leaving building 2, there should be two employees moving to building 0, one employee moving to building 1, and one employee moving to building 2.

Return the maximum number of achievable requests.

Method: Backtracking (DFS)

class Solution:

def maximumRequests(self, n: int, requests: List[List[int]]) -> int:

self.anw = 0

building = [0] * n

self.dfs(requests, building, 0, 0)

return self.anw

def dfs(self, requests, building, ind, total):

if ind == len(requests):

for i in range(len(building)):

if building[i] != 0:

return

self.anw = max(self.anw, total)

return

self.dfs(requests, building, ind+1, total) # if not current index satisfies the requirements

# backtracking, if satisfied

building[requests[ind][0]] -= 1

building[requests[ind][1]] += 1

self.dfs(requests, building, ind+1, total+1)

# change back

building[requests[ind][0]] += 1

building[requests[ind][1]] -= 1

You are given n rectangles represented by a 0-indexed 2D integer array rectangles, where rectangles[i] = [widthi, heighti] denotes the width and height of the ith rectangle.

Two rectangles i and j (i < j) are considered interchangeable if they have the same width-to-height ratio. More formally, two rectangles are interchangeable if widthi/heighti == widthj/heightj (using decimal division, not integer division).

Return the number of pairs of interchangeable rectangles in rectangles

Method: Hashmap + Combination Formula

class Solution:

def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:

if not rectangles:

return 0

anw = 0

hashmap = collections.defaultdict(int)

for rec in rectangles:

if rec[0] / rec[1] not in hashmap: # get the ratio

hashmap[rec[0]/rec[1]] = 1

else:

hashmap[rec[0]/rec[1]] += 1

for key in hashmap.keys():

if hashmap[key] > 1: # get those with count > 1, so they can be matched

anw += self.combination(hashmap[key])

return anw

def combination(self, x): # combination formula, m chose 2

return x * (x-1) // 2

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Method: Backtrack, DFS

class Solution:

def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:

ind = 0

# 剪枝

hashcounter = Counter()

for i in range(len(board)):

for j in range(len(board[0])):

hashcounter[board[i][j]] += 1

res = []

for word in words:

tempCounter = Counter(word)

flag = True

for oc in tempCounter:

if hashcounter[oc] < tempCounter[oc]:

flag = False

break

if not flag:

continue

find = False

for i in range(len(board)):

for j in range(len(board[0])):

visited = [[False] * len(board[0]) for _ in range(len(board))] # every word has a own visited matrix

if self.backtrack(board, word, i, j, ind, visited):

res.append(word)

find = True

break

if find:

break

return res

def backtrack(self, board, word, i, j, ind, visited):

if ind == len(word):

return True

if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or visited[i][j]:

return False

if board[i][j] == word[ind]:

visited[i][j] = True

for dx, dy in (0, 1), (0, -1), (1, 0), (-1, 0):

if self.backtrack(board, word, i+dx, j+dy, ind+1, visited):

return True

visited[i][j] = False

return False

Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.

You are given n projects where the ith project has a pure profit profits[i] and a minimum capital of capital[i] is needed to start it.

Initially, you have w capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital.

Pick a list of at most k distinct projects from given projects to maximize your final capital, and return the final maximized capital.

The answer is guaranteed to fit in a 32-bit signed integer.

Method: Priority Queue(Heap)

import heapq

class Solution:

def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:

if not profits and not capital:

return -1

total = []

for i in range(len(profits)):

total.append([profits[i], capital[i]]) # combine two lists

total.sort(key = lambda x: x[1]) # and sort by captical value in ascending order

#print(total)

cur_choice = [] # list to store available projects

ind = 0 # index for the projects

i = 0

while i < k:

while ind < len(profits) and total[ind][1] <= w: # python heapq only supports min heap, so we have to add negative value to perform max heap

heapq.heappush(cur_choice, -total[ind][0]) # add all avaliable choice to queue

ind += 1

if cur_choice:

w -= heapq.heappop(cur_choice) # pop the max capital value

else:

break

i += 1

return w

Balanced strings are those that have an equal quantity of 'L' and 'R' characters. Given a balanced string s, split it in the maximum amount of balanced strings. Return the maximum amount of split balanced strings.

Method: Greedy, keep track of a variable that increases by 1 when find a "R" and decreases by 1 otherwise. (can also do vice-versa). when the variable = 0, we find an answer

class Solution:

def balancedStringSplit(self, s: str) -> int:

if not s:

return 0

anw = 0

track = 0

for i in range(len(s)):

if s[i] == "R": # when meet a R

track += 1 # track variable += 1

if s[i] == "L": # when meet a L

track -= 1 # decrease

if track == 0: # track = 0, we find an answer

anw += 1

return anw

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Method: Stack

class Solution:

def longestValidParentheses(self, s: str) -> int:

if not s:

return 0

stack = [-1]

anw = 0

for i in range(len(s)):

if s[i] == "(":

stack.append(i)

else:

stack.pop()

if not stack:

stack.append(i)

length = i - stack[-1]

anw = max(anw, length)

return anw

Given an m x n matrix, return all elements of the matrix in spiral order.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]

Output: [1,2,3,6,9,8,7,4,5]

Method: 模拟

class Solution:

def spiralOrder(self, matrix: List[List[int]]) -> List[int]:

# 模拟

row = len(matrix)

col = len(matrix[0])

i = 0

j = 0

anw = [0] * (row*col)

dir_ = 0 # 0:right, 1:down 2:left 3:up

for cur in range(row*col):

anw[cur] = (matrix[i][j])

matrix[i][j] = "/"

if dir_ == 0 and (j == col-1 or matrix[i][j+1] == "/"):

dir_ = 1

elif dir_ == 1 and (i == row-1 or matrix[i+1][j] == "/"):

dir_ = 2

elif dir_ == 2 and (j == 0 or matrix[i][j-1] == "/"):

dir_ = 3

elif dir_ == 3 and (i == 0 or matrix[i-1][j] == "/"):

dir_ = 0

if dir_ == 0:

j += 1

if dir_ == 1:

i += 1

if dir_ == 2:

j -= 1

if dir_ == 3:

i -= 1

return anw

字节跳动（ByteDance）校招面试题

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Method：Brute Force，计算相同斜率（直线）上最多的点，并用哈希表统计

class Solution:

def maxPoints(self, points: List[List[int]]) -> int:

n = len(points)

if n < 3: return n # less than 3, just return it

ans = 0

def gcd(a, b) -> int:

while b != 0:

a, b = b, a % b # euclidean algo to find gcd

return a

for i in range(n-1): # loop til last second

hash_map = collections.defaultdict(lambda: 0) # set default value to 0

for j in range(i+1, n):

a = points[i][1] - points[j][1] # delta y

b = points[i][0] - points[j][0] # delta x

gcd_ab = gcd(a, b)

key = tuple((a // gcd_ab, b // gcd_ab))

hash_map[key] += 1

max_ = max(hash_map.values()) # find max points algin with point i

ans = max(ans, max_ + 1) # + 1 to add point i

return ans

Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same.

In one step, you can delete exactly one character in either string.

Method: change the problem to "Longest Common Subsequence" and then modify based on top of the LCS solution

class Solution:

def minDistance(self, word1: str, word2: str) -> int:

if not word1 and not word2:

return 0

dp = [[0] * (len(word2)+1) for _ in range(len(word1)+1)] # dp[i][j] = the longest subsequence of s1(0...i-1) and s2(0...j-1)

for i in range(len(word1)+1): # boundary situation

dp[i][0] = 0

for j in range(len(word2)+1):

dp[0][j] = 0

max_ocur = 0

for i in range(1, len(word1)+1):

for j in range(1, len(word2)+1):

if word1[i-1] == word2[j-1]: # if two letters are equal

dp[i][j] = dp[i-1][j-1] + 1 # update

max_ocur = max(max_ocur, dp[i][j])

else:

dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # else find the max of left partition and right partition

return int(len(word1) - max_ocur) + int(len(word2) - max_ocur)

An integer array is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, [1,3,5,7,9], [7,7,7,7], and [3,-1,-5,-9] are arithmetic sequences.

Given an integer array nums, return the number of arithmetic subarrays of nums.

A subarray is a contiguous subsequence of the array.

Method: Dynamic Programming

class Solution:

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

if not nums or len(nums) < 3:

return 0

anw = 0

dp = 0

dif1 = nums[1] - nums[0]

for i in range(2, len(nums)):

if nums[i] - nums[i-1] == dif1:

dp += 1 # 满足dif1的数量

anw += dp # 总数量

else:

dp = 0

dif1 = nums[i] - nums[i-1]

return anw

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Method: Dynamic Programming

class Solution:

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

if not nums:

return 0

dp = [1] * (len(nums)) # dp[i] 表示以i结尾的数字的最长上升序列的长度

for i in range(1, len(nums)):

for j in range(0, i):

if nums[j] < nums[i]: # 如果满足，那么最长上升序列长度可以再加1

dp[i] = max(dp[j]+1, dp[i])

return max(dp)

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Method: Backtracking, DFS

class Solution:

def generateParenthesis(self, n: int) -> List[str]:

temp = ""

anw = []

self.dfs(anw, temp, 0, 0, n)

return anw

def dfs(self, anw, temp, L, R, n):

if L < R or L > n or R > n: # 特判条件

return

if L == n and R == n: # 找到满足的括号对儿

anw.append(temp)

return

self.dfs(anw, temp+"(", L+1, R, n) # dfs，加左括号

self.dfs(anw, temp+")", L, R+1, n) # dfs，加右括号

阿里巴巴笔试题

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Method：DFS+backtracking, search for the single word in (1,0), (-1,0), (0,1), (0,-1) directions

class Solution:

def exist(self, board: List[List[str]], word: str) -> bool:

if not board:

return False

used = [[False] * (len(board[0])) for _ in range(len(board))]

#flag = False

for i in range(len(board)):

for j in range(len(board[0])):

if self.dfs(board, i, j, used, word, 0):

return True

return False

def dfs(self, board, i, j, used, word, ind):

if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[ind] or used[i][j]: # 边界条件

return False

if ind == len(word)-1: # 如果找到word

return True

if used[i][j] == False: # 如果当前字母没被用过

used[i][j] = True

if self.dfs(board, i+1, j, used, word, ind+1) or self.dfs(board, i-1, j, used, word, ind+1) or self.dfs(board, i, j+1, used, word, ind+1) or self.dfs(board, i, j-1, used, word, ind+1): # 从当先字母做dfs

return True

used[i][j] = False # 回溯

return False

Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1 and return them in any order.

The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).

Method: Backtracking, dfs

class Solution:

def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:

res = []

path = [0] # start node 0

self.dfs(graph, res, path, 0)

return res

def dfs(self, graph, res, path, ind):

if ind == len(graph)-1: # if find a path

res.append(copy.deepcopy(path))

return

for i in graph[ind]:

path.append(i) # back track

self.dfs(graph, res, path, i)

path.pop()

Given a triangle array, return the minimum path sum from top to bottom

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

Method: 自底向上动态规划

class Solution:

def minimumTotal(self, triangle: List[List[int]]) -> int:

if not triangle:

return 0

if len(triangle) == 1:

return min(triangle[0])

for i in range(len(triangle)-1, 0, -1):

for j in range(i):

triangle[i-1][j] += min(triangle[i][j], triangle[i][j+1]) # i位置，或者i+1位置，找最小

return triangle[0][0]

Given a string s, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create. You can return the output in any order.

Example: input = "a1b2", output: ["a1b2", "a1B2", "A1b2", "A1B2"]

Method: backtracking

class Solution:

def letterCasePermutation(self, s: str) -> List[str]:

res = []

path = ""

k = len(s)

self.backtracking(s, k ,res, path, 0)

return res

def backtracking(self, s, k, res, path, ind):

if len(path) == k:

res.append(copy.deepcopy(path))

return

if s[ind].isdigit():

path += (s[ind])

self.backtracking(s, k, res, path, ind+1)

elif s[ind].islower():

self.backtracking(s, k, res, path+(s[ind]), ind+1)

self.backtracking(s, k, res, path+(s[ind].upper()), ind+1)

elif s[ind].isupper():

self.backtracking(s, k, res, path+(s[ind]), ind+1)

self.backtracking(s, k, res, path+(s[ind].lower()), ind+1)

You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water. Details of this question can be found here：

class Solution:

def maxAreaOfIsland(self, grid: List[List[int]]) -> int:

anw = 0

for i in range(len(grid)):

for j in range(len(grid[0])):

if grid[i][j] == 1:

anw = max(self.dfs(grid, i, j), anw)

return anw

def dfs(self, grid, x, y): # dfs, search for all possible directions

if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]) or grid[x][y] == 0 or grid[x][y] == -1: # 特判

return 0

grid[x][y] = -1 # 访问过之后把值改为-1，保证不会重复访问

counter = 1

counter += self.dfs(grid, x-1, y) # 4个方向

counter += self.dfs(grid, x+1, y)

counter += self.dfs(grid, x, y+1)

counter += self.dfs(grid, x, y-1)

return counter

The first problem I am going to share is "The best time to buy and sell stock Version 1", the link for this problem can be found here.

Explanation:

This problem is asked you to write a function that takes a list of prices as parameter, returns the maximum profit if only one deal is allowed. The phrase "one deal" means you can only buy once and sell once for one stock.

Solution:

This problem is a classical dynamic programming approach. The maximum profit can be derived from two states:

1. If there is no stock been held, the max profit is the previous max profit

2. If there is a stock been held, the max profit is the current stock price minus the minimum price that we buy it previously

The max profit is the maximum value between 1 and 2

Similarly, we mentioned that the minimum price that we buy the stock, which can also be derived from take the minimum between the pre-defined value and current stock price when looping the list.

Code: (Python 3 version)

class Solution:

def maxProfit(self, prices: List[int]) -> int:

if not prices or len(prices) <= 1:

return 0

max_profit = 0 # pre-defined

min_price = 1e9 # pre-defined

for i in range(len(prices)):

min_price = min(prices[i], min_price) # find the minimum price tp buy stock

max_profit = max(max_profit, prices[i] - min_price) # find the maximum profit

return int(max_profit)

• Question: Find the K-th greatest element in a given array.

• Example: Input: [-1, 2, 0], K = 3 Output: -1, Input: [3, 2, 3, 1, 2, 4, 5, 5, 6], K = 2 Output: 5

• Solution:

Strategy: We can modify the quick sort algorithm. We just need to find a pivot in the index position len(array) - k(array start from index 0). Denote len(array) - k be the K-th largest index. For example, in the above sample input: [3, 2, 3, 1, 2, 4, 5, 5, 6], the sorted array should be [1, 2, 2, 3, 3, 4, 5, 5, 6]. The second largest element in the array is 5, and it appears at index 9-2=7 (the last occurrence of 5). Therefore, we can combine quick sort with general binary search idea, that is, if the pivot index returned by quick sort algorithm is greater than K-th largest index, we know that the current value is bigger than K-th largest element, so we want to search on the left side of pivot index. Similar idea if the pivot index is less than K-th largest element

Review of quick sort: it is the O(nlogn) sorting algorithm. The key of this algorithm is the pivot. Selecting an arbitrary element as the pivot, we want every number that smaller than the pivot is on the left hand side ; every number that greater than the pivot is on the right hand side. To do this, we find the elements that smaller than pivot in the RIGHT hand side and switch with the elements that greater than pivot in the LEFT hand side. At the end update the pivot value. Another important thing is we'd better randomized the pivot each time to avoid extreme case.

First, we write out the quick sort algorithm as follows:

def partition(self, nums, l, r):

random_ind = random.randint(l, r) # random a position in the range of (left, right)

temp_rand = nums[random_ind]

nums[random_ind] = nums[l]

nums[l] = temp_rand

pivot = nums[l] # randomized pivot

i = l # start from the left side

j = r # j start from the right side

while i != j: # while left pointer is not equal to right pointer

while i < j and nums[j] >= pivot: # search for switch pair, if nums[j] greater than pivot, do noting

j -= 1

while i < j and nums[i] <= pivot: # if nums[i] smaller than pivot, do noting

i += 1

if i < j: # if we find such pair

temp = nums[i] # swap

nums[i] = nums[j]

nums[j] = temp

nums[l] = nums[i] # update the pivot

nums[i] = pivot

return i # return pivot index

The function above returns the pivot index, now we can comparing the pivot index and the K-th largest index:

left = 0

right = len(nums) - 1

while left <= right:

index = self.partition(nums, left, right)

if index == target: # method of binary search

return nums[index]

elif index > target:

right = index - 1

else:

left = index + 1

Full code:

import random

class Solution:

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

target = len(nums) - k

left = 0

right = len(nums) - 1

while left <= right:

index = self.partition(nums, left, right)

if index == target:

return nums[index]

elif index > target:

right = index - 1

else:

left = index + 1

def partition(self, nums, l, r):

random_ind = random.randint(l, r)

temp_rand = nums[random_ind]

nums[random_ind] = nums[l]

nums[l] = temp_rand

pivot = nums[l]

i = l

j = r

while i != j:

while i < j and nums[j] >= pivot:

j -= 1

while i < j and nums[i] <= pivot:

i += 1

if i < j:

temp = nums[i]

nums[i] = nums[j]

nums[j] = temp

nums[l] = nums[i]

nums[i] = pivot

return i

Problem:

Suppose that Mary wants to travel from city A to city B, there are also three small cities between A and B denoted by C, D, E. She starts at city A with no energy supply for her trip initially. However, she could gain some units of energy in all cities prior to her destination if that city has one(denoted by a positive integer > 0). There also exists a situation where there is no energy supply in that city(denoted by 0).

Suppose that, without loss of generality, it is always possible for Mary to travel from A to B with the energy supply in each city prior to B and it requires 1 unit of energy to travel between adjacent cities. If Mary wants to MINIMIZE the times she acquires the energy between A and B, how many times does she need?

Input: [1, 3, 1, 1, 4]

A C D E B

The first element in the array represents city A and the last element in the array represents city B. Others are the small cities between A and B. The number represents how many units of energy available in each city.

Output: 2

Explanation: Mary starts from A, she has 1 unit of energy. Then she travels to C, consumes 1 unit of energy and gains 3 more energy in C. Finally, she could strictly finish her trip(C->D->E->B, she had 0 energy when she arrived at the destination).

3 2 1 0

Solution:

def minimize_step(nums):

if not nums or len(nums) == 1: # base case

return 0

nextMaxDistance = 0 # max distance covered by moving one more step

counter = 0 # number of steps

curDis = 0 # current distance covered

for i in range(len(nums)):

nextMaxDistance = max(nextMaxDistance, i+nums[i]) # calculate the max distance for next step

if i == curDis: # if current position i is at the end of current distance covered

if curDis != len(nums)-1: # and this position is not the end of array

counter += 1 # have to move one more step

curDis = nextMaxDistance # now the current distance covered is the max distance for next step, since we move one step forward

if nextMaxDistance == len(nums)-1: # if the max distance for next step touches the end of array

break # stop looping

else: # if current distance covered already touches the end of array

break # stop looping

return counter