Introduction

Algorithm and Data Structure Notes

#algorithm# #datastructure# #数据结构和算法#

Problems coming from LeetCode, LintCode, TopCoder, CtCi, etc.

Disclaimer:

1. Under construction

2. Some solutions, comments, concepts, explanation, analysis may come from Internet, discussion forums

3. Personal use only, for learning purpose

Contents

Summary

• Introduction

• Linked List

• Sort List

• Merge Two Sorted Lists

• Merge k Sorted Lists

• Linked List Cycle

• Linked List Cycle II

• Add Two Numbers II

• Add Two Numbers

• Odd Even Linked List

• Intersection of Two Linked Lists

• Reverse Linked List

• Reverse Linked List II

• Remove Linked List Elements

• Remove Nth Node From End of List

• Middle of the Linked List

• Design Linked List

• Design Singly Linked List

• Design Doubly Linked List

• Palindrome Linked List

• Remove Duplicates from Sorted List

• Remove Duplicates from Sorted List II

• Implement Stack Using Singly Linked List

• Copy List with Random Pointer

• Binary Search

• Search in Rotated Sorted Array

• Search in Rotated Sorted Array II

• Search in a Sorted Array of Unknown Size

• First Bad Version

• Find Minimum in Rotated Sorted Array

• Find Minimum in Rotated Sorted Array II

• Find Peak Element

• Search for a Range

• Find K Closest Elements

• Search Insert Position

• Peak Index in a Mountain Array

• Heaters

• Hash Table

• Jewels and Stones

• Single Number

• Subdomain Visit Count

• Design HashMap

• Design HashSet

• Logger Rate Limiter

• Isomorphic Strings

• Minimum Index Sum of Two Lists

• Contains Duplicate II

• Contains Duplicate III

• Longest Consecutive Sequence

• Valid Sudoku

• Distribute Candies

• Shortest Word Distance

• Shortest Word Distance II

• String

• Rotate String

• Add Binary

• Implement strStr()

• Longest Common Prefix

• Reverse Words in a String

• Reverse Words in a String II

• Reverse Words in a String III

• Valid Word Abbreviation

• Group Anagrams

• Unique Email Addresses

• Next Closest Time

• License Key Formatting

• String to Integer - atoi

• Ransom Note

• Multiply Strings

• Text Justification

• Reorder Log Files

• Most Common Word

• Valid Parenthesis String

• K-Substring with K different characters

• Find All Anagrams in a String

• Find the Closest Palindrome

• Simplify Path

• Array

• Partition Array

• Median of Two Sorted Arrays

• Intersection of Two Arrays

• Intersection of Two Arrays II

• Maximum Subarray Sum

• Minimum Subarray Sum

• Maximum Subarray II

• Maximum Subarray III

• Subarray Sum Closest

• Subarray Sum

• Plus One

• Maximum Subarray Difference

• Maximum Subarray IV

• Subarray Sum Equals K

• Intersection of Two Arrays

• Intersection of Two Arrays II

• Find Pivot Index

• Rotate Array

• Get Smallest Nonnegative Integer Not In The Array

• Maximize Distance to Closest Person

• Sort Colors

• Next Permutation

• Rotate Image

• Pour Water

• Prison Cells After N Days

• Majority Element

• Can Place Flowers

• Candy

• Matrix

• Spiral Matrix

• Set Matrix Zeroes

• Diagonal Traverse

• Queue

• Design Circular Queue

• Implement Queue using Stacks

• Implement Queue by Two Stacks

• Implement Stack using Queues

• Moving Average from Data Stream

• Walls and Gates

• Open the Lock

• Sliding Window Maximum

• Implement Queue Using Fixed Length Array

• Animal Shelter

• Stack

• Valid Parentheses

• Longest Valid Parentheses

• Min Stack

• Max Stack

• Daily Temperatures

• Evaluate Reverse Polish Notation

• Next Greater Element I

• Next Greater Element II

• Next Greater Element III

• Largest Rectangle in Histogram

• Maximal Rectangle

• Car Fleet

• Heap

• Trapping Rain Water II

• The Skyline Problem

• Top K Frequent Words

