Han Zhu's Study Notes

Given two arrays, write a function to compute their intersection. Example: Given  nums1  =  [1, 2, 2, 1] ,  nums2  =  [2, 2] , return  [2, 2] . Note: Each element in the result should appear as many times as it shows in both arrays. The result can be in any order. Follow up: What if the given array is already sorted? How would you optimize your algorithm? What if  nums1 's size is small compared to  nums2 's size? Which algorithm is better? What if elements of  nums2  are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once? Thought process: Iterate through both arrays. Count the number of each number and put the counts into two maps. Iterate through both maps. For numbers that appear in both maps, put min(count1, count2) of that number into result. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 ...

Given two arrays, write a function to compute their intersection. Example: Given  nums1  =  [1, 2, 2, 1] ,  nums2  =  [2, 2] , return  [2] . Note: Each element in the result must be unique. The result can be in any order. Thought process: Iterate through nums1. Put the elements into a hash set. Iterate through nums2. The elements that the hash set contains are the intersection. 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 [] intersection ( int [] nums1 , int [] nums2 ) { Set < Integer > set = new HashSet <>(); for ( int num : nums1 ) { set . add ( num ); } Set < Integer > intersection = new HashSet <>(); for ( int num : nums2 ) { if ( set . contains ( num )) { intersection . add ( num ); } } ...

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target. Note: Given target value is a floating point. You are guaranteed to have only one unique value in the BST that is closest to the target. Thought process: Record root.val and recursively search for the closest value: If root.val < target, search in the right sub-tree. If abs(result - target) < abs(root.val - target), return result. If root.val >= target, search in the left sub-tree. If abs(result - target) < abs(root.val - target), return result. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int closestValue ( TreeNode root , double target ) { int closest =...

The demons had captured the princess ( P ) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight ( K ) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess. The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately. Some of the rooms are guarded by demons, so the knight loses health ( negative  integers) upon entering these rooms; other rooms are either empty ( 0's ) or contain magic orbs that increase the knight's health ( positive  integers). In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step. Write a function to determine the knight's minimum initial health so that he is able to rescue the princess. For example, given the dungeon below, the initial health of th...

Given a binary search tree, write a function  kthSmallest  to find the  k th smallest element in it. Note:  You may assume k is always valid, 1 ≤ k ≤ BST's total elements. Follow up: What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine? Thought process: Use instance variables to keep track of k and result. Do an in-order traversal of the BST. As I traverse it in ascending order, decrement k for each node. Solution 1 (In-order traversal): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { private int number ; private int count ; public int kthSmallest ( TreeNode root , in...

Given an array which consists of non-negative integers and an integer  m , you can split the array into  m  non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these  m  subarrays. Note: If  n  is the length of array, assume the following constraints are satisfied: 1 ≤  n  ≤ 1000 1 ≤  m  ≤ min(50,  n ) Examples: Input: nums = [7,2,5,10,8] m = 2 Output: 18 Explanation: There are four ways to split nums into two subarrays. The best way is to split it into [7,2,5] and [10,8] , where the largest sum among the two subarrays is only 18. Thought process: Binary search. The range of the answer is between max(nums) and sum(nums). Do a binary search on this range. For every mid value, I check if the array can be split into m sub-arrays, where each sub-array's sum <= mid. If I can, that means mid is too large. Keep the left half. If I can't, that means mid is too small. Keep the...

Follow up   for   H-Index : What if the   citations   array is sorted in ascending order? Could you optimize your algorithm? Thought process: Binary search. Compare citations[mid] with citations.length - mid. If citations[mid] >= citations.length - mid, that means the h-index is at least Math.min(citations.length - mid, nums[mid]). Keep the first half of the array. Otherwise keep the second half.  Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 public class Solution { public int hIndex ( int [] citations ) { if ( citations . length == 0 ) { return 0 ; } int h = 0 ; int length = citations . length ; int left = 0 ; int right = length - 1 ; while ( left + 1 < right ) { int mid = left + ( right - left ) / 2 ; if ( citations [ mid ] >= l...

Implement pow( x ,   n ). Thought process: Shortest problem description!  Recursively calculate pow(x, n / 2). Base cases: n = 0, return 1. n = 1, return x. n = -1, return 1 / x. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public class Solution { public double myPow ( double x , int n ) { if ( n == 0 ) { return 1 ; } if ( n == 1 ) { return x ; } if ( n == - 1 ) { return 1 / x ; } if ( n % 2 == 0 ) { double half = myPow ( x , n / 2 ); return half * half ; } if ( n < 0 ) { return myPow ( x , n / 2 ) * myPow ( x , n / 2 - 1 ); } return myPow ( x , n / 2 ) * myPow ( x , n / 2 + 1 ); } } Time complexity: O(logn).

Given an array of  n  positive integers and a positive integer  s , find the minimal length of a  contiguous  subarray of which the sum >=  s . If there isn't one, return 0 instead. For example, given the array  [2,3,1,2,4,3]  and  s = 7 , the subarray  [4,3]  has the minimal length under the problem constraint. click to show more practice. More practice: If you have figured out the  O ( n ) solution, try coding another solution of which the time complexity is  O ( n  log  n ). Thought process: Sliding window. Iterate through the array. Add numbers until current sum >= s. Record current sub-array length. As a new number is added, check if I can remove a number from the beginning of the sub-array without reducing current sum below s. Keep track of new sub-array length and minimum length. Solution 1: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public in...