“The ultimate goal in designing algorithms and data structures is to find an optimal algorithm for a problem, that is, an algorithm whose worst-case runtime complexity matches the intrinsic complexity of the problem it solves.”
Martin Erwig. “Once Upon an Algorithm: How Stories Explain Computing.”
“Problem simplification is often a crucial step toward solving a problem.”
Martin Erwig. “Once Upon an Algorithm: How Stories Explain Computing.”
The distinction between the complexity of a problem and the complexity of its solutions helps us understand the notion of an optimal solution.
Martin Erwig. “Once Upon an Algorithm: How Stories Explain Computing.”
In this case, even if the sorting takes linearithmic time, it is worth the effort, since it saves precious class time. This is an example of precomputing, where some data needed for an algorithm is computed before the algorithm is executed.
“This strategy of computing information ahead of time is called precomputation.”
“The crucial aspect of precomputation is that computational effort is expended at one time and the computed result is used at a later time. The precomputed result is preserved in a data structure”
“Situations in which one can expect to make use of a data structure repeatedly provide a strong incentive to expend the precomputing effort because the cost can be amortized over several uses.”
“ There are many situations, however, when it’s not clear whether the precomputation effort will pay off.”
“In cases like these, the value of acting early, or precomputing, is called into question by uncertainty about the future. Since the benefit of precomputation depends on a specific outcome of future events, it reflects a rather optimistic computation attitude with a confident outlook on the future.”
“A skeptical attitude toward the future calls for a radically different strategy for scheduling computation, namely, a strategy that tries to delay costly operations as much as possible until they cannot be avoided anymore. The hope or expectation is that something might happen that makes the costly operation obsolete and thus saves its runtime (and potentially other resources). In real life this behavior would be called procrastination; in computer science it is called lazy evaluation. ”
“Lazy evaluation can save computation effort whenever the information that would have been obtained by the saved computation is not needed anymore.”
“While lazy evaluation seems attractive in its promise to not waste effort, it is problematic when an action that becomes unavoidable takes longer than it would have under precomputing, or worse, longer than there is time available. In particular, when several delayed actions become due at the same time, this might present a serious resource problem. Therefore, an overall more sensible strategy is to distribute work evenly over time. While this might waste some effort on precomputing, it avoids crises that a lazy evaluation strategy might bring on.”
Martin Erwig. “Once Upon an Algorithm: How Stories Explain Computing.”
Contains Duplicate
Missing Number
Find All Numbers Disappeared in an Array
Single Number
Climbing Stairs
House Robber
Best Time to Buy and Sell Stock
Maximum Subarray
Range Sum Query - Immutable
Linked List Cycle
Middle of the Linked List
Palindrome Linked List
Remove Linked List Elements
Remove Duplicates from Sorted List
Reverse Linked List
Merge Two Sorted Lists
Meeting Rooms
Binary Search
Find Smallest Letter Greater Than Target
Peak Index in a Mountain Array
Binary Tree Level Order Traversal II
Average of Levels in Binary Tree
Minimum Depth of Binary Tree
Same Tree
Path Sum
Diameter of Binary Tree
Merge Two Binary Trees
Maximum Depth of Binary Tree
Lowest Common Ancestor of a Binary Search Tree
Subtree of Another Tree
Invert Binary Tree
Two Sum
Squares of a Sorted Array
Backspace String Compare
Longest Word in Dictionary
Index Pairs of a String
Majority Element
Product of Array Except Self
Find the Duplicate Number
Find All Duplicates in an Array
Set Matrix Zeroes
Spiral Matrix
Rotate Image
Word Search
45. Letter Case Permutation
46. Subsets
47. Subsets II
48. Permutations
49. Permutations II
50. Combinations
51. Combination Sum
52. Combination Sum II
53. Combination Sum III
54. Generate Parentheses
55. Target Sum
56. Palindrome Partitioning
57. Letter Combinations of a Phone Number
58. Generalized Abbreviation
59. House Robber II
60. Coin Change
61. Maximum Product Subarray
62. Longest Increasing Subsequence
63. Longest Palindromic Substring
64. Word Break
65. Combination Sum IV
66. Decode Ways
67. Unique Paths
68. Jump Game
69. Palindromic Substrings
70. Number of Longest Increasing Subsequence
71. Partition Equal Subset Sum
72. Partition to K Equal Sum Subsets
73. Best Time to Buy and Sell Stock with Cooldown
74. Counting Bits
75. Linked List Cycle II
76. Add Two Numbers
77. Remove Nth Node From End Of List
78. Sort List
79. Reorder List
80. Clone Graph
81. Pacific Atlantic Water Flow
82. Number of Islands
83. Graph Valid Tree
84. Number of Connected Components in an Undirected Graph
85. Reverse Linked List II
86. Rotate List
87. Swap Nodes in Pairs
88. Odd Even Linked List
89. Kth Smallest Element in a Sorted Matrix
90. Find K Pairs with Smallest Sums
91. Merge Intervals
92. Interval List Intersections
93. Non-overlapping Intervals
94. Meeting Rooms II
95. Task Scheduler
96. Minimum Number of Arrows to Burst Balloons
97. Find Minimum in Rotated Sorted Array
98. Find Peak Element
99. Search in Rotated Sorted Array
Search in Rotated Sorted Array II
Search a 2D Matrix
Search a 2D Matrix II
Find K Closest Elements
Minimum Size Subarray Sum
Fruit Into Baskets
Permutation in String
Longest Repeating Character Replacement
Kth Smallest Element in a BST
K Closest Points to Origin
Top K Frequent Elements
Sort Characters By Frequency
Kth Largest Element in an Array
Reorganize String
Course Schedule
Course Schedule II
Minimum Height Trees
Binary Tree Level Order Traversal
Binary Tree Zigzag Level Order Traversal
Populating Next Right Pointers in Each Node
Populating Next Right Pointers in Each Node II
Binary Tree Right Side View
All Nodes Distance K in Binary Tree
Path Sum II
Path Sum III
Lowest Common Ancestor of a Binary Tree
Maximum Binary Tree
Maximum Width of Binary Tree
Construct Binary Tree from Preorder and Inorder Traversal
Validate Binary Search Tree
Implement Trie (Prefix Tree)
3 Sum
3 Sum Closest
Subarrays with Product Less than K
Sort Colours
Maximum XOR of Two Numbers in an Array
First Missing Positive
Longest Consecutive Sequence
Sudoku Solver
N-Queens
Reverse Nodes in k-Group
Merge k Sorted Lists
Smallest Range Covering Elements from K Lists
Insert Interval
Employee Free Time
Count of Range Sum
Sliding Window Maximum
Longest Substring Without Repeating Characters
Minimum Number of K Consecutive Bit Flips
Count Unique Characters of All Substrings of a Given String
Minimum Window Substring
Substring with Concatenation of All Words
Rearrange String k Distance Apart
Course Schedule III
Maximum Frequency Stack
Alien Dictionary
Sequence Reconstruction
Binary Tree Maximum Path Sum
Serialize and Deserialize Binary Tree
Word Search II
Find Median from Data Stream
Sliding Window Median
Trapping Rain Water
Container With Most Water
Concatenated Words
Prefix and Suffix Search
Palindrome Pairs
Design Search Autocomplete System
Word Squares
Sort Items by Groups Respecting Dependencies
Median of Two Sorted Arrays
Join Leetcode Live Coding Telegram group: https://t.me/joinchat/VOy5LhxpFvgV4aJKeMBIRg
Friendly Link to join: https://t.me/livecodingpro
Join Leetcode Live Coding Telegram group: https://t.me/livecodingpro
It is always a good idea to look for similarities between problems. By studying the differences and similarities between two problems, one usually gains insight into both problems. Given a new problem, the first question should be in almost all cases, "Is this problem similar to a known problem?" Sometimes, the similarities between two problems become apparent only after complicated reductions are exhibited. The reductions between matrix and graph algorithms are especially interesting.
