Posts

Showing posts with the label Hash Table

[LeetCode] 350. Intersection of Two Arrays II

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

[LeetCode] 349. Intersection of Two Arrays

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 ); } } ...

[LeetCode] 242. Valid Anagram

Given two strings  s  and  t , write a function to determine if  t  is an anagram of  s . For example, s  = "anagram",  t  = "nagaram", return true. s  = "rat",  t  = "car", return false. Note: You may assume the string contains only lowercase alphabets. Follow up: What if the inputs contain unicode characters? How would you adapt your solution to such case? Thought process: Iterate through both strings, count the number of each character, and compare the counts. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public boolean isAnagram ( String s , String t ) { int [] count = new int [ 26 ]; for ( char c : s . toCharArray ()) { count [ c - 'a' ]++; } for ( char c : t . toCharArray ()) { count [ c - 'a' ]--; } for ( int i : count ) { if ( i !=...

[LeetCode] 3. Longest Substring without Repeating Characters

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 ) { ...

[LeetCode] 249. Group Shifted Strings

Given a string, we can "shift" each of its letter to its successive letter, for example:  "abc" -> "bcd" . We can keep "shifting" which forms the sequence: "abc" -> "bcd" -> ... -> "xyz" Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence. For example, given:  ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"] , A solution is: [ ["abc","bcd","xyz"], ["az","ba"], ["acef"], ["a","z"] ] Thought process: Hash table. If two strings belong to the same shifting sequence, the differences between any consecutive pair of their characters are the same. We can use those differences as encoding for the strings. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ...

[LeetCode] 340. Longest Substring with At Most K Distinct Characters

Given a string, find the length of the longest substring T that contains at most  k  distinct characters. For example, Given s =  “eceba”  and k = 2, T is "ece" which its length is 3. Thought process: Sliding window. Use a hash map of character => integer to keep track of the count of each character in the current window. 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 class Solution { public int lengthOfLongestSubstringKDistinct ( String s , int k ) { Map < Character , Integer > map = new HashMap <>(); int i = 0 ; int longest = 0 ; for ( int j = 0 ; j < s . length (); j ++) { int count = map . getOrDefault ( s . charAt ( j ), 0 ); map . put ( s . charAt ( j ), count + 1 ); if ( map . size () > k ) { while ( i < s . length () && ...

[LeetCode] 554. Brick Wall

Image
There is a brick wall in front of you. The wall is rectangular and has several rows of bricks. The bricks have the same height but different width. You want to draw a vertical line from the  top  to the  bottom  and cross the  least  bricks. The brick wall is represented by a list of rows. Each row is a list of integers representing the width of each brick in this row from left to right. If your line go through the edge of a brick, then the brick is not considered as crossed. You need to find out how to draw the line to cross the least bricks and return the number of crossed bricks. You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks. Example: Input: [[1,2,2,1], [3,1,2], [1,3,2], [2,4], [3,1,2], [1,3,1,1]] Output: 2 Explanation: Note: The width sum of bricks in different rows are the same and won't exceed INT_MAX. The number of bricks in each row is in...

[LeetCode] 535. Encode and Decode TinyURL

Note: This is a companion problem to the  System Design  problem:  Design TinyURL . TinyURL is a URL shortening service where you enter a URL such as  https://leetcode.com/problems/design-tinyurl  and it returns a short URL such as  http://tinyurl.com/4e9iAk . Design the  encode  and  decode  methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL. Thought process: Use a simple counter. Solution 1 (counter): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 public class Codec { private int i ; private Map < Integer , String > map ; public Codec () { i = 0 ; map = new HashMap <>(); } // Encodes a URL to a shortened URL. public String encode ( String longUrl )...

[LeetCode] 525. Contiguous Array

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1. Example 1: Input: [0,1] Output: 2 Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1. Example 2: Input: [0,1,0] Output: 2 Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1. Note:  The length of the given binary array will not exceed 50,000. Thought process: Iterate through the array. Use a variable count to keep track of 0s and 1s. If I see a 1, increment count; Else, decrement count. The trick is that when I see two indices with the same count, the sub-array between them must have equal number of 0 and 1. Use a hash map of count -> index to keep track of this information. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int findMaxLength ( int [] nums ) { Map < Integer , Integer > map = new HashMap ...

[LeetCode] 311. Sparse Matrix Multiplication

Given two  sparse matrices   A  and  B , return the result of  AB . You may assume that  A 's column number is equal to  B 's row number. Example: A = [ [ 1, 0, 0], [-1, 0, 3] ] B = [ [ 7, 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 1 ] ] | 1 0 0 | | 7 0 0 | | 7 0 0 | AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 | | 0 0 1 | Thought process: Create product matrix. Iterate through it and calculate result for each position. This ignores the fact that the matrices are sparse. Solution 1: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int [][] multiply ( int [][] A , int [][] B ) { int Arow = A . length ; int Acolumn = A [ 0 ]. length ; int Brow = B . length ; int Bcolumn = B [ 0 ]. length ; int [][] product = new int [ Arow ][ Bcolumn ]; for ( int i = 0 ; i < Arow ; i ++) { ...

[LeetCode] 76. Minimum Window Substring

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