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 string, find the length of the  longest substring  without repeating characters. Examples: Given  "abcabcbb" , the answer is  "abc" , which the length is 3. Given  "bbbbb" , the answer is  "b" , with the length of 1. Given  "pwwkew" , the answer is  "wke" , with the length of 3. Note that the answer must be a  substring ,  "pwke"  is a  subsequence  and not a substring. Thought process: Two pointers + sliding window: Pointer i points to the left end of current window. Pointer j points to the right end of current window. Use a hash set to keep track of the characters in current window. Iterate through the string using j. If s[j] is a repeating character, increment i and remove s[i] from set until no repeating character is there. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int lengthOfLongestSubstring ( String s ) { ...

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  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 =...

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. For example, "A man, a plan, a canal: Panama"  is a palindrome. "race a car"  is  not  a palindrome. Note: Have you consider that the string might be empty? This is a good question to ask during an interview. For the purpose of this problem, we define empty string as valid palindrome. Thought process: Two pointers. 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 class Solution { public boolean isPalindrome ( String s ) { int i = 0 ; int j = s . length () - 1 ; while ( i < j ) { while ( i < s . length () && ! Character . isLetterOrDigit ( s . charAt ( i ))) { i ++; } while ( j >= 0 && ! Character . isLetterOrDigit ( s . charAt ( j ))) { j --;...

Implement strStr(). Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Thought process: Iterate through haystack. When I find the first character of needle, iterate through needle. Check if all the rest of the characters match. Solution: 1 2 3 4 5 6 7 8 9 10 class Solution { public int strStr ( String haystack , String needle ) { for ( int i = 0 ; i < haystack . length () - needle . length () + 1 ; i ++) { if ( haystack . substring ( i , i + needle . length ()). equals ( needle )) { return i ; } } return - 1 ; } } Time complexity: Say the length of haystack is h and needle is n. The overall time complexity is O((h - n)n).

Given a singly linked list, determine if it is a palindrome. Follow up: Could you do it in O(n) time and O(1) space? Thought process: Use a fast and a slow pointer to iterate through the list. At the end, slow is at the middle of the list and fast is at the end. Reverse the second half of the list. Iterate through both halves in the same time and check if they match. 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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public boolean isPalindrome ( ListNode head ) { if ( head == null ) { return true ; } ListNode mid = getMid ( head ); ListNode midReversed = reverse ( mid ); while ( midReversed != nu...

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). For example, S  =  "ADOBECODEBANC" T  =  "ABC" Minimum window is  "BANC" . Note: If there is no such window in S that covers all characters in T, return the empty string  "" . If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S. Thought process: Hash map + two pointers. Use a hash map to keep track of the occurrence of T's letters in S. The hash map maps a character in T to the remaining number of it to be matched. The value can also be negative, which means that there is one extra such character in the current window. Iterate through T. Populate map<letter, count>. This map represents the remaining characters in T to be matched. Iterate through S. Initialize variable count = t.length, window = empty string. Pointer i is the le...

Given an array  nums , write a function to move all  0 's to the end of it while maintaining the relative order of the non-zero elements. For example, given  nums = [0, 1, 0, 3, 12] , after calling your function,  nums  should be  [1, 3, 12, 0, 0] . Note : You must do this  in-place  without making a copy of the array. Minimize the total number of operations. Thought process: Two pointers: Pointer 1 iterate through the array. Pointer 2 points to the next position of the number that's not 0. Whenever pointer 1 reaches a number that's not 0, swap pointer 1 and 2's numbers and increment pointer 2. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 public class Solution { public void moveZeroes ( int [] nums ) { int slow = 0 ; for ( int fast = 0 ; fast < nums . length ; fast ++) { if ( nums [ fast ] != 0 ) { int temp = nums [ slow ]; ...