1. General Thought Process

- Step 1: Identify problem type (e.g., array, string, graph, etc.).

- Step 2: Look for keywords (e.g., "sorted," "subarray," "paths").

- Step 3: Match to relevant techniques from this cheat sheet.

- Step 4: Choose and apply the corresponding template.

---

1. Common Patterns and Techniques

   Arrays/Strings

- Two Pointers:

- Use for sorted arrays, overlapping intervals, or partitioning.

- Example Problems: #167, #125, #11, #3, #42

- Sliding Window:

- Use for consecutive elements or subarrays.

- Example Problems: #3, #209, #424, #567, #76

- Prefix Sum:

- Use for range queries or cumulative sums.

- Example Problems: #560, #238, #303

---

Searching

- Binary Search:

- Use for sorted data or monotonic functions.

- Example Problems: #704, #33, #153, #162, #658

- DFS (Depth-First Search):

- Use for paths, graph traversal, or backtracking.

- Example Problems: #200, #733, #130, #417, #695

- Template:

```java

void dfs(int[][] grid, int i, int j) {

if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) return;

grid[i][j] = 0; // Mark as visited

dfs(grid, i 1, j);

dfs(grid, i - 1, j);

dfs(grid, i, j 1);

dfs(grid, i, j - 1);

}

```

- Visual Example:

Grid:

```

1 1 0

1 0 0

0 0 1

```

- Start: `(0, 0)`.

- Explore all connected `1`s.

- Mark visited as `0`.

- BFS (Breadth-First Search):

- Use for shortest paths or level-order traversal.

- Example Problems: #127, #207, #994, #417, #286

- Template:

```java

Queue<int\[\]> queue = new LinkedList<>();

queue.add(new int[]{startX, startY});

while (!queue.isEmpty()) {

int[] current = queue.poll();

for (int[] direction : directions) {

int newX = current[0] direction[0];

int newY = current[1] direction[1];

// Process newX, newY

}

}

```

- Visual Example:

Graph:

```

A - B - C

| |

D E

```

- Start: `A`.

- Explore neighbors level by level.

---

Optimization

- Dynamic Programming (DP):

- Use for optimal subproblems and overlapping subproblems.

- Example Problems: #70, #198, #1143, #322, #300

- Template:

```java

int[] dp = new int[n 1];

dp[0] = 1;

for (int i = 1; i <= n; i ) {

dp[i] = dp[i - 1] nums[i]; // Update based on problem logic

}

return dp[n];

```

- Visual Example:

Problem: Climbing Stairs, `n = 4`

- DP Table: `[1, 1, 2, 3, 5]`

- Result: `5` ways.

- Greedy:

- Use for local decisions leading to global results.

- Example Problems: #55, #45, #435, #1029, #452

- Template:

```java

Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

int count = 0, prevEnd = Integer.MIN_VALUE;

for (int[] interval : intervals) {

if (interval[0] >= prevEnd) {

count ;

prevEnd = interval[1];

}

}

return count;

```

- Visual Example:

Intervals: `[[1, 2], [2, 3], [3, 4]]`

- Sort by end time.

- Choose non-overlapping intervals.

---

1. Process of Elimination

   1. Identify Problem Type:

   - Arrays/Strings, Graphs, or Optimization. 2. Match Keywords to Patterns:

   - "Sorted" -> Binary Search, Two Pointers.

   - "Consecutive" -> Sliding Window.

   - "Paths" -> DFS, BFS.

   - "Optimal" -> DP, Greedy. 3. Apply Template:

   - Use the most appropriate template for implementation.

---

1. Priority Order of Techniques

   1. Simple Patterns: Two Pointers, Sliding Window, Binary Search.
   2. Data Structure Based: HashMap, Stack/Queue.
   3. Graph Patterns: DFS, BFS.
   4. Complex Patterns: DP, Backtracking.

---

1. Tips for Practice and Revision

- Daily Routine:

- Solve 1-2 problems from each category.

- Use this cheat sheet to identify techniques.

- Review:

- Annotate solved problems under corresponding techniques.

- Focus on less familiar patterns during revision.