Techniques
Greatest Common Deviders
def gcd(a, b):
while b: a, b = b, a % b
return a
Longest Increasing Subsequence
def lis(nums):
tails = []
for num in nums:
i = bisect_left(tails, num)
if i == len(tails): tails.append(num)
else: tails[i] = num
return len(tails)
2D Array
Location in a square matrix:
+ Main diagnoal is r == c
+ Off diagnoal is r + c == n - 1
Two Pointers Technique
Same sequence Opposite direction
- 11. Container With Most Water
- 1877. Minimize Maximum Pair Sum in Array
- 15. 3Sum solution 1
- 246. Strobogrammatic Number
Same sequence Same direction
Sliding Window
For problems on Array, Strings or Linked List, where the task is to find a subarray/ a section of the linked list satisify certain criterion. General approach is to use two pointers to indicate the left and right of the window, move, expand and contract the window along the line.
- Use some variables to summarize the window for simple questions like sum, avg.
- Use a hashmap/hashset/orderedhashmap/deque to keep track of counts of elements in the window for more complex problems.
- Think about what is the core information needed from the window that is needed to solve the problem.