• Top K Frequent Words II

• Top K Frequent Elements

• Top k Largest Numbers

• Top k Largest Numbers II

• Minimum Cost to Hire K Workers

• Kth Largest Element in an Array

• Kth Smallest Number in Sorted Matrix

• Kth Smallest Sum In Two Sorted Arrays

• K Closest Points to the Origin

• Merge K Sorted Lists

• Merge K Sorted Arrays

• Top K Frequent Words - Map Reduce

• Data Structure & Design

• Hash Function

• Heapify

• LRU Cache

• LFU Cache

• Rehashing

• Stack Sorting

• Animal Shelter

• Sliding Window Maximum

• Moving Average from Data Stream

• Find Median from Data Stream

• Sliding Window Median

• Design Hit Counter

• Read N Characters Given Read4 II - Call multiple times

• Read N Characters Given Read4

• Flatten 2D Vector

• Flatten Nested List Iterator

• Design Search Autocomplete System

• Time Based Key-Value Store

• Design Tic-Tac-Toe

• Insert Delete GetRandom O(1)

• Union Find

• Find the Connected Component in the Undirected Graph

• Find the Weak Connected Component in the Directed Graph

• Graph Valid Tree

• Number of Islands

• Number of Islands II

• Surrounded Regions

• Most Stones Removed with Same Row or Column

• Redundant Connection

• Trie

• Implement Trie

• Add and Search Word

• Word Search II

• Longest Word in Dictionary

• Palindrome Pairs

• Trie Serialization

• Trie Service

• Design Search Autocomplete System

• Typeahead

• Trees

• Binary Tree Inorder Traversal

• Binary Tree Postorder Traversal

• Binary Tree Preorder Traversal

• Binary Tree Level Order Traversal

• Binary Tree Zigzag Level Order Traversal

• Binary Tree Vertical Order Traversal

• N-ary Tree Level Order Traversal

• N-ary Tree Preorder Traversal

• N-ary Tree Postorder Traversal

• Construct Binary Tree from Preorder and Inorder Traversal

• Populating Next Right Pointers in Each Node

• Populating Next Right Pointers in Each Node II

• Maximum Depth of Binary Tree

• Symmetric Tree

• Validate Binary Search Tree

• Convert Sorted Array to Binary Search Tree

• Path Sum

• Path Sum II

• Path Sum III

• Binary Tree Maximum Path Sum

• Kth Smallest Element in a BST

• Same Tree

• Lowest Common Ancestor of a Binary Tree

• Lowest Common Ancestor of a Binary Search Tree

• Nested List Weight Sum II

• BST Node Distance

• Minimum Distance (Difference) Between BST Nodes

• Closet Common Manager

• N-ary Tree Postorder Traversal

• Serialize and Deserialize Binary Tree

• Serialize and Deserialize N-ary Tree

• Diameter of a Binary Tree

• Print Binary Trees

• Segment Tree

• Segment Tree Build

• Range Sum Query - Mutable

• Binary Indexed Tree

• Graph & Search

• Clone Graph

• N Queens

• Six Degrees

• Number of Islands

• Number of Distinct Islands

• Word Search

• Course Schedule

• Course Schedule II

• Word Ladder

• Redundant Connection

• Redundant Connection II

• Longest Increasing Path in a Matrix

• Reconstruct Itinerary

• The Maze

• The Maze II

• The Maze III

• Topological Sorting

• Island Perimeter

• Flood Fill

• Cheapest Flights Within K Stops

• Evaluate Division

• Alien Dictionary

• Cut Off Trees for Golf Event

• Jump Game II

• Most Stones Removed with Same Row or Column

• Backtracking

• Subsets

• Subsets II

• Letter Combinations of a Phone Number

• Permutations

• Permutations II

• Combinations

• Combination Sum

• Combination Sum II

• Combination Sum III

• Combination Sum IV

• N-Queens

• N-Queens II

• Generate Parentheses

• Subsets of Size K

• Two Pointers

• Two Sum II

• Triangle Count

• Trapping Rain Water

• Container with Most Water

• Minimum Size Subarray Sum

• Minimum Window Substring

