yitonghe00’s gists

yitonghe00 / 349. Intersection of Two Arrays (#1 Hash table).java

Last active November 11, 2019 04:45

349. Intersection of Two Arrays (https://leetcode.com/problems/intersection-of-two-arrays/submissions/): Given two arrays, write a function to compute their intersection.

	// HashTable solution: 2 HashSet, one for nums1 and one for answer
	// Time: O(n1 + n2), 2ms
	// Space: O(n1), 37.4mb
	class Solution {
	public int[] intersection(int[] nums1, int[] nums2) {
	Set<Integer> set1 = new HashSet<>();
	Set<Integer> inter = new HashSet<>();

	for(int i = 0; i < nums1.length; i++) {
	set1.add(nums1[i]);

yitonghe00 / 350. Intersection of Two Arrays II (#1 HashMap).java

Last active October 26, 2019 03:55

350. Intersection of Two Arrays II (https://leetcode.com/problems/intersection-of-two-arrays-ii/): Given two arrays, write a function to compute their intersection.

	// HashMap Solution
	// Time: O(n), 2ms
	// Space: O(n), 36.5mb
	class Solution {
	public int[] intersect(int[] nums1, int[] nums2) {
	// HashMap to save the nums in nums1
	Map<Integer, Integer> map = new HashMap<>();
	for(int n : nums1) {
	if(map.containsKey(n)) {
	map.put(n, map.get(n) + 1);

yitonghe00 / 76. Minimum Window Substring (#1 Two pointer subtring).java

Last active October 29, 2019 20:16

76. Minimum Window Substring (https://leetcode.com/problems/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).

	// Two pointer solution: min/max substring template
	// Time: O(s + t) where m is the length of s and t is the length of t, 3ms
	// Space: O(1) since we have int[128] instead of int[t], 37.8mb
	class Solution {
	public String minWindow(String s, String t) {
	// Init the char table
	int[] table = new int[128];
	int count = 0; // count is the flag that whether we have all the char in t in the substring
	for(int i = 0; i < t.length(); i++) {
	table[t.charAt(i)]++;

yitonghe00 / T01. Substring Two Pointers Solution Template.java

Last active October 29, 2019 19:16

Substring Two Pointers Solution Template

	class Solution {
	public String minWindow(String s, String t) {
	int[] table = new int[128]; //Hash table
	int begin = 0, end = 0, len = Integer.MAX_VALUE, minBegin = 0;
	int count = 0; //Check whether the substring is valid
	for(char c : t.toCharArray()) {
	//Initialize the hash table here
	}
	while(end < s.length()) {
	if(table[s.charAt(end++)]-- /various condition/){//Move end forward to make it valid(min) / invalid(max)

yitonghe00 / 487. Max Consecutive Ones II (#1 Two Pointers Substring template).java

Last active October 31, 2019 19:25

487. Max Consecutive Ones II (https://leetcode.com/problems/max-consecutive-ones-ii/): Given a binary array, find the maximum number of consecutive 1s in this array if you can flip at most one 0.

	// Two pointer solution: min/max substring template
	// Time: O(n), 4ms
	// Space: O(1), 38mb
	class Solution {
	public int findMaxConsecutiveOnes(int[] nums) {
	int begin = 0, end = 0, maxLen = 0, zeros = 0;
	while(end < nums.length) {
	// Expand the window to the right
	if(nums[end++] == 0) {
	zeros++;

yitonghe00 / 713. Subarray Product Less Than K (#1 Array + Two pointer).java

Last active February 11, 2020 02:36

713. Subarray Product Less Than K (https://leetcode.com/problems/subarray-product-less-than-k/): Your are given an array of positive integers nums. Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k.

	// Array + Two pointer solution
	// Time: O(n), 10ms
	// Space: O(1), 54.3mb
	class Solution {
	public int numSubarrayProductLessThanK(int[] nums, int k) {
	// Subarray is [slow, fast). product is the product of subarray
	int slow = 0, fast = 0, ans = 0, product = 1;
	while(fast < nums.length) {
	while(fast < nums.length && (product *= nums[fast]) < k) {
	ans += (fast - slow + 1); // Since [slow, fast] is valid, [slow + 1, fast], [slow + 2, fast], ... are all valid

yitonghe00 / 16. 3Sum Closest (#1 Two Pointers).java

Last active October 25, 2019 06:02

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.16. 3Sum Closest (https://leetcode.com/problems/3sum-closest/):

	// Two pointer: 3 pointers -> loop + begin/end pointers
	// Time: O(n ^ 2), 6ms
	// Space: O(1), 36.5mb
	class Solution {
	public int threeSumClosest(int[] nums, int target) {
	Arrays.sort(nums);
	int ans = nums[0] + nums[1] + nums[2];
	for(int i = 0; i < nums.length - 2; i++) {
	int l = i + 1, r = nums.length - 1;
	while(l < r) {

yitonghe00 / 259. 3Sum Smaller (#1 Two pointer).java

Last active October 25, 2019 06:16

259. 3Sum Smaller (https://leetcode.com/problems/3sum-smaller/): 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.

	// Two pointer: 3 pointer -> loop + begin/end pointers
	// Time: O(n ^ 2), 3ms
	// Space: O(1), 36.3mb
	class Solution {
	public int threeSumSmaller(int[] nums, int target) {
	int ans = 0;
	Arrays.sort(nums);
	for(int i = 0; i < nums.length - 2; i++) {
	int l = i + 1, r = nums.length -1;
	while(l < r) {

yitonghe00 / 611. Valid Triangle Number (#1 Two pointer).java

Last active October 25, 2019 20:28

611. Valid Triangle Number (https://leetcode.com/problems/valid-triangle-number/): Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

	// Two pointer: 3 pointers -> loop + begin/end pointers
	// Time: O(n ^ 2), 4ms
	// Space: O(1), 39.3mb
	class Solution {
	public int triangleNumber(int[] nums) {
	// Sort the array first to use two pointer technic
	Arrays.sort(nums);

	int ans = 0;
	for(int i = nums.length - 1; i >= 2; i--) {

yitonghe00 / 159. Longest Substring with At Most Two Distinct Characters (#1 Two pointer substring).java

Last active October 30, 2019 01:19

159. Longest Substring with At Most Two Distinct Characters (https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/): Given a string s , find the length of the longest substring t that contains at most 2 distinct characters.

	// Two pointer solution: min/max substring template
	// Time: O(n), 1ms
	// Space: O(1), 35.9mb
	class Solution {
	public int lengthOfLongestSubstringTwoDistinct(String s) {
	// Init table that keeps track of char we have and the count
	int[] table = new int[128];
	int count = 0;

	// Two pointer

YitongHe yitonghe00