Han Zhu's Study Notes

Your are given an array of integers  prices , for which the  i -th element is the price of a given stock on day  i ; and a non-negative integer  fee  representing a transaction fee. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.) Return the maximum profit you can make. Example 1: Input: prices = [1, 3, 2, 8, 4, 9], fee = 2 Output: 8 Explanation: The maximum profit can be achieved by: Buying at prices[0] = 1 Selling at prices[3] = 8 Buying at prices[4] = 4 Selling at prices[5] = 9 The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8. Note: 0 < prices.length <= 50000 . 0 < prices[i] < 50000 . 0 <= fee < 50000 . Thought process: Each day there are two options, buy or sell. Use two variables buy and sell to keep track of the max profit. Solutio...

In a given array  nums  of positive integers, find three non-overlapping subarrays with maximum sum. Each subarray will be of size  k , and we want to maximize the sum of all  3*k  entries. Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one. Example: Input: [1,2,1,2,6,7,5,1], 2 Output: [0, 3, 5] Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5]. We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger. Note: nums.length  will be between 1 and 20000. nums[i]  will be between 1 and 65535. k  will be between 1 and floor(nums.length / 3). Thought process: Dynamic programming. Create an array of sums of windows of size k. This array's length will be nums.length - k + 1, because an array can have this many choices of windows. I...

Assume you have an array of length  n  initialized with all  0 's and are given  k  update operations. Each operation is represented as a triplet:  [startIndex, endIndex, inc]  which increments each element of subarray  A[startIndex ... endIndex]  (startIndex and endIndex inclusive) with  inc . Return the modified array after all  k  operations were executed. Example: Given: length = 5, updates = [ [1, 3, 2], [2, 4, 3], [0, 2, -2] ] Output: [-2, 0, 3, 5, 3] Explanation: Initial state: [ 0, 0, 0, 0, 0 ] After applying operation [1, 3, 2]: [ 0, 2, 2, 2, 0 ] After applying operation [2, 4, 3]: [ 0, 2, 5, 5, 3 ] After applying operation [0, 2, -2]: [-2, 0, 3, 5, 3 ] Thought process: The brute force solution has a time complexity of O(kn), where length = n. How can we improve this? We are running a lot of duplicate iterations over the array. Multiple updates may have...

According to the  Wikipedia's article : "The  Game of Life , also known simply as  Life , is a cellular automaton devised by the British mathematician John Horton Conway in 1970." Given a  board  with  m  by  n  cells, each cell has an initial state  live  (1) or  dead  (0). Each cell interacts with its  eight neighbors  (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article): Any live cell with fewer than two live neighbors dies, as if caused by under-population. Any live cell with two or three live neighbors lives on to the next generation. Any live cell with more than three live neighbors dies, as if by over-population.. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction. Write a function to compute the next state (after one update) of the board given its current state. Follow up :  Could you solve ...

Given an array of  n  integers  nums  and a  target , find the number of index triplets  i, j, k  with  0 <= i < j < k < n  that satisfy the condition  nums[i] + nums[j] + nums[k] < target . For example, given  nums  =  [-2, 0, 1, 3] , and  target  = 2. Return 2. Because there are two triplets which sums are less than 2: [-2, 0, 1] [-2, 0, 3] Follow up: Could you solve it in  O ( n 2 ) runtime? Thought process: Although the question requires that 0 <= i < j < k < n, we can still sort the array, because as long as we can find a triplet that satisfy nums[i] + nums[j] + nums[k] < target, we can always swap i, j, and k to make them in the right order. So the idea is to sort the array and use two pointers. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public int threeSumSmaller ( int [] nums , i...

Given a non-negative integer represented as a  non-empty  array of digits, plus one to the integer. You may assume the integer do not contain any leading zero, except the number 0 itself. The digits are stored such that the most significant digit is at the head of the list. Thought process: We don't know if the result array will have the same length as the input array. Therefore, we can use a list to hold the sum, and copy the numbers over to the result array. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public int [] plusOne ( int [] digits ) { List < Integer > list = new ArrayList <>(); int sum = digits [ digits . length - 1 ] + 1 ; int carry = sum / 10 ; list . add ( sum % 10 ); int i = digits . length - 2 ; while ( i >= 0 || carry > 0 ) { int digit = i >= 0 ? digits [ i...

Given  n  non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. For example, Given  [0,1,0,2,1,0,1,3,2,1,2,1] , return  6 . The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.  Thanks Marcos  for contributing this image! Thought process: Iterate through the array. For each element, calculate the amount of water trapped in the current position. To do this, we need to iterate through the elements to the left and the right, and find the cap (top of water). Solution 1 (brute force): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int trap ( int [] height ) { int len = height . length ; int trapped = 0 ; for ( int i = 1 ; i < len - 1 ; i ++) { int leftTop =...

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place, do not allocate extra memory. Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column. 1,2,3  →  1,3,2 3,2,1  →  1,2,3 1,1,5  →  1,5,1 Thought process: Iterate through the array backwards. Find the first index i where nums[i] < nums[i + 1]. There are two cases: i = -1: the array is originally in descending order. Reverse it. i >= 0:  Find the first element from the right that's larger than nums[i]. Swap it with nums[i]. We now need to fix the order of the elements to the right of i. From the iteration at the beginning, we know that all elements to the right of i are in descending order. Reverse t...

Given an array containing  n  distinct numbers taken from  0, 1, 2, ..., n , find the one that is missing from the array. For example, Given  nums  =  [0, 1, 3]  return  2 . Note : Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity? Thought process: Use the XOR operation. a ^ a = 0. Since the numbers run from 0 to n, nums[i] ^ i = 0. If there's no number missing, nums[0] ^ 0 ^ nums[1] ^ 1 ^ ... ^ nums[n] ^ n = 0. Now that there's one number missing, the result of the above XOR calculation will give me the missing number. Solution: 1 2 3 4 5 6 7 8 9 10 11 class Solution { public int missingNumber ( int [] nums ) { int i = 0 ; int xor = 0 ; for (; i < nums . length ; i ++) { xor ^= i ^ nums [ i ]; } return xor ^ i ; } } Time complexity: O(n). S...