• Longest Substring Without Repeating Characters

• Longest Substring with At Most K Distinct Characters

• Longest Substring with At Most Two Distinct Characters

• Fruit Into Baskets

• Nuts & Bolts Problem

• Valid Palindrome

• The Smallest Difference

• Reverse String

• Remove Element

• Max Consecutive Ones

• Max Consecutive Ones II

• Remove Duplicates from Sorted Array

• Remove Duplicates from Sorted Array II

• Move Zeroes

• Longest Repeating Character Replacement

• 3Sum With Multiplicity

• Merge Sorted Array

• 3Sum Smaller

• Backspace String Compare

• Mathematics

• Ugly Number

• Ugly Number II

• Super Ugly Number

• Sqrt(x)

• Random Number 1 to 7 With Equal Probability

• Pow(x, n)

• Narcissistic Number

• Rectangle Overlap

• Happy Number

• Add N Days to Given Date

• Reverse Integer

• Greatest Common Divisor or Highest Common Factor

• Bit Operation

• IP to CIDR

• Random

• Random Pick with Weight

• Random Pick Index

• Linked List Random Node

• Dynamic Programming

• House Robber

• House Robber II

• House Robber III

• Longest Increasing Continuous Subsequence

• Longest Increasing Continuous Subsequence II

• Coins in a Line

• Coins in a Line II

• Coins in a Line III

• Maximum Product Subarray

• Longest Palindromic Substring

• Stone Game

• Burst Balloons

• Perfect Squares

• Triangle

• Pascal's Triangle

• Pascal's Triangle II

• Min Cost Climbing Stairs

• Climbing Stairs

• Unique Paths

• Unique Paths II

• Minimum Path Sum

• Word Break

• Word Break II

• Range Sum Query - Immutable

• Decode Ways

• Edit Distance

• Unique Binary Search Trees

• Unique Binary Search Trees II

• Maximal Rectangle

• Maximal Square

• Regular Expression Matching

• Wildcard Matching

• Flip Game II

• Longest Increasing Subsequence

• Target Sum

• Partition Equal Subset Sum

• Coin Change

• Jump Game

• Can I Win

• Maximum Sum Rectangle in a 2D Matrix

• Cherry Pick

• Knapsack

• Backpack

• Backpack II

• Backpack III

• Backpack IV

• Backpack V

• Backpack VI

• Backpack VII

• Coin Change

• Coin Change II

• High Frequency

• 2 Sum Closest

• 3 Sum

• 3 Sum Closest

• Sort Colors II

• Majority Number

• Majority Number II

• Majority Number III

• Best Time to Buy and Sell Stock

• Best Time to Buy and Sell Stock II

• Best Time to Buy and Sell Stock III

• Best Time to Buy and Sell Stock IV

• Two Sum

• Two Sum II - Input array is sorted

• Two Sum III - Data structure design

• Two Sum IV - Input is a BST

• 4 Sum

• 4 Sum II

• Sorting

• Greedy

• Jump Game II

• Remove K Digits

• Minimax

• Nim Game

• Can I Win

• Sweep Line & Interval

• Meeting Rooms

• Meeting Rooms II

• Merge Intervals

• Insert Interval

• Number of Airplanes in the Sky

• Exam Room

• Employee Free Time

• Closest Pair of Points

• My Calendar I

• My Calendar II

• My Calendar III

• Add Bold Tag in String

• Other Algorithms and Data Structure

• Huffman Coding

• Reservoir Sampling

• Bloom Filter

• External Sorting

• Construct Quad Tree

• Company Tag

• Google

• Guess the Word

• Raindrop on Sidewalk

• Airbnb

• Display Pages (Pagination)

• Amazon

• Problem Solving Summary

• String or Array Rotation

• Tips for Avoiding Bugs

• Substring or Subarray Search

• Sliding Window

• K Sums

• Combination Sum Series

• Knapsack Problems

• Depth-first Search

• Large Number Operation

• Implementation - Simulation

• Monotonic Stack & Queue

• Top K Problems

• Java Interview Tips

• OOP in Java

• Conversion in Java

• Data Structures in Java

• Algorithm Optimization Tips

• Reference