Problem Names Solution Writeups Code
Maximum Subarray

Check for each number in the array, if that number is larger than current sum, if yes update current sum to that number, if not then take current sum + number. Track only the maximum current sum. This approach is called Kadane's algorithm.

Jump Game

The trick is we can move the goal position forward. At first the goal position is at len(nums) - 1, then starting from len(nums) - 2 to 0, say i, if i >= goal_pos, update goal_pos to i. At last, check if goal_pos is reachable from index 0.

Jump Game II

For each position, create a left and right pointer corresponding to the possible next positions reachable by current position. Be greedy and always jump to the next farthest position. This can be achieved by farhtest = max(farthest, nums[curr] + curr), where curr is in range(left, right + 1).

Gas Station

First check if sum(gas) - sum(cost) < 0, if true simply return -1. Else, check from idx 0 to len(gas) - 1, keep track of the total gas consumption, if total < 0 simply set another starting point to idx + 1. This guarantees an answer.

Hand of Straights

Create a hash table that stores each card with its corresponding card count, and another min heap that will always give the current minimum card value to form a group. If a consecutive card cannot be found or current top number in the min heap is not equal to the value that is going to pop, return FALSE. Else, decrease card count by 1 for each time a card is found.

Merge Triplets to Form Target Triplet

Create a set to check if any number in the target triplet is found. The set will store the index of the found number. Then, check for each triplet, skip those triplet which has a value > target, and if a value matched the target number value, add that index to the set. After the loop, check if the size of the set is 3, if not return false.

Partition Labels

Create a hash map that will store the last occurence of each character in the string. Then, for each character in the string, greedily increase the sliding window.

Valid Parenthesis String

Create two stacks, one stack stores left parenthesis index position, another one stores star index position. When encounter right parenthesis, first pop left paren stack if it is not empty, else pop star stack. After iterating each character in string, check if left parent is not empty, if true then check if star is not empty and the top index is larger than top index of left paren.