CS Level Up Series (30 Part Series)

1) CS Level Up Series Introduction
2) Dynamic Arrays
3 ... 28
3) Linked Lists
4) Stacks
5) Queues
6) Hash Tables
7) Binary Search Trees
8) Binary Heaps
9) Priority Queues
10) Graphs
11) Tries
12) Binary & Bit Manipulation
13) Common Sorting Algorithms
14) Searching Algorithms
15) Permutations, Combinations, & Subsets
16) NP-Complete & Fibonacci Heap
17) Detecting Graph Cycles With Depth-First Search
18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS)
19) Topological Sorting of Directed Acyclic Graphs (DAGs)
20) Finding Articulation Points & Bridges in Undirected Graphs
21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm
22) Checking If An Undirected Graph Is Bipartite
23) Extending An Iterator
24) Union-find (Disjoint-set)
25) Minimum Spanning Tree (Kruskal's Algorithm)
26) Sliding Window Technique
27) String Searching Using Rabin-Karp
28) Fenwick Tree (Binary Indexed Tree)
29) Dynamic Programming
30) Traveling Salesman Problem

## Resources:

Takeaways:

- The sliding window technique is where we use two pointers on a collection. We say that one pointer represents the start of the window and the other the end of the window. The space/elements between the two pointers is the window size.
- A sliding window can be of fixed length or it can be variable length (meaning the window expands/contracts dynamically).
- Fixed length is often easier to grasp/think about. Both pointers, say
`i`

and`j`

, in a loop are incremented by the same number each time our max window size is reached. - Variable length is where
`i`

or`j`

change at a different pace to each other. Often questions requiring this technique don't provide a window size, but ask for the largest/smallest possible window given some constraints.

- Fixed length is often easier to grasp/think about. Both pointers, say
- Here are some questions we can use the sliding window technique on:
- In an array of
`n`

integers, find a contiguous`k`

length subarray that has the largest value when it's elements are summed.- We can use two pointers here and our window would be of size
`k`

.

- We can use two pointers here and our window would be of size
- What is the size of the minimum subarray that when summed will equal a target sum?
- We can use two pointers here, but because we want the
*minimum*length subarray (i.e the question is asking how big/small the window is) the window can't be of fixed length.

- We can use two pointers here, but because we want the
- What is the largest subarray of
`k`

distinct characters?- We can use two pointers here. This will again be a variable length window, as we are being asked what the size of the window is (largest subarray). We will also need to use an auxiliary data structure to keep track of how many distinct characters are in a given subarray.

- In an array of
- A less obvious question where sliding window would come in handy:
- Given two strings
`inputA`

&`inputB`

, determine if any permutation of`inputA`

is a substring of`inputB`

.- Here we can use two pointers and the window will be of fixed size/won't ever grow larger than the length of
`inputA`

.

- Here we can use two pointers and the window will be of fixed size/won't ever grow larger than the length of

- Given two strings

Below are solutions to all the problems mentioned. I have annotated the source code with time & space complexities for each solution:

As always, if you found any errors in this post please let me know!

CS Level Up Series (30 Part Series)

1) CS Level Up Series Introduction
2) Dynamic Arrays
3 ... 28
3) Linked Lists
4) Stacks
5) Queues
6) Hash Tables
7) Binary Search Trees
8) Binary Heaps
9) Priority Queues
10) Graphs
11) Tries
12) Binary & Bit Manipulation
13) Common Sorting Algorithms
14) Searching Algorithms
15) Permutations, Combinations, & Subsets
16) NP-Complete & Fibonacci Heap
17) Detecting Graph Cycles With Depth-First Search
18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS)
19) Topological Sorting of Directed Acyclic Graphs (DAGs)
20) Finding Articulation Points & Bridges in Undirected Graphs
21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm
22) Checking If An Undirected Graph Is Bipartite
23) Extending An Iterator
24) Union-find (Disjoint-set)
25) Minimum Spanning Tree (Kruskal's Algorithm)
26) Sliding Window Technique
27) String Searching Using Rabin-Karp
28) Fenwick Tree (Binary Indexed Tree)
29) Dynamic Programming
30) Traveling Salesman Problem

## Discussion